A Nonogram solver in C++. See the Wikipedia article.
Requires the Visual Studio C++ developer tools, which can be installed with the Visual Studio Installer.
- In Developer Command Prompt for VS run
codeto open Visual Studio Code. - Confirm the Microsoft C++ tool (MSVC) is working by typing
clin the command prompt. - Run build task: Ctrl + Shift + B
- Run with:
NonogramSolver.exein the cmd. For exampleNonogramSolver --solve --filepath puzzles/lost.txt.
In Developer Command Prompt for VS:
- Set the directory with
set "fileDirname=C:\path\to\NonogramSolverCpp\src" - Build with:
cl.exe /Zi /EHsc /nologo "/Fe%fileDirname%\\NonogramSolver.exe" "%fileDirname%\\*.cpp"
Delete .obj, .ilk and .pdb files. This can be done with: del *.obj *.ilk *.pdb.
The NonogramSolver.exe can be run without these.
In the cmd navigate to the folder with the NonogramSolver.exe and type NonogramSolver. Examples:
NonogramSolver --solve --file-path "jsimlo-puzzles\01 starters\anime.sgriddler"NonogramSolver --solve --show-runs --file-path puzzles/lost.txt > solutions/lost.txtNonogramSolver --solve-collection --guess --file-path collections/various.txt > solutions/various.txtNonogramSolver --solve-collection --file-path collections/activity_workshop_puzzles.txt > solutions/activity_workshop_solutions.txt
Make the directory "solutions" if it doesn't exist.
Based on ideas by Jan Wolter and Steve Simpson.
Algorithm
- Do constraint propagation with row and column sweeps.
- Find the left-most and right-most match for each row/column. This is done using a Nondeterministic Finite State Machine and Thompsons algorithm. This is an O(n^2) algorithm. See my blog post for more detail.
- Find overlaps. This is done by finding a "changer sequence". See the example below. It is made by replacing each symbol with a counter which increments every time the symbols change e.g. from BLACK to WHITE. Counter values which are in the same index in both left and right matches are overlaps.
- A simple filler which adds very simple clues that the left-right algorithm sometimes misses e.g. a white after ending a black sequence.
- If this fails, guess and then go back to constraint propagation.
- First try to find contradictions -> guesses which are obviously wrong. This will happen if there are no matches for the line matcher. The opposite guess is therefore correct.
- Otherwise save the current grid and make a binary guess. Backtrack if it is wrong. This is O(2^n), so it can very easily lead down a never ending spiral of guesses.
Example by [Steve Simpson][lancaster_fast]:
Length: 24
Rule: 1,1,5
Original: >---#---------#-----#####<
Broken: >---#-- - # <
left>000122344444444444555556<
right>000122222222222223455555<
fast>---#--+++++++++-+++####+<
Solve a collection of puzzles in a single file.
Format is:
General description (this line is skipped by the file reader)
-- puzzle title (this line is skipped by the file reader)
[run rows]
[run cols]
-- next puzzle title (this line is skipped by the file reader)
...
---
-- puzzle title (this line is skipped by the file reader)
[run rows]
[run cols]
-- next puzzle title (this line is skipped by the file reader)
...
---
The runs are given by sets of unicode characters, with A=1, B=2 and so on. Spaces represent a new row/column. This can work for a numbers greater than 26, but these will be encoded as non-Basic Latin unicode symbols.
Based on Steve Simpsons .non format.
Format is:
text (this line is skipped by the file reader)
title (this line is skipped by the file reader)
title (this line is skipped by the file reader)
width w (this line is skipped by the file reader)
height h (this line is skipped by the file reader)
rows
x, x, x
....
columns
x, x, x
...
Elephant, 15x15, solved in 0.012s
- - - - - - 03 - - - 01 - - - - - - - - - - - - - - 03 07 - - 05 02 - - 01 01 01 01 - - - - - 01 11 01 02 07 15 07 08 14 09 06 09 09 10 12 - - - 03 . . . . . # # # . . . . . . . - - 04 02 . . # # # # . # # . . . . . . - - 06 06 . # # # # # # . # # # # # # . - 06 02 01 . # # # # # # . # # . . . . # 01 04 02 01 . # . # # # # . # # . . . . # - 06 03 02 . # # # # # # . # # # . . # # - - 06 07 . # # # # # # . # # # # # # # - - 06 08 # # # # # # . # # # # # # # # - - 01 10 . # . . . # # # # # # # # # # - - 01 10 . # . . . # # # # # # # # # # - - 01 10 . # . . . # # # # # # # # # # 01 01 04 04 . # . # . # # # # . . # # # # - 03 04 04 . # # # . # # # # . . # # # # - - 04 04 . . . . . # # # # . . # # # # - - 04 04 . . . . . # # # # . . # # # #
"Where there is smoke", solved in 0.154s with 12 guesses:
- - - - - - - - - - - 01 - - - - - - - - - - - - - - - - - - - - - - 03 - - 01 02 - 03 - - - - - - - - - - - - - - - - - - 01 03 - 01 01 01 02 01 01 - - - - - 03 - - - - - - - - - - 02 06 01 - 03 02 01 04 02 04 03 02 - - - 02 03 - - 01 - - - - - - 02 04 01 02 03 01 01 03 03 02 01 01 03 07 05 01 04 09 08 08 - - - - - - 01 04 04 02 03 02 01 03 01 01 02 01 03 04 04 03 01 02 03 02 - - 01 03 02 01 . # . # # # . . # # . . . . . . . . . # - - - 01 02 02 # . # # . . . # # . . . . . . . . . . . - - - - 03 04 # # # . . . # # # # . . . . . . . . . . - - - 02 03 02 . # # . # # # . . # # . . . . . . . . . - - - 02 01 06 # # . . # . . . . # # # # # # . . . . . - - - 02 13 01 # # . . # # # # # # # # # # # # # . . # - - - 01 01 08 . # . . . . . # . . . . # # # # # # # # - - 02 01 01 07 . # # . . . . # . # . . . # # # # # # # - 01 02 02 02 03 . . # . . . # # . # # . . # # . . # # # - 03 01 01 01 03 # # # . . # . . . . . . . # . # . # # # - 01 02 01 01 03 . # . . # # . . . . . . . # . # . # # # - - 02 01 01 03 . # # . # . . . # . . . . . . . . # # # - - - 01 05 05 . # . . # # # # # . . . . . . # # # # # - - - 01 01 03 . . # . . . . # . . . . . . . . # # # . - - - - 04 02 . . . . . # # # # . . . . . . . # # . . - 02 02 01 02 01 . # # . # # . . # . . . . . . # # . . # - 02 01 02 03 02 . # # . # . . # # . . . . # # # . . # # - - 04 01 06 01 . # # # # . . # . . # # # # # # . . # . - - 03 04 03 02 . # # # . . . # # # # . # # # . . # # . - - - - 04 02 . . . . . . . . . . . # # # # . # # . .
Lost, 78x78, solved in 1.6s:
- # . . # # # . . . # # . # # . . . # # # . # # . # # . # # . . # # . # # # . # # . . # # # . # # # . # # # . . # # # . # # . # # # . . # # . . . # # . # # # - # . # # . # # # . . # # # . # # . # # # . # # . . # # # . # # . # # # . . . # # . # # . . # # # . # # . . . # # . # # # . # # # . # # # . # # # . . # # # . - . . . . # # . # # # . # # . # # . . . # # # . # # . . # # . . # # . # # . # # . # # # . . # # . . # # . # # # . # # . . . # # . # # . # # . . # # . . # . # - # # # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # # - # # # . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # - # . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # # . - . # # . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # . . - # # # . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . # . . . # - # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # - . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # . - . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # . # - # . # . # . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # . # # # # # # . . . . . . . . . . . . . . . . . . . . . # . . # # - # # . # # . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # . . . # # # # # # # . . . . . . . . . . . . . . . . . . . # # # # # - # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # . . # # # # # # # . . . . . . . . . . . . . . . . . . . # # # . . - . # # . # . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . # # # # # - # . . # # # # # # . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . # . . # # - # . . # # # # # # # . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . # # # . . - . . # # # # # # # # # . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . # # # # . - . # # . . # # # # # # # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . # # . # # - # # . # # # # # # # # # # # . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . # . . . # - # # # # # # # # # # # # # # # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . # . # . # - . . # . . . . # # # # # # # # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . # # # # . - . # . # . . . . . # # # # # # # # # # . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . # # # # # - # # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . # . . . # - # # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . # # # . # - . . # . # . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . # # # # . - # # # # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . # # # # # . . . . . . . # # # # # - # # . # # . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . # # # # # . . . . . . . # . . # # - . . # . # . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # . . . . . . # # # . # - # # # . # . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . # # # # # # # . . . . . # # # # . - # # # # # . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . # # # # # # # # . . . . # . # # . - . . . # # . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . # # # # # # # # # # # # # . . . # - # # # . # . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . # # # # # # # # # # # . # . # . # - # # # # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . # # # # # # # # . . . . # # # . # - . # . # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . # # # # # # # # # . . . . # # . # . - . . . # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # . # . # # # - . # . . # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # . . . . . . # # # . # - # # # . # . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . # # # . . . . . . . . # # # # # # # # # . . . . . . . # # . # . - # # # # # . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . # # . . . . . . . . . # # # # # # # . . . . . . . # . . # . - . . . # # . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # . . . # # # . . - . . # . # . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . # . . # # # # # # # # # # # . . . # # # . # - # # # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . # # # . . . . . . . . # # # . # # # # # # # # # # # # # # # . . . # - # # . # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . . # # # # . - . . . . # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . . # # # # # - # # . . # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # . . . . . . # . . # # - # # . # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . # # . # . # - . # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . # . # # # . - # . # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # . . . . # # # . # # - # . # . # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # . . . . . . # # . # . # - . # . # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . # # # # # # # . . . . . . # # . # # # - . # # # # . . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . # # # . . . . . # # # # # # # # # . . . . # # # # . # . - # # # . # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . # # . . . # # # # # # # # # # # . . . # # # # # . # - # . . . # # . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . # . . . . # # # # # # # # # # # # # # # # # . # . # - # # # # # # . . # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # . - . # # # # # . . . # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # . # . - # # # . # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . # # # # # # # # # . # # # # # # # # # # # # # # # # # # # # . . # - # . . # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . # # # # . . . # # # # # # # # # # # # # # # # # # # . . . # - # # # # # . . . . . . # # # # # # # # # # # # # # # # # # # # # # . . . # . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # . # # . - . # # # # . . . . . . . . # # # # # # # # # # # # # # # # # # # # . . . . # . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # - # . . . # # . . . . . . . # # # # # # # # # # # # # # # # # # # . . . . # # . . . . . . . . . . . # # # . # # # # # # # # # # # # # # # # # # # # # # # . # - # . # # # . . . . . . . # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # . . # # - # # # # # . . . . . . . # # # # # # # # # # # # # # # # # # # . . . . . . . . # # . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # . - . # # # # . . . . . . # # # # # # # # # # # # # # # # # # # # . . . . . . . . # # # # . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # . . - . # . . # # # . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # - # . # . # # # . . # # # # # # # # # # # # # # # # # # # # # # . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . # # - # # # # # # . . # # # # # # # # # # # # # # # # # # . . . # # # . . . . . . . . . . # # # . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # - . # . # # . . . # # # # # # # # # # # # # # # # # . . . . # # . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . - # # . # # # . . # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # . # # . - # . # . # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . # # # . . . # # # # # # # # # # # # # # # # # # # . . . . # # - . # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . . . . . . . . # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . # # - # # . # # # # # # # # # # # # # # # # # # # # # . . . . . # # . . . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # - # # . . # # # # # # # # # # # # # # # # # # # # . . . . . # # # # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . - . . # . # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . # . - # . # . # # . # # # . # # . . # # . . # # . # # . # # . # # . . . # # # . # # # . . # # # . # # # . # # # . . # # . # # # . # # . . # # . # # # . # # # # #