Sudoku solver

[Marko Rauhamaa]

Abhiram R <abhi.darkness at gmail.com>:

> On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R <abhi.darkness at gmail.com> wrote:
>>> On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.kelly at gmail.com> wrote:
>>>> $ cat sudoku2.dat
>>>> . . . 7 . . . . .
>>>> 1 . . . . . . . .
>>>> . . . 4 3 . 2 . .
>>>> . . . . . . . . 6
>>>> . . . 5 . 9 . . .
>>>> . . . . . . 4 1 8
>>>> . . . . 8 1 . . .
>>>> . . 2 . . . . 5 .
>>>> . 4 . . . . 3 . .
>>>>
>>>> I tried the first puzzle you posted, and it took about a second. I
>>>> then started running it on this one before I started typing up this
>>>> post, and it hasn't finished yet.
>>>
>>> Sooooo... Is it done yet? And if yes, how long did it take?
>>
>> I don't know, I killed it at about 16 minutes.
>
> :( Too bad. I'll give it a go myself. And then try implementing my own
> solution. Have a lot of time on my hands today :D

Early optimization and so on and so forth...

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).

The program runs single-threaded. Taking the trouble to parallelize the
algorithm is out of scope for the purposes of this discussion; it would
necessarily destroy the compactness of the solution.

========================================================================
#!/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:
            if not any(board[buddy] is candidate for buddy in buddies[slot]):
                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