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):
polys.add(tuple(sorted(added)))
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:
to_remove.add(p)
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)
blob.add(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:
