'''
An example method of solving Sudoku puzzles on a 9x9 grid. Implements brute force search -- conceptually the simplest method but intractable for most problems.

John Quinn <jquinn@cit.mak.ac.ug>
'''
import copy
import time

def check_constraint(c,Assg):
    '''
    Is the given constraint satisfied by the given variable assignment.
    Here we expect the constraint just to be a list of variables, and to
    satisfy the constraint each non-null variable is different.
    '''
    assignments = []
    for v in c:
        this_assignment = Assg[v]
        if not this_assignment == None:
            assignments.append(Assg[v][0])

    # the constraint is satisfied if there are no duplicates
    valid = (len(set(assignments))==len(assignments))
    
    return valid

def brute_force_search(V,Dom,Assg,C):
    '''
    Enumerate all the possible assignments.
    '''
    try:
        # find the first unassigned variable
        v = Assg.index(None)

        # loop through the values in its domain
        for d in Dom[v]:
            AssgPrime = copy.deepcopy(Assg)
            AssgPrime[v] = [d]
            sol = brute_force_search(V,Dom,AssgPrime,C)
            if not sol == None:
                return sol

        # if we didn't find any value, return null
        return None

    except ValueError:
        # if everything has been assigned, check all the constraints
        valid = True
        for c in C:
            valid = valid and check_constraint(c,Assg)
        if valid:
            return Assg
        else:
            return None

def solver(puzzle):
    '''
    Given a number grid (list of lists) with missing values, find a valid
    solution.
    '''
    n = len(puzzle)

    # the list of variables
    V = range(n**2)

    # Domains for all the unallocated variables
    Dom = []
    # Current assignment to variables
    Assg = []
    for y in range(n):
        for x in range(n):
            if puzzle[y][x] == None:
                Dom.append(range(1,n+1))
                Assg.append(None)
            else:
                Dom.append([puzzle[y][x]])
                Assg.append([puzzle[y][x]])


    # there are n column/row/block constraints.
    C = []

    for i in range(n):
        # all the column constraints
        C.append(range(i*n,(i+1)*n))

        # all the row constraints
        C.append(range(i,i+(n-1)*n+1,n))

    # all the block constraints (hard coded for 9x9 grid for now)
    C.append([0,1,2,9,10,11,18,19,20])
    C.append([3,4,5,12,13,14,21,22,23])
    C.append([6,7,8,15,16,17,24,25,26])
    C.append([27,28,29,36,37,38,45,46,47])
    C.append([30,31,32,39,40,41,48,49,50])
    C.append([33,34,35,42,43,44,51,52,53])
    C.append([54,55,56,63,64,65,72,73,74])
    C.append([57,58,59,66,67,68,75,76,77])
    C.append([60,61,62,69,70,71,78,79,80])

    starttime = time.clock()

    solution = brute_force_search(V,Dom,Assg,C)

    elapsed = time.clock() - starttime + 0.0001

    return solution, elapsed

if __name__=='__main__':

    puzzle1 = [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,9,8,None,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle2 = [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,9,5,None,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,None,8,5,3,7,9,1],
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle3 = [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,None,5,3,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,None,1],
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,None,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle4 = [[5,3,4,6,7,8,9,1,2],
              [6,7,None,1,9,5,3,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,None,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,None,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,None,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle5 = [[5,3,None,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,None,8,3,None,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,3,9,2,None,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,None,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle6 = [[5,3,None,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,None,8,3,None,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,3,9,2,None,8,5,6],
              [9,None,1,5,3,7,2,8,4],
              [2,8,7,4,None,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]

    puzzle7 = [[5,3,None,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,None,8,3,None,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,3,9,2,None,8,5,6],
              [9,None,1,5,3,7,2,8,4],
              [2,8,7,4,None,9,6,None,5],
              [3,4,5,2,8,6,1,7,9]]


    '''
    Solution...
             [[5,3,4,6,7,8,9,1,2],
              [6,7,2,1,9,5,3,4,8],
              [1,9,8,3,4,2,5,6,7],
              [8,5,9,7,6,1,4,2,3],
              [4,2,6,8,5,3,7,9,1],
              [7,1,3,9,2,4,8,5,6],
              [9,6,1,5,3,7,2,8,4],
              [2,8,7,4,1,9,6,3,5],
              [3,4,5,2,8,6,1,7,9]]
    '''

    sol,elapsed = solver(puzzle3)
    if not sol == None:
        print 'Solution found:'
        for i in range(9):
            print(sol[i*9:(i+1)*9])
    else:
        print 'No solution found.'
    print 'Elapsed time: %.4f seconds.' % elapsed