Sudoku solver

[Marko Rauhamaa]

Dave Angel <davea at davea.name>:

> When in a playful mood, I wonder if all the Sudoku puzzles out there
> are just permutations of a few hundred written by Will Shortz.

A sudoku solver can be trivially turned into a puzzle generator:

========================================================================
$ ./sudoku.py --generate >puzzle.dat
$ cat puzzle.dat
3 . 2 . 4 . . . .
4 5 . . . 6 . . .
6 . . . 9 . . 8 .
. . . . . . 5 . .
. 6 4 . . 9 . 3 .
. 7 3 5 . . . 4 8
. . . . . . 8 . .
. 8 . . 7 . . . 3
. . . . 1 . . . 2

$ ./sudoku.py <puzzle.dat 
3 9 2 8 4 7 1 6 5
4 5 8 1 3 6 7 2 9
6 1 7 2 9 5 3 8 4
8 2 1 4 6 3 5 9 7
5 6 4 7 8 9 2 3 1
9 7 3 5 2 1 6 4 8
1 4 9 3 5 2 8 7 6
2 8 5 6 7 4 9 1 3
7 3 6 9 1 8 4 5 2

========================================================================

========================================================================
#!/usr/bin/env python3

import sys, random

M = 3
N = M * M
P = M * N
Q = M * P

EMPTY = "."

buddies = [ [ buddy
              for buddy in range(Q)
              if buddy != slot and
                  (buddy % N == slot % N or
                   buddy // N == slot // N or
                   buddy // P == slot // P and
                   buddy % N // M == slot % N // M) ]
            for slot in range(Q) ]
interned = { n : n for n in range(1, N + 1) }
candidates = list(interned.values())

def main():
    if len(sys.argv) > 1 and sys.argv[1] == "--generate":
        generate()
        return
    board = []
    for n in sys.stdin.read().split():
        try:
            board.append(int(n))
        except ValueError:
            board.append(EMPTY)
    for solution in solve(board):
        report(solution)

def generate():
    report(minimize(next(solve([ EMPTY ] * Q))))

def solve(board, slot=0):
    if slot == Q:
        yield board[:]
    elif board[slot] is EMPTY:
        shuffled = candidates[:]
        random.shuffle(shuffled)
        for candidate in shuffled:
            for buddy in buddies[slot]:
                if board[buddy] is candidate:
                    break
            else:
                board[slot] = candidate
                yield from solve(board, slot + 1)
        board[slot] = EMPTY
    else:
        yield from solve(board, slot + 1)

def minimize(board):
    while True:
        nonempty_slots = [ slot for slot in range(Q)
                           if board[slot] is not EMPTY ]
        random.shuffle(nonempty_slots)
        for slot in nonempty_slots:
            removed, board[slot] = board[slot], EMPTY
            if uniquely_solvable(board):
                break
            board[slot] = removed
        else:
            return board

def uniquely_solvable(board):
    it = solve(board[:])
    next(it)
    try:
        next(it)
    except StopIteration:
        return True
    return False

def report(board):
    print("\n".join(
        " ".join(str(board[row * N + col])
                 for col in range(N))
        for row in range(N)))
    print()

if __name__ == '__main__':
    main()
========================================================================


Marko