# Pseudoku: A Game of Finding Order in Chaos

You are Pat Doe, a lowly Sudoku puzzle-maker eking out a living by producing hand-made Sudoku puzzles.

After an exhausting eight hours, you've just completed your last Sudoku grid for the day. Unfortunately, it's only after you've completed the grid that you realize the usual $3\times 3$ blocks aren't legal (none of them contain exactly the digits 1 thru 9). To make matters worse, your hand malfunctioned and inserted several bold lines denoting boundaries of neighbouring blocks in unusual places.

Rather than redoing the entire grid, you resolve that you will find out a way to partition the grid into 9 irregular blocks (nonominoes) in such a way that:

• each block contains the digits 1 thru 9 each exactly once
• the blocks respect the existing boundaries (i.e. a boundary may appear nowhere on a block except at its borders)

Can you recover from your error? Can you partition the grid and salvage a workable (if highly irregular) Sudoku grid?

Good luck! :)

The following is an example of a valid block. It is a nonomino containing the digits 1-9 each exactly once, and it respects established boundaries.

The following is not a valid block because it is not a nonomino.

The following is not a valid block because it doesn't respect existing boundaries.

My solution:

Solution method:

I didn't do anything that systematic or logical. I made some vague approximate clusters that had most of the digits 1-9. Then, when a cluster needed a number that it wasn't adjacent to, I'd have it "trade" numbers with adjacent clusters. Often, a whole chain of trades was needed. Though I started on the right and went left, fixing a single disconnected cell in the last incomplete cluster caused a chain reaction that made me reconstruct the bottom right section of the board.

• Well done. I feel like there exists a flash game with puzzles like this. (Also, I wish I'd have seen this earlier, these are the kinds of puzzles for me!) Dec 10 '14 at 11:19
• This is precisely the solution I designed, and (I believe) the only correct solution. Nicely done!
– COTO
Dec 10 '14 at 12:54
• Also, if you think solving these is a worthy challenge, try building one. Getting the first eight blocks to fit is a cakewalk. The ninth one... not so much. :D
– COTO
Dec 10 '14 at 12:56
• @COTO Not the only one. Pink and Grey can swap the "1". Dec 10 '14 at 13:50
• @No.7892142: I stand corrected. ;)
– COTO
Dec 10 '14 at 13:55

Thanks to @xnor presenting a solution, I was finally able to fix the bug in my Python 3 program.

from collections import Counter
import sys

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

walls = [((0,4), (1,4)),
((1,4), (1,5)),
((2,4), (2,5)),
((1,8), (2,8)),
((3,6), (3,7)),
((4,6), (4,7)),
((4,1), (4,2)),
((4,1), (5,1)),
((5,1), (6,1)),
((6,4), (6,5)),
((6,5), (7,5)),
((7,5), (7,6))]

def neighbours(cell):
results = []

for neighbour in [(cell[0]-1, cell[1]), (cell[0]+1, cell[1]),
(cell[0], cell[1]-1), (cell[0], cell[1]+1)]:
if (0 <= neighbour[0] < len(grid) and 0 <= neighbour[1] < len(grid) and
tuple(sorted([cell, neighbour])) not in walls):
results.append(neighbour)

return results

def all_polyominoes(grid):
polys = set()

def search(curr_cell, added, nums, to_search, searched):
if len(nums) == len(grid):
return

while to_search:
n = to_search.pop()

if grid[n[0]][n[1]] not in nums:
search(n, added | {n}, nums | {grid[n[0]][n[1]]},
to_search | {x for x in neighbours(n) if x not in searched},
searched)

return

for i in range(len(grid)):
for j in range(len(grid)):
start_cell = (i, j)
search(start_cell, {start_cell}, {grid[i][j]},
{n for n in neighbours(start_cell)},
{n for n in neighbours(start_cell)})

to_remove = set()

for p in polys:
for cell1 in p:
for cell2 in p:
if tuple(sorted((cell1, cell2))) in walls:

polys = polys - to_remove
return polys

walls = set(tuple(sorted(x)) for x in walls)
polys = list(all_polyominoes(grid))

print(len(polys), "polyominoes formed")

all_cells = {(i, j) for i in range(len(grid)) for j in range(len(grid))}

def good_blobs(cells):
# Look at blobs (contiguous regions of unused cells) with size divisible by grid size

remaining_cells = all_cells - cells

while remaining_cells:
cell = remaining_cells.pop()
blob = {cell}
to_search = [cell]

while to_search:
c = to_search.pop()

for n in neighbours(c):
if n in remaining_cells:
remaining_cells.remove(n)
to_search.append(n)

if len(blob) % len(grid) != 0:
return False

return True

def solve(covering, cells_covered, index):
if len(covering) == len(grid):
print()
print(covering)
return True

for i,p in enumerate(polys[index:]):
if len(covering) == 0:
print(i, end=" ")
sys.stdout.flush()

q = set(p)

if not (q & cells_covered):
new_cells_covered = q | cells_covered

if good_blobs(new_cells_covered):
new_covering = covering + [p]
result = solve(new_covering, new_cells_covered, i+index+1)

#if result:
#    return True

return False

solve([], set(), 0)


The algorithm is pretty simple:

• Generate all valid polyominoes that can be formed from the grid (i.e. contains the numbers 1-9 exactly once, and respects the walls). This is where my bug was as I initially did a flood fill incorrectly, finding only the polyominoes that can be formed "without lifting your pen off the paper", so to speak.
• Keep placing polyominoes while we can, and backtrack if we can't. Basically, recursion.

At this point, it seems like what we have is exactly the set cover problem. But there's restrictions on the polyominoes, namely the grid, allowing us to use one important heuristic that drastically improves the running time:

When you place a new polyomino, look at the regions formed by cells not currently in a polyomino. If any of the regions have size which is not 0 modulo 9, then backtrack.

Using PyPy to speed things up, the program above finds its first solution at the 4 minute mark:

The program terminates after 20 minutes, finding a total of 5 solutions, the others being:

(xnor's is the second one)

It was easier for me to make the images from scratch, hence the difference in colour choice between each grid. Here's the common bits between each solution to make things easier to see:

• Nicely done, that. Dec 11 '14 at 7:42
• I love it when puzzles get solved by code! Dec 12 '14 at 13:11