# Section 1 - Some Useful Definitions
let = 'ABCDEFGHI'
num = (1, 2, 3, 4, 5, 6, 7, 8, 9)

cells = []
for a in 'ABCDEFGHI':
    for b in '123456789':
        cells += [a+b]


cells_def  = {}
cells_poss = {}

for x in cells:
    cells_def[x]  = 0           # (The initial value of each cell is zero, and
    cells_poss[x] = list(num)   #  the initial possibility is anything in num,
                                #  but we need to be able to change it.)

# Section 2 - The Functions

# First, getters of the values of the locales to check against:
def get_row(cell):
    'Gets the row surrounding the cell'
    my_row = []
    for letter in let:                          # Iterate through the letters,
        my_row += [ cells_def[letter+cell[1]] ] # adding the value of each cell
    return my_row                               # in the row.

def get_col(cell):
    'Gets the column surrounding the cell'
    my_col = []                                 # ~Ditto
    for number in num:
        my_col += [ cells_def[cell[0]+`number`] ] # `x` => string of x
    return my_col

def get_box(cell):
    'Gets the box surrounding cell'
    # Just remember that cell[0] is the column and
    # cell[1] the row!
    
    my_box = []

    for poss_cols in ['ABC','DEF','GHI']:
        if cell[0] in poss_cols:
            box_cols = poss_cols
            break

    for poss_rows in ['123','456','789']:
        if cell[1] in poss_rows:
            box_rows = poss_rows
            break

    for col in box_cols:
        for row in box_rows:
            my_box += [ cells_def[col+row] ]

    return my_box

def get_cells(cell,kind):
    'Gets the locale of the surrounding cell'
    # In essence the same as get_row et al.,
    # but gives the cells instead of the values.

    if kind in ['row','Row']:
            the_row = []
            for col in let:
                    the_row += [col+cell[1]]
            return the_row
    elif kind in ['col','Col']:
            the_col = []
            for row in num:
                    the_col += [cell[0]+`row`]
            return the_col
    elif kind in ['box','Box']:
            the_box = []
            for pcol in ['ABC','DEF','GHI']:
                    if cell[0] in pcol:
                            box_cols = pcol
                            break
            for prow in ['123','456','789']:
                    if cell[1] in prow:
                            box_rows = prow
                            break
            for row in box_rows:
                    for col in box_cols:
                            the_box += [col+row]
            return the_box
    else:
            return 'Unsupported kind '+kind+'.'

def get_cells_poss(cell, kind):
    'Gets the locale of possibilities surrounding the cell'
    # This is what get_row, get_col and get_box
    # could be reduced to.

    posses = []
    for j in get_cells(cell,kind):
        posses += [cells_poss[j]]
    return posses

# Now the functions to print out the grid, and the function to
# check if the puzzle is done:
def print_grid():
    'Prints the grid in its current state of completion'
    # 's'*2 => 'ss'

    print '+'+'-'*37+'+'
    for x in range(9):
        if x in [3,6]:
            print '|'+'='*37+'|'
        elif x != 0:
            print ('|---'*3+'|')*2+'|'+'---|'*3
        print ( '| %i | %i | %i || %i | %i | %i || %i | %i | %i |' % tuple(get_row('A'+`x+1`)) ).replace('0',' ')
    print '+'+'-'*37+'+'

def print_grid_debug():
    'Prints the grid with coordinates.'
    # Basically the same as print_grid(), but with
    # cell coordinates as well.
    print ' '*4+'A'+' '*3+'B'+' '*3+'C'+' '*4+'D'+' '*3+'E'+' '*3+'F'+' '*4+'G'+' '*3+'H'+' '*3+'I'
    print ' '*2+'+'+'-'*37+'+'
    for x in range(9):
            if x in [3,6]:
                    print '  |'+'='*37+'|'
            elif x != 0:
                    print ' '*2+('|---'*3+'|')*2+'|'+'---|'*3
            print `x+1`+( ' | %i | %i | %i || %i | %i | %i || %i | %i | %i |' % tuple(get_row('A'+`x+1`)) ).replace('0',' ')
    print ' '*2+'+'+'-'*37+'+'

def is_finished():
    'Checks whether the grid is complete:'
    entire = cells_def.values()

    if entire.count(0) == 0 and sum(entire) == 405: # A rudimentary value check
        return True

    return False

# Et les pieces de resistance: the possibility shrinker and the single placer!
def poss_shrinker(cell):
    'Evaluates  and shrinks the cell\'s possible values'

    # This basically checks the cell's current
    # possible values against all locale values,
    # removing those that match.

    me = cell

    my_poss = cells_poss[me]
    my_row  = get_row(me)
    my_col  = get_col(me)
    my_box  = get_box(me)

    while 0 in my_row: my_row.remove(0)
    while 0 in my_col: my_col.remove(0)
    while 0 in my_box: my_box.remove(0)

    if cells_def[me] != 0:
            cells_poss[me] = [ cells_def[me] ]
    else:
            for loc in [my_row,my_col,my_box]:
                    for x in loc:
                            if x in my_poss:
                                    my_poss.remove(x)
                    cells_poss[me] = my_poss

def single_placer(cell):
    'Finds places in locales where only one value can go'

    # This is a complicated one -
    # 'You are not expected to understand this...'
    # Using the 'zip' function, we get a list of
    # cells mapped to possible values for each of
    # the cell's locales.

    # We then go through for each digit, and check
    # if it appears more than once. If not, the only
    # cell in which the digit is a possibility is
    # noted, along with the digit. This list of
    # definite values is then returned.

    row = zip(get_cells(cell,'row'),get_cells_poss(cell,'row'))
    col = zip(get_cells(cell,'col'),get_cells_poss(cell,'col'))
    box = zip(get_cells(cell,'box'),get_cells_poss(cell,'box'))

    defs = []
    for loc in [row,col,box]:
            for digit in num:
                    occs = []
                    for z in loc:
                            if digit in z[1]:
                                    occs += [z[0]]
                    if len(occs) == 1:
                            defs += [(occs[0],digit)]

    for x in defs:
            if cells_def[x[0]] != 0:
                    while x in defs: defs.remove(x)
    return defs

# NEW to v2.0 - find_pairs and find_triples.
def find_pairs(cell):
    'Finds \'naked pairs\', and updates the possibilities accordingly.'
    pairs = []
    for loc in ['row','col','box']:
        truc = get_cells(cell,loc)
        for a in truc:
            for b in truc:
                if not a == b:
                    if cells_poss[a] == cells_poss[b] and len(cells_poss[a]) == 2:
                        pairs += [(a,b,loc,cells_poss[a])]

    if len(pairs) > 0:
        for p in pairs:
            cel = get_cells(p[0],p[2])
            cel.remove(p[0])
            cel.remove(p[1])

            for j in cel:
                if cells_def[j] == 0 and len(cells_poss[j]) > 1:
                    if p[3][0] in cells_poss[j]: cells_poss[j].remove(p[3][0])
                    if p[3][1] in cells_poss[j]: cells_poss[j].remove(p[3][1])

# For about a week a bug in these functions meant that they would erase
# possibile values from already found cells! This meant that the solver
# kept reducing a cell's _poss to [], causing it to crash.

# (The line 'and len(cells_poss[j]) > 1:' corrects this)

def find_triples(cell):
    'Finds... \'naked triples\', I suppose.'
    triples = []
    for loc in ['row','box','col']:
        truc = get_cells(cell,loc)
        for c in truc:
            for d in truc:
                for e in truc:
                    if not c in [d,e] and not d == e:
                        if cells_poss[c] == cells_poss[d] == cells_poss[e] and len(cells_poss[c]) == 3:
                            triples += [(c,d,e,loc,cells_poss[c])]

    if len(triples) > 0:
        for t in triples:
            cel = get_cells(t[0],t[3])
            cel.remove(t[0])
            cel.remove(t[1])
            cel.remove(t[2])

            for k in cel:
                if cells_def[k] == 0 and len(cells_poss[k]) > 1:
                    for i in t[4]:
                        if i in cells_poss[k]: cells_poss[k].remove(i)
                            
while True:
    # Section 3 - Getting the values
    print 'Welcome to Chris\' sudoku solver!'
    print
    print 'The puzzle is entered row by row.'
    print 'You type each number as it appears in the grid, putting blanks as .\'s.'
    print 'For example:'
    print '\t..3 4.. 7.2'
    print 'is'
    print '\t'+('|---'*3+'|')*2+'|'+'---|'*3
    print '\t|   |   | 3 || 4 |   |   || 7 |   | 2 |'
    print '\t'+('|---'*3+'|')*2+'|'+'---|'*3
    print
    print 'If the rest of the row is blank, you can ignore it. So'
    print '\t3.2 1.6'
    print 'is the same as'
    print '\t3.2 1.6 ...'
    print ', and a blank input is'
    print '\t... ... ...'
    print '(you can also represent \'...\' with \'%\')'
    print
    print

    ords = ['First','Second','Third','Fourth','Fifth','Sixth','Seventh','Eighth','Last']
    grid = [[]]*9
    errs = []
    for q in range(9):
        if q % 3 == 0: print            # On every third input, insert a line

        sp  = (len('Seventh row:') - len(ords[q]+' row:')) + 3
        row = raw_input(ords[q]+' row:'+' '*sp)

        for f in row:
                if not f in '%.0123456789':
                        row = row.replace(f,'')

        row = row.replace('%','...')

        if len(row) < 9: # Fill lines with 0s
                row += '.' * (9 - len(row))

        row = row.replace('.','0')
        row = row.replace(' ','')

        if len(row) > 9:
                errs += [q]

        row = list(row)

        for x in range(9):
                row[x] = int(row[x])

        grid[q] = list(row)

    while len(errs) > 0:
        print 'There were some errors in these rows:'
        for r in errs:
                if q % 3 == 0: print
                
                sp  = (len('Seventh row:') - len(ords[q]+' row:')) + 3
                row = raw_input(ords[q]+' row:'+' '*sp)

                for f in row:
                        if not f in '%.0123456789':
                                row = row.replace(f,'')

                row = row.replace('%','...')

                if len(row) < 9:
                    row += '.' * (9 - len(row))

                row = row.replace('.','0')
                row = row.replace(' ','')

                if len(row) < 9:
                        errs += [row]

                row = list(row)

                for x in range(9):
                        row[x] = int(row[x])


                grid[q] = list(row)
                errs.remove(r)

    for a,b in enumerate('ABCDEFGHI'):      # 'enumerate' is like a straight list,
        for c,d in enumerate('123456789'):  # but sets the first vaariable to the
                cells_def[b+d] = grid[c][a] # index and the second as the item.

    # Section 4 - Solving the puzzle
    print '\nThe original grid:'

    print_grid()

    from time import time, sleep
    steps = 0
    failed = False

    start = time()
    while not is_finished() and not failed:
        steps += 1

        # First, we update the possible values of each cell...
        for x in cells:
            poss_shrinker(x)
            if len(cells_poss[x]) == 1 and cells_def[x] == 0:   # ... and, if a blank cell has only
                cells_def[x] = cells_poss[x][0]                 # one possibility, we assign it.
            elif len(cells_poss[x]) == 0:
                print '### ERROR: There are no possible values for cell '+x+'!' # And, if there is an error,
                failed = True                                                   # quit.

        # Then we check every row, column and box for unique possibilities.
        for y in ['A1','B4','C7','D2','E5','F8','G3','H6','I9']:     # (these cells cover every row, column and box)
            for z in single_placer(y):
                cells_def[ z[0] ] = z[1]
            find_pairs(y)
            find_triples(y)

        if steps == 500:
            failed = True
            print '\n### ERROR: Unable to solve'

    end = time()

    if failed:
        print
        print_grid_debug()
    else:
        print '\nAnd, solved:'
        print_grid()

        if steps == 1: name = 'step'
        else: name = 'steps'

        if end-start == 1.00: name2 = 'second'
        else: name2 = 'seconds'

        if steps != 0:
            print '(took '+`steps`+' '+name+' in '+( '%.3f ' % (end-start,) )+name2+')'


    q = raw_input('\nSolve another? (y/n) ')
    if q in ['n','N']:
        print 'Bye!'
        sleep(1)
        break
    else:
        print
        for x in cells:
            cells_def[x] = 0
            cells_poss[x] = list(num)