27
$\begingroup$

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.

                           pseudoku grid

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.

                           example of a valid pseudoku nonomino


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

                           invalid pseudoku block is not a nonomino


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

                           invalid pseudoku block does not respect existing boundaries

$\endgroup$
13
$\begingroup$

My solution:

The solved puzzle

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.

$\endgroup$
  • $\begingroup$ 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!) $\endgroup$ – No. 7892142 Dec 10 '14 at 11:19
  • $\begingroup$ This is precisely the solution I designed, and (I believe) the only correct solution. Nicely done! $\endgroup$ – COTO Dec 10 '14 at 12:54
  • $\begingroup$ 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 $\endgroup$ – COTO Dec 10 '14 at 12:56
  • 1
    $\begingroup$ @COTO Not the only one. Pink and Grey can swap the "1". $\endgroup$ – No. 7892142 Dec 10 '14 at 13:50
  • $\begingroup$ @No.7892142: I stand corrected. ;) $\endgroup$ – COTO Dec 10 '14 at 13:55
13
$\begingroup$

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:

enter image description here

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

enter image description here

enter image description here

enter image description here

enter image description here

(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:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Nicely done, that. $\endgroup$ – No. 7892142 Dec 11 '14 at 7:42
  • 1
    $\begingroup$ I love it when puzzles get solved by code! $\endgroup$ – Rik_S Dec 12 '14 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.