Nonogram Solver

The program solves nonograms whose solution can be find by logical elimination. (Ie. those that don't require guessing or bifurcation.)

Usage

$ nonogram_solver.py --help
$ nonogram_solver.py examples/house.txt

  X
 XXX
XXXXX
X X X
X XXX

Note that python 3.7 or later is required because of the use of dataclasses.

If the program didn't find a solution then it's worth to pass the --debug option on the command line so you can see how far it got:

$ nonogram_solver.py examples/smiley.txt --debug

Program couldn't find any solution.
   +---- (3<->4|len: 1)
   |+--- (1<->1|len: 1); (3<->4|len: 1)
   ||+-- (4<->4|len: 1)
   |||+- (1<->1|len: 1); (3<->4|len: 1)
   ||||+ (3<->4|len: 1)
   01234
 0       (0<->4|len: 0)
 1  X X  (1<->1|len: 1); (3<->3|len: 1)
 2       (0<->4|len: 0)
 3 .. .. (0<->1|len: 1); (3<->4|len: 1)
 4 ..X.. (0<->4|len: 3)

BTW the puzzle above would require bifurcation for the solution because the possibilities as to which cell mark as black or white cannot be narrowed down further so one of the possibilities should be explored until a discrepancy found or the puzzle is solved.

Puzzle Input Format

Puzzle is defined as a text file with empty lines (containing only whitespace) and lines starting with comment (#) ignored.

1. The first line defines the number of columns and rows in the puzzle in this order separated by a single space.
2. The subsequent lines define the length of blocks in the columns of the puzzle. The leftmost block is the bottom in the column and the rightmost block is at the top of the column. Each number should be separated by a single space.
3. The following lines define the length of blocks in the rows of the puzzle in left-to-right order. Each number should be separated by a single space.

Sample

This puzzle:

               1   
         3 2 5 2 3 
        +-+-+-+-+-+
      1 | | | | | |
        +-+-+-+-+-+
      3 | | | | | |
        +-+-+-+-+-+
      5 | | | | | |
        +-+-+-+-+-+
  1 1 1 | | | | | |
        +-+-+-+-+-+
    1 3 | | | | | |
        +-+-+-+-+-+

should be represented as follows:

# number of columns   number of rows
5 5
# columns:
3
2
5
2 1
3

# rows:
1
3
5
1 1 1
1 3

FAQ

• Is this solver fast?

  No. Speed was not a concern during the implementation. It solves a 100x100 puzzle within 12 seconds on a @2.53GHz Inter i3 CPU.

• What if I need a solver that do bifurcation?

  I suggest checking Dr. Steven Simpson's excellent nonogram solver. It's fast, portable and I assume that it can deal with all the solvable puzzles.

• What are the rules that you're referring to in the code?

  This program is an implementation of the logical rules published by Chiung-Hsueh Yu, Hui-Lung Lee and Ling-Hwei Chen at the paper titled "An efficient algorithm for solving nonograms".