# http://sudoku.sourceforge.net/
# http://www.sudokusolver.co.uk/solvemethods.html

import os
import sys
import string
from sets import Set
import copy

elements = tuple(range(1,10))
nelements = len(elements)

sample_boards = ( { "name":"Easy Board 1",
                    "board":"     5    1 62 58  3 4 8   6 8   23  4     9  93   6 4   8 2 1  54 96 7    1     ",
                    "scanned":"826935147419627583735418926678549231541263798293781654367852419154396872982174365",
                    "solution":"826935147419627583735418926678549231541263798293781654367852419154396872982174365" },
                  { "name":"Easy Board 2",
                    "board":"2   849 35   6 1   6  278  38   27 1    9    1 46   58  573  1   9 4   64 791   2",
                    "scanned":"271584963548369127963127845386452791752891634194673258625738419819245376437916582",
                    "solution":"271584963548369127963127845386452791752891634194673258625738419819245376437916582" },
                  { "name":"Easy Board 3",
                    "board":"  9 7 61    4 87 3 38    9 97456   2 1     6 2   87349 5    82 1 72 5    92 1 4  ",
                    "scanned":"549372618621498753738651294974563182813924567265187349456739821187245936392816475",
                    "solution":"549372618621498753738651294974563182813924567265187349456739821187245936392816475" },
                  { "name":"Easy Board 4",
                    "board":"53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79",
                    "scanned":"534678912672195348198342567859761423426853791713924856961537284287419635345286179",
                    "solution":"534678912672195348198342567859761423426853791713924856961537284287419635345286179" },
                  { "name":"Easy Board 5",
                    "board":"  1234       5  1 567      3  8 7   12     96   9 1  5      482 9  8       5723  ",
                    "scanned":"981234657243756918567198243359867124128345796476921835735619482692483571814572369",
                    "solution":"981234657243756918567198243359867124128345796476921835735619482692483571814572369" },
                  { "name":"Hard Board 1",
                    "board":   "  73 61  8   4   7  6   9  3  9 1  6  1 8 7  5  2 4  1  5   4  2   1   3  94 72  ",
                    "scanned": "BD73C61DD8D3B4CBC7BD6DCC9ED3B29B1BC6CC1B8B7CC5B82B4391CE5BDD4DB2C4C1CCD3BD94C72DB",
                    "solution":"427396185893145627156728934342971856961583742578264391715832469284619573639457218" },
                  { "name":"Hard Board 2",
                    "board":" 1   234    456       3 678  62 9   8 7   1 9   8 54  435 9       627    625   9 ",
                    "scanned":"619782345CCB456BBBBB4931678CB62B9CCB8B73641B9DBB8B54CD435198BBCBBB627BDCB62543B9B",
                    "solution":"619782345378456912254931678546219783827364159193875426435198267981627534762543891" },
                  { "name":"Hard Board 3",
                    "board":"1  2    345  6       758    1  4  9  6     5  3  1  7    926       3  287    5  1",
                    "scanned":"17829456345B361B8CCBD758C1CC1CB4BD9BB6C87CD5BD3DB1BD7C381926745CBD137B287BC485B31",
                    "solution":"178294563459361287623758419817542396964873152235619874381926745546137928792485631" },
				  { "name":"Too Difficult",
                    "board":" 2          6    3 74 8         3  2 8  4  1 6  5         1 78 5    9          4 ",
                    "scanned":"D2FEDDFDGCCD6DEFD3C74D8CEDDDDDDC3ED2D8EC4CD1D6DE5CDDCDDDDC1D78C5DFED9DCBFDGDEEF4D",
                    "solution":"D26EDDECFCCD6DEFD3C74D8CEDDDDDDC3ED2D8EC4CD1D6DE5CDDCDDDCC1D78C5DEED9DCBFDFDEEF4D" },
                    # .26..7..889562..73.74.8....457193862983246517612578..42.9.1.78.5487.9...7.18.2.4. from sudoku.sourceforge.net
                )

def grid_index(i):
    return (i % nelements) / 3 + ((i / (nelements * 3) * 3))

def link(cell, group):
    cell.AddGroup(group)
    group.AddCell(cell)

class cell:
    def __init__(self, index):
        self._values = list(elements)
        self._groups = []
        self._index = index
        self._done = False
        
    def __str__(self):
        """ Returns a string of the number, if the number is known,
        or an encoded digit signifying how many possibilities this cell has."""
        if len(self._values) > 1:
            return chr(ord("A") + len(self._values) - 1)
        return str(self._values[0])

    def Value(self):
        if len(self._values) > 1:
            return 0
        return self._values[0]

    def Count(self):
        return len(self._values)
    
    def Set(self, value):
        self._values = [value,]
        self._done = True
        if len(self._values) is 1 and value is not self._values[0]:
            raise "Cell[" + str(self._index) + "] being set to " + str(value) + " from " + str(self._values[0])
        try:
            for i in self._groups:
                i.Advise(self, value)
        except:
            pass

    def Reset(self):
        self._values = list(elements)
        self._done = False
        
    def RemoveValue(self, value):
        try:
            self._values.remove(value)
        except ValueError:
            pass
        if len(self._values) is 1:
            self.Set(self._values[0])

    def AddGroup(self, thegroup):
        if thegroup not in self._groups:
            self._groups.append(thegroup)
        else:
            raise "duplicate addition of group to cell."

class group:
    """grid, row, or column.  All the same..."""
    def __init__(self):
        self._cells = []
        self._analyse = False

    def AddCell(self, thecell):
        if thecell not in self._cells:
            self._cells.append(thecell)
        else:
            raise "duplicate addition of cell to group."
        
    def __str__(self):
        return self.Get()

    def FindUniqueValues(self):
        did_set = False
        s = [Set(c._values) for c in self._cells]
        const_s = copy.deepcopy(s)
        for i in range(nelements):
            for j in range(nelements):
                if i is not j:
                    s[i] -= const_s[j]
            if len(self._cells[i]._values) > 1:
                if len(s[i]) is 1:
#                    print "FindUniqueValues setting cell[" + str(self._cells[i]._index % 9 + 1) + "][" + str(self._cells[i]._index / 9 + 1) + "] (" + str(self._cells[i]._index) + ")"
                    self._cells[i].Set(s[i].pop())
                    did_set = True
        return did_set        
    
    def Get(self, colDelimeter = " "):
        return colDelimeter.join([str(x) for x in self._cells])
    
    def Advise(self, thecell, value):
        if self._analyse:
            for i in self._cells:
                if i._done is False and i is not thecell:
                     i.RemoveValue(value)

    def Check(self):
        if self._analyse is False:
            return
        for i in range(nelements - 1):
            value = self._cells[i].Value()
            if value:
                for j in range(i + 1, nelements):
                    if value in self._cells[j]._values:
                        raise Exception, "Bad Board : cell[" + str((self._cells[i]._index % nelements) + 1) + "," + str((self._cells[i]._index / nelements) + 1) + "] is " + str(value) \
                            + " and cell[" + str((self._cells[j]._index % nelements) + 1) + "," + str((self._cells[j]._index / nelements) + 1) + "] thinks it could be " + str(value) + " too."

class board:
    """The is the primary object of the file."""
    def __init__(self, starting_state=""):
        self._cells = []
        self._cols = []
        self._rows = []
        self._grids = []
        for i in range(nelements * nelements):
            self._cells.append(cell(i))
        for i in range(nelements):
            self._cols.append(group())
            self._rows.append(group())
            self._grids.append(group())
            for j in range(nelements):
                link(self._cells[i + j * nelements], self._cols[i])
                link(self._cells[j + i * nelements], self._rows[i])
        for i in range(nelements * nelements):
            link(self._cells[i], self._grids[grid_index(i)])
        if starting_state:
            self.SetBoard(values)
    
    def __eq__(self, other):
        for i in range(len(rows)):
            if self._rows[i] != other._rows[i]:
                return False
        return True
    def __ne__(self, other):
        return not(self == other)

    def Reset(self):
        """ Resets each cell to not having been assigned a value. """
        for i in range(nelements * nelements):
            self._cells[i].Reset()

    def Analyse(self, analyse):
        for i in range(len(self._cols)):
            self._cols[i]._analyse = analyse
            self._rows[i]._analyse = analyse
            self._grids[i]._analyse = analyse

    def Solve(self):
        if self._cols[0]._analyse is False:
            raise Exception, "Analysis must be turned on before Solving."
        did_set = False
        for c in self._cells:
            if len(c._values) > 1:
                for col in self._cols:
                    did_set |= col.FindUniqueValues()
                for row in self._rows:
                    did_set |= row.FindUniqueValues()
                for grid in self._grids:
                    did_set |= grid.FindUniqueValues()
                break
        return did_set
            
    def SetBoard(self, values):
        self.Reset()
        for i in range(len(values)):
            if values[i] > "0" and values[i] <= "9":
                self._cells[i].Set(ord(values[i]) - ord("0"))

    def __str__(self):
        return self.Get()

    def Get(self, rowDelimeter = "\n", colDelimeter = " "):
        return rowDelimeter.join([row.Get(colDelimeter) for row in self._rows])

    def GetCell(self, index):
        return str(self._cells[index])

    def SetCell(self, index, value):
        self._cells[index].Set(value)

    def Check(self):
        for i in self._rows:
            i.Check()
        for i in self._cols:
            i.Check()
        for i in self._grids:
            i.Check()
   

def TestGridIndex():
    print
    for i in range(9):
        print " ".join([str(grid_index(i * 9 + j)).rjust(2) for j in range(9)])
    
if __name__ == '__main__':
    import unittest
    class TestCase(unittest.TestCase):
        def test_reduce_boards(self):
            for s in sample_boards:
                b = board()
                b.Analyse(True)
                b.SetBoard(s["board"])
                self.assertEqual(s["scanned"], b.Get("",""))
        def test_solve_boards(self):
            for s in sample_boards:
                b = board()
                b.Analyse(True)
                b.SetBoard(s["board"])
                while b.Solve():
                    pass
                self.assertEqual(s["solution"], b.Get("",""))
    suite = unittest.makeSuite(TestCase, 'test')
    unittest.TextTestRunner(verbosity=2).run(suite)
##    b = board()
##    b.Analyse(True)
##    b.SetBoard(sample_boards[5]["board"])
##    print
##    print b
##    while b.Solve():
##        print
##        print "Solution Iteration"
##        print b
##    print "Final Solution"
##    print b
##    b.Check()