Sudoku solver

[Marko Rauhamaa]

Marko Rauhamaa <marko at pacujo.net>:

> I have optimized my solution slightly:
>
>   1. precalculated integer division operations (big savings)
>
>   2. interned integers (little savings)
>
> The example above now finishes in 41 minutes on my computer. (The C
> version finishes in 13 seconds).

Any considered harmfull.

Changing an "any" test to a loop shortens the solving time from 41
minutes to 14 minutes.

Object creation overhead seems to be the killer. The program still has a
prominent integer incrementation...

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

import sys

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

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():
    board = []
    for n in sys.stdin.read().split():
        try:
            board.append(int(n))
        except ValueError:
            board.append(None)
    solve(board)

def solve(board, slot=0):
    if slot == Q:
        report(board)
    elif board[slot] is None:
        for candidate in candidates:
            for buddy in buddies[slot]:
                if board[buddy] is candidate:
                    break
            else:
                board[slot] = candidate
                solve(board, slot + 1)
        board[slot] = None
    else:
        solve(board, slot + 1)

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