Artificial-Intelligence-Nanodegree/Term-I – AI Foundations/01 - Sudoku Solver/sudoku.py

assignments = []

class Sudoku():
    """Initializing and solving a classic/diagnol Sudoku.

    ATTRIBUTES:
        grid        : row-wise string representation of Sudoku
        row         : string 'ABCDEFGHI'
        cols        : string '123456789'
        boxes       : list of all squares
        unit_list   : list of all units
        peers       : dictionary of peers for each box
        values      : dictionary of box:digits
    """

    def __init__(self, grid, partial=False, diag=False,rows='ABCDEFGHI', cols='123456789'):
        """
            Args:
            - grid      : 81-char string to be solved if 'partial = False'
                          else intermediate solution as a dict of box:values
            - partial   : init with string or partial solution
            - diag      : boolean - diagonal Sudoku = True

            Returns:
                All class attributes initialized
        """
        self.grid = grid
        self.rows = rows
        self.cols = cols
        self.grid_init(partial, diag)

    def cross(self, A, B):
        """
        Cross product of elements in a and b
        """
        return [a+b for a in A for b in B]

    def assign_value(self, box, value):
        """Update the values dictionary.
        Assigns a value to a given box. If it updates the board, records it.
        """
        self.values[box] = value
        if len(value) == 1:
            assignments.append(self.values.copy())

    def grid_init(self, partial, diag):
        """Setup the grid and initialize difference parameters.
        i.e. Boxes, Values, Peers.
        """
        self.boxes = self.cross(self.rows,self.cols)

        if partial:
            self.values = self.grid.copy()
        else:
            self.values = {}
            for box,char in zip(self.boxes,self.grid):
                if char == '.':
                    self.values[box] = self.cols
                else:
                    self.values[box] = char

        rowunits = [self.cross(r,self.cols) for r in self.rows]
        colunits = [self.cross(self.rows,c) for c in self.cols]
        squareunits = [self.cross(rs, cs) for rs in ['ABC','DEF','GHI'] for cs in ['123','456','789']]

        self.unitlist = rowunits + colunits + squareunits
        if diag:
            self.unitlist += [[r+c for r,c in zip(self.rows,self.cols)],
                              [r+c for r,c in zip(self.rows,self.cols[::-1])]]

        units = {box:[u for u in self.unitlist if box in u] for box in self.boxes}
        self.peers = {box:set(sum(units[box],[]))-set([box]) for box in self.boxes}

    def display(self):
        """Display the values as a 2-D grid.
        Args:
            values(dict): The sudoku in dictionary form
        """
        width = 1+max(len(self.values[s]) for s in self.boxes)
        line = '+'.join(['-'*(width*3)]*3)
        for r in self.rows:
            print(''.join(self.values[r+c].center(width)+('|' if c in '36' else '')
                      for c in self.cols))
            if r in 'CF': print(line)
        print('\n')

    def solved_values(self):
        return [box for box in self.boxes if len(self.values[box]) == 1]

    def eliminate(self):
        """Eliminate values from peers of each box with a single value.

        Go through all the boxes, and whenever there is a box with a single
        value, eliminate this value from the set of values of all its peers.

        Args:
            values: Sudoku in dictionary form
        Returns:
            Resulting Sudoku in dictionary form after eliminating values
        """
        solved_values_boxes = self.solved_values()
        for box in solved_values_boxes:
            digit = self.values[box]
            for peer in self.peers[box]:
                value = self.values[peer]
                value = value.replace(digit,'')
                self.assign_value(peer, value)

    def only_choice(self):
        """Finalize all values that are the only choice for a unit.

        Go through all the units, and whenever there is a unit with a value
        that only fits in one box, assign the value to this box.

        Input: Sudoku in dictionary form.
        Output: Resulting Sudoku in dictionary form after filling in only
        choices.
        """
        for unit in self.unitlist:
            for digit in self.cols:
                boxes_containing_digit =[box for box in unit if digit in self.values[box]]
                if len(boxes_containing_digit) == 1:
                    self.assign_value(boxes_containing_digit[0], digit)

    #Naked-Twins Stragtegy
    def find_naked_twins(self):
        twins = [[a for a in u
                        for b in u
                            if (a != b) and (len(self.values[a]) == 2)
                                        and (self.values[a] == self.values[b])
                 ]
                 for i,u in enumerate(self.unitlist)
                ]
        return twins

    def eliminate_naked_twins(self, twins):
        for i, twin in enumerate(twins):
            if twin:
                for box in self.unitlist[i]:
                    if box not in twin:
                        for digit in self.values[twin[0]]:
                            value = self.values[box]
                            if len(value) > 1 :
                                value = value.replace(digit,'')
                                self.assign_value(box, value)

    def naked_twins(self):
        """Eliminate values using the naked twins strategy.
        Args:
            values(dict): a dictionary of the form {'box_name': '123456789', ...}

        Returns:
            the values dictionary with the naked twins eliminated from peers.
        """
        #Find all instances of naked twins
        twins = self.find_naked_twins()
        #Eliminate the naked twins as possibilities for their units
        self.eliminate_naked_twins(twins)

    def reduce_puzzle(self):
        """Iterate eliminate() and only_choice().
        If at some point, there is a box with no available values, return False.

        If the sudoku is solved, return the sudoku.
        If after an iteration of both functions, the sudoku remains the same,
        return the sudoku.

        Input: A sudoku in dictionary form.
        Output: The resulting sudoku in dictionary form.
        """
        stalled = False
        while not stalled:
            solved_values_before = self.solved_values()
            self.eliminate()
            self.only_choice()
            solved_values_after = self.solved_values()

            stalled = solved_values_before == solved_values_after

            if len([box for box in self.boxes if len( self.values[box]) == 0]):
                # if it is still solvable run naked_twins or not
                self.naked_twins()
                return True
        return False

    def search(self):
        """Using depth-first search and propagation,
        create a search tree and solve the sudoku.
        """
        # Reduce the puzzle
        failed = self.reduce_puzzle()
        if failed :
            return False #Tree-leaf: not a solution
        if all(len(self.values[box]) == 1 for box in self.boxes):
            return True #Solved

        # Choose box with min possibilities
        n, box = min((len(self.values[box]),box) for box in self.boxes if len(self.values[box]) > 1)

        # Recursion to solve each one of the resulting sudokus,
        # and if one returns a value (not False), return that answer!
        for digit in self.values[box]:
            tmp = self.values.copy() # copy of the values in case of failure = 'attempt ===False'
            self.values[box] = digit
            attempt = self.search()
            if attempt:
                return attempt
            else:
                self.values = tmp