bogo_sudoku.py

#!/usr/bin/env python
# encoding: utf-8
'''
Solves Sudoku Boards In Due Time
Austin G. Davis-Richardson

Board.txt:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Usage:
python sudoku.py board.txt
'''

from random import choice
from copy import deepcopy
from time import time, sleep

nums = set(range(1,10))

def main():
    from sys import argv
    filename = argv[1]
    with open(filename) as handle:
        board = load_board(handle)
    print_board(board)
    starttime = time()    
    while True:
        tryboard = solve_board(board)
        if tryboard:
            break
    print_board(tryboard)
    duration = time() - starttime
    print 'solved in %f seconds' % duration
    
def solve_board(board):
    tryboard = deepcopy(board)
    length = len(board[0])
    for row in tryboard:
        for i in range(length):
            for j in range(length):
                diff = tuple(nums - set(tryboard[i]))
                if diff == (): break
                if tryboard[i][j] == 0:
                    tryboard[i][j] = choice(diff)
    if check_board(tryboard):
        return tryboard
    else:
        return False
        
def rotate(board):
    newboard = []
    length = len(board[0])
    for i in range(length):
        row = []
        for j in range(length):
            row.append(board[j][i])
        newboard.append(row)
    return newboard
    
def check_board(board):
    blank = set([])
    def _check(board):
        for row in board:
            if (nums - set(row)) == blank:
                continue
            else:
                return False
        return True
    if _check(rotate(board)) & _check(board):
        return True
    return False

def print_board(board):
    for row in board:
        for number in row:
            print number,
        print ''
    print ''
     
def load_board(handle):
    board = []
    for line in handle:
        line = [ int(i) for i in line.split()]
        board.append(line)
    return board
    
if __name__ == '__main__':
    main()