#!/usr/bin/python
    
#
# This programs solves SuDoku problems as seen in The Times.
# It takes a filename as an argument.
#
# sudoku.py puzzle.txt
#
# The file should contain a 9x9 grid of numbers at _s for blank spaces
# A simple example is given below.
# 
# _ 2 _ 8 1 _ 7 4 _
# 7 _ _ _ _ 3 1 _ _
# _ 9 _ _ _ 2 8 _ 5
# _ _ 9 _ 4 _ _ 8 7
# 4 _ _ 2 _ 8 _ _ 3
# 1 6 _ _ 3 _ 2 _ _
# 3 _ 2 7 _ _ _ 6 _
# _ _ 5 6 _ _ _ _ 8
# _ 7 6 _ 5 1 _ 9 _



# Sudoku.py - A Sudoku solver written in Python

# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

import Queue, bisect, copy

#class PriorityQueue(Queue.Queue):
#    def _put(self, item):
#        bisect.insort(self.queue, item)
class PriorityQueue(list):
    def put(self, item):
        bisect.insort(self, item)
    def get(self):
        item = self[0]
        del self[0]
        return item

memo = ([], [([False for x in range(9)], [False for x in range(9)], [[False for x in range(3)] for x in range(3)]) for n in range(9)])

def readFile(filename):
    fp = open(filename)
    data = fp.read()
    fp.close()

    table = []
    for line in data.split("\n"):
        row = []
        if line == "":
            continue
        for element in line.split(" "):
            if element == "_":
                row.append(None)
            elif element.strip() == "":
                pass
            else:
                row.append(int(element))
        assert len(row) == 9
        table.append(row)
    assert len(table) == 9
    return table

def printTable(initial, table):
    print "------------------------------------------------------------------"
    for y in range(len(table)):
        for x in range(len(table[y])):
            if table[y][x] is None:
                print "_\t",
            elif initial[y][x] is None:
                print table[y][x]+1, "\t",
            else:
                print "%c[33;1m%i%c[0m\t" % (27, table[y][x]+1, 27),
        print ""
    print "------------------------------------------------------------------"

def prefill(memo, table):
    for y in range(9):
        for x in range(9):
            v = table[y][x]
            if v is None:
                memo[0].append((x,y))
                continue
            assert v >= 1 and v <= 9
            v = v - 1
            table[y][x] = v
            memo[1][v][0][x] = True
            memo[1][v][1][y] = True
            memo[1][v][2][x/3][y/3] = True
    return len(memo[0])

def findSpace(memo, table):
    if len(memo[0]) == 0:
        return None
    else:
        return iter(memo[0])
 
def chooseNumber(memo, x, y):
    return filter(lambda n: not memo[1][n][0][x] and not memo[1][n][1][y] and not memo[1][n][2][x/3][y/3], range(9))

tries = 0
def markNumber(n, x, y, memo, table):
    global tries
    tries += 1
    print "\r", tries, 
    table[y][x] = n
    memo[0].remove((x,y))
    memo[1][n][0][x] = True
    memo[1][n][1][y] = True
    memo[1][n][2][x/3][y/3] = True

def clearNumber(n, x, y, memo, table):
    table[y][x] = None
    memo[0].append((x,y))
    memo[1][n][0][x] = False
    memo[1][n][1][y] = False
    memo[1][n][2][x/3][y/3] = False

def solve(memo, table, depth=0):
    fs = findSpace(memo, table)
    if fs is None:
        print "\nSolution after %i tries" % (tries, )
        printTable(initial, table)
        return

    queue = PriorityQueue()
    for x, y in fs:
        nums = list(chooseNumber(memo, x, y))
        if len(nums) == 0:
            return
        queue.put((len(nums), x, y, nums))

    c, x, y, nums = queue.get()
    for n in nums:
        markNumber(n, x, y, memo, table)
        solver = solve(memo, table, depth+1)
        clearNumber(n, x, y, memo, table)

import sys

table = readFile(sys.argv[1])

print "Minimum solve: ", prefill(memo, table)

initial = copy.deepcopy(table)

solver = solve(memo, table)

print "No more solutions after %i tries" % (tries, )