yangs - Yet Another NonoGram Solver

Aim

Solve the first part of the GCHQ Christmas puzzle using a concise, easy-to-understand Python program.

Method

The puzzle is a 25x25 nonogram. I decided to write a program that uses the same method that I would use if solving the puzzle by hand:

  1. For each row and column, generate the set of patterns that match the given clues
  2. For each row, eliminate the patterns that don't match the cells we already know
  3. For each row, deduce the known cells based on the reduced pattern set
  4. For each column, eliminate the patterns that don't match the cells we already know
  5. For each column, deduce the known cells based on the reduced pattern set
  6. Go back to 2. and repeat, unless we've solved it

Imports and settings

In [1]:
from itertools import combinations_with_replacement
SHOW_TESTS = True

Input data

Put all the clues into a list of lists:

In [2]:
ROW_CLUES = [
    [7, 3, 1, 1, 7,],
    [1, 1, 2, 2, 1, 1,],
    [1, 3, 1, 3, 1, 1, 3, 1,],
    [1, 3, 1, 1, 6, 1, 3, 1,],
    [1, 3, 1, 5, 2, 1, 3, 1,],
    [1, 1, 2, 1, 1,],
    [7, 1, 1, 1, 1, 1, 7,],
    [3, 3,],
    [1, 2, 3, 1, 1, 3, 1, 1, 2,],
    [1, 1, 3, 2, 1, 1,],
    [4, 1, 4, 2, 1, 2,],
    [1, 1, 1, 1, 1, 4, 1, 3,],
    [2, 1, 1, 1, 2, 5,],
    [3, 2, 2, 6, 3, 1,],
    [1, 9, 1, 1, 2, 1,],
    [2, 1, 2, 2, 3, 1,],
    [3, 1, 1, 1, 1, 5, 1,],
    [1, 2, 2, 5,],
    [7, 1, 2, 1, 1, 1, 3,],
    [1, 1, 2, 1, 2, 2, 1,],
    [1, 3, 1, 4, 5, 1,],
    [1, 3, 1, 3, 10, 2,],
    [1, 3, 1, 1, 6, 6,],
    [1, 1, 2, 1, 1, 2,],
    [7, 2, 1, 2, 5,],
]

COL_CLUES = [
    [7, 2, 1, 1, 7,],
    [1, 1, 2, 2, 1, 1,],
    [1, 3, 1, 3, 1, 3, 1, 3, 1,],
    [1, 3, 1, 1, 5, 1, 3, 1,],
    [1, 3, 1, 1, 4, 1, 3, 1,],
    [1, 1, 1, 2, 1, 1,],
    [7, 1, 1, 1, 1, 1, 7,],
    [1, 1, 3,],
    [2, 1, 2, 1, 8, 2, 1,],
    [2, 2, 1, 2, 1, 1, 1, 2,],
    [1, 7, 3, 2, 1,],
    [1, 2, 3, 1, 1, 1, 1, 1,],
    [4, 1, 1, 2, 6,],
    [3, 3, 1, 1, 1, 3, 1,],
    [1, 2, 5, 2, 2,],
    [2, 2, 1, 1, 1, 1, 1, 2, 1,],
    [1, 3, 3, 2, 1, 8, 1,],
    [6, 2, 1,],
    [7, 1, 4, 1, 1, 3,],
    [1, 1, 1, 1, 4,],
    [1, 3, 1, 3, 7, 1,],
    [1, 3, 1, 1, 1, 2, 1, 1, 4,],
    [1, 3, 1, 4, 3, 3,],
    [1, 1, 2, 2, 2, 6, 1,],
    [7, 1, 3, 2, 1, 1,],
]

ROW_LEN = len(COL_CLUES)
COL_LEN = len(ROW_CLUES)

Set up a grid to contain the result, and fill in the cells we already know.

Notes:

  • I'm using 1 to represent a known filled cell, 0 for a known blank cell, and None for an unknown cell.
  • The rows must be repeated using list comprehension. Using list repetition (i.e. result = [[None] * ROW_LEN] * COL_LEN) would result in a list of references to the same row list.
In [3]:
# Create blank results grid
result = [[None] * ROW_LEN for c in range(COL_LEN)]

# Fill in the cells we already know
known_coords = {3: (3, 4, 12, 13, 21),
                8: (6, 7, 10, 14, 15, 18),
                16: (6, 11, 16, 20),
                21: (3, 4, 9, 10, 15, 20, 21)
               }

for row, cols in known_coords.items():
    for col in cols:
        result[row][col] = 1

Helper functions

Define some functions to display the results:

In [4]:
SYMBOLS = {None: '?', 1:'#', 0:'.'}

def print_row(row, i=0):
    print '%s [%s]' % (str(i).rjust(2), ' '.join(SYMBOLS[cell] for cell in row))
        
def print_grid(rows):
    col_labels = [str(i).rjust(2) for i in range (len(rows[0]))]
    print '   ', ' '.join(cl[0] for cl in col_labels)
    print '   ', ' '.join(cl[1] for cl in col_labels)
    for i, row in enumerate(rows):
        print_row(row, i)

# Test
if SHOW_TESTS:
    print_grid(result)
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 1 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 2 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 3 [? ? ? # # ? ? ? ? ? ? ? # # ? ? ? ? ? ? ? # ? ? ?]
 4 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 5 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 6 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 7 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
 8 [? ? ? ? ? ? # # ? ? # ? ? ? # # ? ? # ? ? ? ? ? ?]
 9 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
10 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
11 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
12 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
13 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
14 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
15 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
16 [? ? ? ? ? ? # ? ? ? ? # ? ? ? ? # ? ? ? # ? ? ? ?]
17 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
18 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
19 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
20 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
21 [? ? ? # # ? ? ? ? # # ? ? ? ? # ? ? ? ? # # ? ? ?]
22 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
23 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
24 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]

And a function to count the number of unknown cells in the results. We'll use this to check if we've solved the puzzle, or if we're not making progress.

In [5]:
def count_unknowns(rows):
    return sum(row.count(None) for row in rows)

# Test
if SHOW_TESTS:
    print 'Unknowns = %s' % count_unknowns(result)
Unknowns = 603

Generate sets of patterns

Terminology:

  • Block = one or more consecutive filled cells
  • Space = an unfilled cell
  • Clue = the lengths of each block
  • Pattern = a series of cells that match the clue

The generate_patterns function does step 1 of the general approach: give it the clue and the pattern length, and it generates all the possible patterns.

For the clue [7, 3, 1, 1, 7] and length = 25:

  • There are 5 blocks, comprising 7 + 3 + 1 + 1 + 7 = 19 filled cells.
  • There are 6 positions where spaces can be inserted (numbered 0 through 5)
  • The middle 4 positions all must have at least one space - so there are 4 fixed spaces
  • That means there are 25 - 19 - 4 = 2 movable spaces, which can go in any permutation of the 6 positions
  • Therefore, there are 6CR2 = 21 different patterns that match this clue
position 0 1 1 2 2 3 3 4 4 5 5
blocks and fixed spaces 1111111 0 111 0 1 0 1 0 1111111
movable spaces (any 2 of 6 positions) ? ? ? ? ? ?
In [6]:
def generate_patterns(clue, length):
    blocks = [0] + clue
    fixed_spaces = [0] + [1] * (len(clue) - 1) + [0]
    positions = range(len(blocks))
    n_movable_spaces = length - sum(clue) - len(clue) + 1
    for space_positions in combinations_with_replacement(positions, n_movable_spaces):
        movable_spaces = [space_positions.count(p) for p in positions]
        yield sum(([1] * b + [0] * (fs + ms) for b, fs, ms in zip(blocks, fixed_spaces, movable_spaces)), [])

# Test
if SHOW_TESTS:
    test_pats = list(generate_patterns([7, 3, 1, 1, 7], 25))
    print_grid(test_pats)
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [. . # # # # # # # . # # # . # . # . # # # # # # #]
 1 [. # # # # # # # . . # # # . # . # . # # # # # # #]
 2 [. # # # # # # # . # # # . . # . # . # # # # # # #]
 3 [. # # # # # # # . # # # . # . . # . # # # # # # #]
 4 [. # # # # # # # . # # # . # . # . . # # # # # # #]
 5 [. # # # # # # # . # # # . # . # . # # # # # # # .]
 6 [# # # # # # # . . . # # # . # . # . # # # # # # #]
 7 [# # # # # # # . . # # # . . # . # . # # # # # # #]
 8 [# # # # # # # . . # # # . # . . # . # # # # # # #]
 9 [# # # # # # # . . # # # . # . # . . # # # # # # #]
10 [# # # # # # # . . # # # . # . # . # # # # # # # .]
11 [# # # # # # # . # # # . . . # . # . # # # # # # #]
12 [# # # # # # # . # # # . . # . . # . # # # # # # #]
13 [# # # # # # # . # # # . . # . # . . # # # # # # #]
14 [# # # # # # # . # # # . . # . # . # # # # # # # .]
15 [# # # # # # # . # # # . # . . . # . # # # # # # #]
16 [# # # # # # # . # # # . # . . # . . # # # # # # #]
17 [# # # # # # # . # # # . # . . # . # # # # # # # .]
18 [# # # # # # # . # # # . # . # . . . # # # # # # #]
19 [# # # # # # # . # # # . # . # . . # # # # # # # .]
20 [# # # # # # # . # # # . # . # . # # # # # # # . .]

Eliminate patterns

The eliminate_patterns function does steps 2 and 4 of the general approach: give it a list of patterns, and it will eliminate the patterns that don't match the already-known cells.

Notes:

  • The set of patterns is iterated in reverse order so that deleting an item won't change the indices of the items yet to be iterated.
  • The any function will short circuit as soon as it finds a cell in the pattern that conflicts with the known cells
  • I've used del patterns[i] instead of patterns.pop(i) because we don't need to do anything with the item after it's removed from the list
In [7]:
def eliminate_patterns(patterns, knowns):
    for i in reversed(range(len(patterns))):
        if any(k not in (p, None) for p, k in zip(patterns[i], knowns)):
            del patterns[i]

# Test
if SHOW_TESTS:
    print 'Before:'
    print_grid(test_pats)
    print
    print 'Apply Knowns:'
    test_knowns = [1] + [None]*23 + [1]
    print_row(test_knowns)
    print
    print 'After:'
    eliminate_patterns(test_pats, test_knowns)
    print_grid(test_pats)
Before:
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [. . # # # # # # # . # # # . # . # . # # # # # # #]
 1 [. # # # # # # # . . # # # . # . # . # # # # # # #]
 2 [. # # # # # # # . # # # . . # . # . # # # # # # #]
 3 [. # # # # # # # . # # # . # . . # . # # # # # # #]
 4 [. # # # # # # # . # # # . # . # . . # # # # # # #]
 5 [. # # # # # # # . # # # . # . # . # # # # # # # .]
 6 [# # # # # # # . . . # # # . # . # . # # # # # # #]
 7 [# # # # # # # . . # # # . . # . # . # # # # # # #]
 8 [# # # # # # # . . # # # . # . . # . # # # # # # #]
 9 [# # # # # # # . . # # # . # . # . . # # # # # # #]
10 [# # # # # # # . . # # # . # . # . # # # # # # # .]
11 [# # # # # # # . # # # . . . # . # . # # # # # # #]
12 [# # # # # # # . # # # . . # . . # . # # # # # # #]
13 [# # # # # # # . # # # . . # . # . . # # # # # # #]
14 [# # # # # # # . # # # . . # . # . # # # # # # # .]
15 [# # # # # # # . # # # . # . . . # . # # # # # # #]
16 [# # # # # # # . # # # . # . . # . . # # # # # # #]
17 [# # # # # # # . # # # . # . . # . # # # # # # # .]
18 [# # # # # # # . # # # . # . # . . . # # # # # # #]
19 [# # # # # # # . # # # . # . # . . # # # # # # # .]
20 [# # # # # # # . # # # . # . # . # # # # # # # . .]

Apply Knowns:
 0 [# ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #]

After:
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [# # # # # # # . . . # # # . # . # . # # # # # # #]
 1 [# # # # # # # . . # # # . . # . # . # # # # # # #]
 2 [# # # # # # # . . # # # . # . . # . # # # # # # #]
 3 [# # # # # # # . . # # # . # . # . . # # # # # # #]
 4 [# # # # # # # . # # # . . . # . # . # # # # # # #]
 5 [# # # # # # # . # # # . . # . . # . # # # # # # #]
 6 [# # # # # # # . # # # . . # . # . . # # # # # # #]
 7 [# # # # # # # . # # # . # . . . # . # # # # # # #]
 8 [# # # # # # # . # # # . # . . # . . # # # # # # #]
 9 [# # # # # # # . # # # . # . # . . . # # # # # # #]

Deduce known cells

The generate_knowns function does steps 3 and 5 of the general approach: give it a set of patterns, and it will deduce which cells are now known.

For each cell, if all the patterns have the same value for each cell, then that is the only possible value for that cell.

Notes:

  • zip(*patterns) transposes the pattern set so that we check one column at a time instead of one row a time
  • the all function will short circuit as soon as it finds a cell that doesn't match the cell in first pattern
In [8]:
def generate_knowns(patterns):
    for col in zip(*patterns):
        yield col[0] if all(c == col[0] for c in col) else None

# Test
if SHOW_TESTS:
    print 'Patterns:'
    print_grid(test_pats)
    print
    print 'Knowns:'
    test_knowns = list(generate_knowns(test_pats))
    print_row(test_knowns)
Patterns:
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [# # # # # # # . . . # # # . # . # . # # # # # # #]
 1 [# # # # # # # . . # # # . . # . # . # # # # # # #]
 2 [# # # # # # # . . # # # . # . . # . # # # # # # #]
 3 [# # # # # # # . . # # # . # . # . . # # # # # # #]
 4 [# # # # # # # . # # # . . . # . # . # # # # # # #]
 5 [# # # # # # # . # # # . . # . . # . # # # # # # #]
 6 [# # # # # # # . # # # . . # . # . . # # # # # # #]
 7 [# # # # # # # . # # # . # . . . # . # # # # # # #]
 8 [# # # # # # # . # # # . # . . # . . # # # # # # #]
 9 [# # # # # # # . # # # . # . # . . . # # # # # # #]

Knowns:
 0 [# # # # # # # . ? ? # ? ? ? ? ? ? . # # # # # # #]

Solve it

Do step 1: generate sets of patterns that match the clues given for each row and column.

In [9]:
rows_valid_patterns = [list(generate_patterns(c, ROW_LEN)) for c in ROW_CLUES]
cols_valid_patterns = [list(generate_patterns(c, COL_LEN)) for c in COL_CLUES]

Calculate how many unknowns there are before we start trying to solve:

In [10]:
unknowns = [count_unknowns(result)]

Repeat through steps 2-5 until either:

  • There are no more unknowns i.e. we've solved it
  • The number of unknowns hasn't decreased since the last pass i.e. we've solved as much as possible

Notes:

  • map is used to apply eliminate_patterns and generate_knowns to multiple rows/columns
  • zip(*) is used to transpose the results grid when working on columns, and transpose it back again before working on rows
In [11]:
while len(unknowns) < 2 or unknowns[-1] not in (0, unknowns[-2]):
    map(eliminate_patterns, rows_valid_patterns, result)
    result = map(generate_knowns, rows_valid_patterns)
    map(eliminate_patterns, cols_valid_patterns, zip(*result))
    result = zip(*map(generate_knowns, cols_valid_patterns))
    unknowns.append(count_unknowns(result))

Display the results:

In [12]:
for i, u in enumerate(unknowns):
    print 'pass %s: %s unknowns' % (i, u)
print_grid(result)
pass 0: 603 unknowns
pass 1: 317 unknowns
pass 2: 58 unknowns
pass 3: 10 unknowns
pass 4: 0 unknowns
                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
 0 [# # # # # # # . # # # . . . # . # . # # # # # # #]
 1 [# . . . . . # . # # . # # . . . . . # . . . . . #]
 2 [# . # # # . # . . . . . # # # . # . # . # # # . #]
 3 [# . # # # . # . # . . # # # # # # . # . # # # . #]
 4 [# . # # # . # . . # # # # # . # # . # . # # # . #]
 5 [# . . . . . # . . # # . . . . . . . # . . . . . #]
 6 [# # # # # # # . # . # . # . # . # . # # # # # # #]
 7 [. . . . . . . . # # # . . . # # # . . . . . . . .]
 8 [# . # # . # # # . . # . # . # # # . # . . # . # #]
 9 [# . # . . . . . . # # # . # # . . . . # . . . # .]
10 [. # # # # . # . # # # # . # # . # . . . . # # . .]
11 [. # . # . . . # . . . # . # . # # # # . # . # # #]
12 [. . # # . . # . # . # . . . . . . # # . # # # # #]
13 [. . . # # # . # # . # # . # # # # # # . # # # . #]
14 [# . # # # # # # # # # . # . # . . # # . . . . # .]
15 [. # # . # . . # # . . . # # . # # # . . . . . # .]
16 [# # # . # . # . # . . # . . . . # # # # # . # . .]
17 [. . . . . . . . # . . . # # . # # . . . # # # # #]
18 [# # # # # # # . # . . # # . . . # . # . # . # # #]
19 [# . . . . . # . # # . . # . . # # . . . # # . # .]
20 [# . # # # . # . . . # # # # . . # # # # # . . # .]
21 [# . # # # . # . # # # . # # # # # # # # # # . # #]
22 [# . # # # . # . # . . # # # # # # . # # # # # # .]
23 [# . . . . . # . . # # . . . . . . # . # . # # . .]
24 [# # # # # # # . # # . . . # . # # . . . # # # # #]