Btukfyl

Here is my sudoku solver in python. It uses simple backtracking algorithm to solve the puzzle.
For simplicity no input validations or fancy output is done. It's the bare minimum code which solves the problem.

Algorithm

1. Find all legal values of a given cell


2. For each legal value, Go recursively and try to solve the grid

Solution

It takes 9X9 grid partially filled with numbers. A cell with value 0 indicates that it is not filled.

Code

def findNextCellToFill(grid, i, j):

        for x in range(i,9):

                for y in range(j,9):

                        if grid[x][y] == 0:

                                return x,y

        for x in range(0,9):

                for y in range(0,9):

                        if grid[x][y] == 0:

                                return x,y

        return -1,-1



def isValid(grid, i, j, e):

        rowOk = all([e != grid[i][x] for x in range(9)])

        if rowOk:

                columnOk = all([e != grid[x][j] for x in range(9)])

                if columnOk:

                        # finding the top left x,y co-ordinates of the section containing the i,j cell

                        secTopX, secTopY = 3 *(i//3), 3 *(j//3) #floored quotient should be used here. 

                        for x in range(secTopX, secTopX+3):

                                for y in range(secTopY, secTopY+3):

                                        if grid[x][y] == e:

                                                return False

                        return True

        return False



def solveSudoku(grid, i=0, j=0):

        i,j = findNextCellToFill(grid, i, j)

        if i == -1:

                return True

        for e in range(1,10):

                if isValid(grid,i,j,e):

                        grid[i][j] = e

                        if solveSudoku(grid, i, j):

                                return True

                        # Undo the current cell for backtracking

                        grid[i][j] = 0

        return False

Testing the code

>>> input = [[5,1,7,6,0,0,0,3,4],[2,8,9,0,0,4,0,0,0],[3,4,6,2,0,5,0,9,0],[6,0,2,0,0,0,0,1,0],[0,3,8,0,0,6,0,4,7],[0,0,0,0,0,0,0,0,0],[0,9,0,0,0,0,0,7,8],[7,0,3,4,0,0,5,6,0],[0,0,0,0,0,0,0,0,0]]

>>> solveSudoku(input)

True

>>> input

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

The above one is very basic backtracking algorithm which is explained at many places. But the most interesting and natural of the sudoku solving strategies I came across is this one from here

Here is a much faster solution based on hari's answer. The basic difference is that we keep a set of possible values for cells that don't have a value assigned. So when we try a new value, we only try valid values and we also propagate what this choice means for the rest of the sudoku. In the propagation step, we remove from the set of valid values for each cell the values that already appear in the row, column, or the same block. If only one number is left in the set, we know that the position (cell) has to have that value.

This method is known as forward checking and look ahead (http://ktiml.mff.cuni.cz/~bartak/constraints/propagation.html).

The implementation below needs one iteration (calls of solve) while hari's implementation needs 487. Of course my code is a bit longer. The propagate method is also not optimal.

import sys

from copy import deepcopy



def output(a):

    sys.stdout.write(str(a))



N = 9



field = [[5,1,7,6,0,0,0,3,4],

         [2,8,9,0,0,4,0,0,0],

         [3,4,6,2,0,5,0,9,0],

         [6,0,2,0,0,0,0,1,0],

         [0,3,8,0,0,6,0,4,7],

         [0,0,0,0,0,0,0,0,0],

         [0,9,0,0,0,0,0,7,8],

         [7,0,3,4,0,0,5,6,0],

         [0,0,0,0,0,0,0,0,0]]



def print_field(field):

    if not field:

        output("No solution")

        return

    for i in range(N):

        for j in range(N):

            cell = field[i][j]

            if cell == 0 or isinstance(cell, set):

                output('.')

            else:

                output(cell)

            if (j + 1) % 3 == 0 and j < 8:

                output(' |')



            if j != 8:

                output(' ')

        output('n')

        if (i + 1) % 3 == 0 and i < 8:

            output("- - - + - - - + - - -n")



def read(field):

    """ Read field into state (replace 0 with set of possible values) """



    state = deepcopy(field)

    for i in range(N):

        for j in range(N):

            cell = state[i][j]

            if cell == 0:

                state[i][j] = set(range(1,10))



    return state



state = read(field)





def done(state):

    """ Are we done? """



    for row in state:

        for cell in row:

            if isinstance(cell, set):

                return False

    return True





def propagate_step(state):

    """

    Propagate one step.



    @return:  A two-tuple that says whether the configuration

              is solvable and whether the propagation changed

              the state.

    """



            new_units = False



    # propagate row rule

    for i in range(N):

        row = state[i]

        values = set([x for x in row if not isinstance(x, set)])

        for j in range(N):

            if isinstance(state[i][j], set):

                state[i][j] -= values

                if len(state[i][j]) == 1:

                    val = state[i][j].pop()

                    state[i][j] = val

                    values.add(val)

                    new_units = True

                elif len(state[i][j]) == 0:

                    return False, None



    # propagate column rule

    for j in range(N):

        column = [state[x][j] for x in range(N)]

        values = set([x for x in column if not isinstance(x, set)])

        for i in range(N):

            if isinstance(state[i][j], set):

                state[i][j] -= values

                if len(state[i][j]) == 1:

                    val = state[i][j].pop()

                    state[i][j] = val

                    values.add(val)

                    new_units = True

                elif len(state[i][j]) == 0:

                    return False, None



    # propagate cell rule

    for x in range(3):

        for y in range(3):

            values = set()

            for i in range(3 * x, 3 * x + 3):

                for j in range(3 * y, 3 * y + 3):

                    cell = state[i][j]

                    if not isinstance(cell, set):

                        values.add(cell)

            for i in range(3 * x, 3 * x + 3):

                for j in range(3 * y, 3 * y + 3):

                    if isinstance(state[i][j], set):

                        state[i][j] -= values

                        if len(state[i][j]) == 1:

                            val = state[i][j].pop()

                            state[i][j] = val

                            values.add(val)

                            new_units = True

                        elif len(state[i][j]) == 0:

                            return False, None



    return True, new_units



def propagate(state):

    """ Propagate until we reach a fixpoint """

    while True:

        solvable, new_unit = propagate_step(state)

        if not solvable:

            return False

        if not new_unit:

            return True





def solve(state):

    """ Solve sudoku """



    solvable = propagate(state)



    if not solvable:

        return None



    if done(state):

        return state



    for i in range(N):

        for j in range(N):

            cell = state[i][j]

            if isinstance(cell, set):

                for value in cell:

                    new_state = deepcopy(state)

                    new_state[i][j] = value

                    solved = solve(new_state)

                    if solved is not None:

                        return solved

                return None



print_field(solve(state))

I wrote a simple program that solved the easy ones. It took its input from a file which was just a matrix with spaces and numbers. The datastructure to solve it was just a 9 by 9 matrix of a bit mask. The bit mask would specify which numbers were still possible on a certain position. Filling in the numbers from the file would reduce the numbers in all rows/columns next to each known location. When that is done you keep iterating over the matrix and reducing possible numbers. If each location has only one option left you're done. But there are some sudokus that need more work. For these ones you can just use brute force: try all remaining possible combinations until you find one that works.

I also wrote a Sudoku solver in Python. It is a backtracking algorithm too, but I wanted to share my implementation as well.

Backtracking can be fast enough given that it is moving within the constraints and is choosing cells wisely. You might also want to check out my answer in this thread about optimizing the algorithm. But here I will focus on the algorithm and code itself.

The gist of the algorithm is to start iterating the grid and making decisions what to do - populate a cell, or try another digit for the same cell, or blank out a cell and move back to the previous cell, etc. It's important to note that there is no deterministic way to know how many steps or iterations you will need to solve the puzzle. Therefore, you really have two options - to use a while loop or to use recursion. Both of them can continue iterating until a solution is found or until a lack of solution is proven. The advantage of the recursion is that it is capable of branching out and generally supports more complex logics and algorithms, but the disadvantage is that it is more difficult to implement and often tricky to debug. For my implementation of the backtracking I have used a while loop because no branching is needed, the algorithm searches in a single-threaded linear fashion.

The logic goes like this:

While True: (main iterations)

1. If all blank cells have been iterated and the last blank cell iterated doesn't have any remaining digits to be tried - stop here because there is no solution.


2. If there are no blank cells validate the grid. If the grid is valid stop here and return the solution.


3. If there are blank cells choose the next cell. If that cell has at least on possible digit, assign it and continue to the next main iteration.


4. If there is at least one remaining choice for the current cell and there are no blank cells or all blank cells have been iterated, assign the remaining choice and continue to the next main iteration.


5. If none of the above is true, then it is time to backtrack. Blank out the current cell and enter the below loop.

While True: (backtrack iterations)

1. If there are no more cells to backtrack to - stop here because there
   is no solution.


2. Select the previous cell according to the backtracking history.


3. If the cell doesn't have any choices left, blank out the cell and
   continue to the next backtrack iteration.


4. Assign the next available digit to the current cell, break out from
   backtracking and return to the main iterations.

Some features of the algorithm:

• it keeps a record of the visited cells in the same order so that it can backtrack at any time




• it keeps a record of choices for each cell so that it doesn't try the same digit for the same cell twice




• the available choices for a cell are always within the Sudoku constraints (row, column and 3x3 quadrant)




• this particular implementation has a few different methods of choosing the next cell and the next digit depending on input parameters (more info in the optimization thread)




• if given a blank grid, then it will generate a valid Sudoku puzzle (use with optimization parameter "C" in order to generate random grid every time)




• if given a solved grid it will recognize it and print a message

The full code is:

import random, math, time



class Sudoku:

    def __init__( self, _g= ):

        self._input_grid =  # store a copy of the original input grid for later use

        self.grid =  # this is the main grid that will be iterated

        for i in _g: # copy the nested lists by value, otherwise Python keeps the reference for the nested lists

            self._input_grid.append( i[:] )

            self.grid.append( i[:] )



    self.empty_cells = set() # set of all currently empty cells (by index number from left to right, top to bottom)

    self.empty_cells_initial = set() # this will be used to compare against the current set of empty cells in order to determine if all cells have been iterated

    self.current_cell = None # used for iterating

    self.current_choice = 0 # used for iterating

    self.history =  # list of visited cells for backtracking

    self.choices = {} # dictionary of sets of currently available digits for each cell

    self.nextCellWeights = {} # a dictionary that contains weights for all cells, used when making a choice of next cell

    self.nextCellWeights_1 = lambda x: None # the first function that will be called to assign weights

    self.nextCellWeights_2 = lambda x: None # the second function that will be called to assign weights

    self.nextChoiceWeights = {} # a dictionary that contains weights for all choices, used when selecting the next choice

    self.nextChoiceWeights_1 = lambda x: None # the first function that will be called to assign weights

    self.nextChoiceWeights_2 = lambda x: None # the second function that will be called to assign weights



    self.search_space = 1 # the number of possible combinations among the empty cells only, for information purpose only

    self.iterations = 0 # number of main iterations, for information purpose only

    self.iterations_backtrack = 0 # number of backtrack iterations, for information purpose only



    self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 } # store the number of times each digit is used in order to choose the ones that are least/most used, parameter "3" and "4"

    self.centerWeights = {} # a dictionary of the distances for each cell from the center of the grid, calculated only once at the beginning



    # populate centerWeights by using Pythagorean theorem

    for id in range( 81 ):

        row = id // 9

        col = id % 9

        self.centerWeights[ id ] = int( round( 100 * math.sqrt( (row-4)**2 + (col-4)**2 ) ) )







    # for debugging purposes

    def dump( self, _custom_text, _file_object ):

        _custom_text += ", cell: {}, choice: {}, choices: {}, empty: {}, history: {}, grid: {}n".format(

            self.current_cell, self.current_choice, self.choices, self.empty_cells, self.history, self.grid )

        _file_object.write( _custom_text )



    # to be called before each solve of the grid

    def reset( self ):

        self.grid = 

        for i in self._input_grid:

            self.grid.append( i[:] )



        self.empty_cells = set()

        self.empty_cells_initial = set()

        self.current_cell = None

        self.current_choice = 0

        self.history = 

        self.choices = {}



        self.nextCellWeights = {}

        self.nextCellWeights_1 = lambda x: None

        self.nextCellWeights_2 = lambda x: None

        self.nextChoiceWeights = {}

        self.nextChoiceWeights_1 = lambda x: None

        self.nextChoiceWeights_2 = lambda x: None



        self.search_space = 1

        self.iterations = 0

        self.iterations_backtrack = 0



        self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }



    def validate( self ):

        # validate all rows

        for x in range(9):

            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }

            for y in range(9):

                digit_count[ self.grid[ x ][ y ] ] += 1

            for i in digit_count:

                if digit_count[ i ] != 1:

                    return False



        # validate all columns

        for x in range(9):

            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }

            for y in range(9):

                digit_count[ self.grid[ y ][ x ] ] += 1

            for i in digit_count:

                if digit_count[ i ] != 1:

                    return False



        # validate all 3x3 quadrants

        def validate_quadrant( _grid, from_row, to_row, from_col, to_col ):

            digit_count = { 0:1, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }

            for x in range( from_row, to_row + 1 ):

                for y in range( from_col, to_col + 1 ):

                    digit_count[ _grid[ x ][ y ] ] += 1

            for i in digit_count:

                if digit_count[ i ] != 1:

                    return False

            return True



        for x in range( 0, 7, 3 ):

            for y in range( 0, 7, 3 ):

                if not validate_quadrant( self.grid, x, x+2, y, y+2 ):

                    return False

        return True



    def setCell( self, _id, _value ):

        row = _id // 9

        col = _id % 9

        self.grid[ row ][ col ] = _value



    def getCell( self, _id ):

        row = _id // 9

        col = _id % 9

        return self.grid[ row ][ col ]



    # returns a set of IDs of all blank cells that are related to the given one, related means from the same row, column or quadrant

    def getRelatedBlankCells( self, _id ):

        result = set()

        row = _id // 9

        col = _id % 9



        for i in range( 9 ):

            if self.grid[ row ][ i ] == 0: result.add( row * 9 + i )

        for i in range( 9 ):

            if self.grid[ i ][ col ] == 0: result.add( i * 9 + col )

        for x in range( (row//3)*3, (row//3)*3 + 3 ):

            for y in range( (col//3)*3, (col//3)*3 + 3 ):

                if self.grid[ x ][ y ] == 0: result.add( x * 9 + y )



        return set( result ) # return by value



    # get the next cell to iterate

    def getNextCell( self ):

        self.nextCellWeights = {}

        for id in self.empty_cells:

            self.nextCellWeights[ id ] = 0



        self.nextCellWeights_1( 1000 ) # these two functions will always be called, but behind them will be a different weight function depending on the optimization parameters provided

        self.nextCellWeights_2( 1 )



        return min( self.nextCellWeights, key = self.nextCellWeights.get )



    def nextCellWeights_A( self, _factor ): # the first cell from left to right, from top to bottom

        for id in self.nextCellWeights:

            self.nextCellWeights[ id ] += id * _factor



    def nextCellWeights_B( self, _factor ): # the first cell from right to left, from bottom to top

        self.nextCellWeights_A( _factor * -1 )



    def nextCellWeights_C( self, _factor ): # a randomly chosen cell

        for id in self.nextCellWeights:

            self.nextCellWeights[ id ] += random.randint( 0, 999 ) * _factor



    def nextCellWeights_D( self, _factor ): # the closest cell to the center of the grid

        for id in self.nextCellWeights:

            self.nextCellWeights[ id ] += self.centerWeights[ id ] * _factor



    def nextCellWeights_E( self, _factor ): # the cell that currently has the fewest choices available

        for id in self.nextCellWeights:

            self.nextCellWeights[ id ] += len( self.getChoices( id ) ) * _factor



    def nextCellWeights_F( self, _factor ): # the cell that currently has the most choices available

        self.nextCellWeights_E( _factor * -1 )



    def nextCellWeights_G( self, _factor ): # the cell that has the fewest blank related cells

        for id in self.nextCellWeights:

            self.nextCellWeights[ id ] += len( self.getRelatedBlankCells( id ) ) * _factor



    def nextCellWeights_H( self, _factor ): # the cell that has the most blank related cells

        self.nextCellWeights_G( _factor * -1 )



    def nextCellWeights_I( self, _factor ): # the cell that is closest to all filled cells

        for id in self.nextCellWeights:

            weight = 0

            for check in range( 81 ):

                if self.getCell( check ) != 0:

                    weight += math.sqrt( ( id//9 - check//9 )**2 + ( id%9 - check%9 )**2 )



    def nextCellWeights_J( self, _factor ): # the cell that is furthest from all filled cells

        self.nextCellWeights_I( _factor * -1 )



    def nextCellWeights_K( self, _factor ): # the cell whose related blank cells have the fewest available choices

        for id in self.nextCellWeights:

            weight = 0

            for id_blank in self.getRelatedBlankCells( id ):

                weight += len( self.getChoices( id_blank ) )

            self.nextCellWeights[ id ] += weight * _factor



    def nextCellWeights_L( self, _factor ): # the cell whose related blank cells have the most available choices

        self.nextCellWeights_K( _factor * -1 )







    # for a given cell return a set of possible digits within the Sudoku restrictions

    def getChoices( self, _id ):

        available_choices = {1,2,3,4,5,6,7,8,9}

        row = _id // 9

        col = _id % 9



        # exclude digits from the same row

        for y in range( 0, 9 ):

            if self.grid[ row ][ y ] in available_choices:

                available_choices.remove( self.grid[ row ][ y ] )



        # exclude digits from the same column

        for x in range( 0, 9 ):

            if self.grid[ x ][ col ] in available_choices:

                available_choices.remove( self.grid[ x ][ col ] )



        # exclude digits from the same quadrant

        for x in range( (row//3)*3, (row//3)*3 + 3 ):

            for y in range( (col//3)*3, (col//3)*3 + 3 ):

                if self.grid[ x ][ y ] in available_choices:

                    available_choices.remove( self.grid[ x ][ y ] )



        if len( available_choices ) == 0: return set()

        else: return set( available_choices ) # return by value



    def nextChoice( self ):

        self.nextChoiceWeights = {}

        for i in self.choices[ self.current_cell ]:

            self.nextChoiceWeights[ i ] = 0



        self.nextChoiceWeights_1( 1000 )

        self.nextChoiceWeights_2( 1 )



        self.current_choice = min( self.nextChoiceWeights, key = self.nextChoiceWeights.get )

        self.setCell( self.current_cell, self.current_choice )

        self.choices[ self.current_cell ].remove( self.current_choice )



    def nextChoiceWeights_0( self, _factor ): # the lowest digit

        for i in self.nextChoiceWeights:

            self.nextChoiceWeights[ i ] += i * _factor



    def nextChoiceWeights_1( self, _factor ): # the highest digit

        self.nextChoiceWeights_0( _factor * -1 )



    def nextChoiceWeights_2( self, _factor ): # a randomly chosen digit

        for i in self.nextChoiceWeights:

            self.nextChoiceWeights[ i ] += random.randint( 0, 999 ) * _factor



    def nextChoiceWeights_3( self, _factor ): # heuristically, the least used digit across the board

        self.digit_heuristic = { 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0 }

        for id in range( 81 ):

            if self.getCell( id ) != 0: self.digit_heuristic[ self.getCell( id ) ] += 1

        for i in self.nextChoiceWeights:

            self.nextChoiceWeights[ i ] += self.digit_heuristic[ i ] * _factor



    def nextChoiceWeights_4( self, _factor ): # heuristically, the most used digit across the board

        self.nextChoiceWeights_3( _factor * -1 )



    def nextChoiceWeights_5( self, _factor ): # the digit that will cause related blank cells to have the least number of choices available

        cell_choices = {}

        for id in self.getRelatedBlankCells( self.current_cell ):

            cell_choices[ id ] = self.getChoices( id )



        for c in self.nextChoiceWeights:

            weight = 0

            for id in cell_choices:

                weight += len( cell_choices[ id ] )

                if c in cell_choices[ id ]: weight -= 1

            self.nextChoiceWeights[ c ] += weight * _factor



    def nextChoiceWeights_6( self, _factor ): # the digit that will cause related blank cells to have the most number of choices available

        self.nextChoiceWeights_5( _factor * -1 )



    def nextChoiceWeights_7( self, _factor ): # the digit that is the least common available choice among related blank cells

        cell_choices = {}

        for id in self.getRelatedBlankCells( self.current_cell ):

            cell_choices[ id ] = self.getChoices( id )



        for c in self.nextChoiceWeights:

            weight = 0

            for id in cell_choices:

                if c in cell_choices[ id ]: weight += 1

            self.nextChoiceWeights[ c ] += weight * _factor



    def nextChoiceWeights_8( self, _factor ): # the digit that is the most common available choice among related blank cells

        self.nextChoiceWeights_7( _factor * -1 )



    def nextChoiceWeights_9( self, _factor ): # the digit that is the least common available choice across the board

        cell_choices = {}

        for id in range( 81 ):

            if self.getCell( id ) == 0:

                cell_choices[ id ] = self.getChoices( id )



        for c in self.nextChoiceWeights:

            weight = 0

            for id in cell_choices:

                if c in cell_choices[ id ]: weight += 1

            self.nextChoiceWeights[ c ] += weight * _factor



    def nextChoiceWeights_a( self, _factor ): # the digit that is the most common available choice across the board

        self.nextChoiceWeights_9( _factor * -1 )







    # the main function to be called

    def solve( self, _nextCellMethod, _nextChoiceMethod, _start_time, _prefillSingleChoiceCells = False ):

        s = self

        s.reset()



        # initialize optimization functions based on the optimization parameters provided

        """

        A - the first cell from left to right, from top to bottom

        B - the first cell from right to left, from bottom to top

        C - a randomly chosen cell

        D - the closest cell to the center of the grid

        E - the cell that currently has the fewest choices available

        F - the cell that currently has the most choices available

        G - the cell that has the fewest blank related cells

        H - the cell that has the most blank related cells

        I - the cell that is closest to all filled cells

        J - the cell that is furthest from all filled cells

        K - the cell whose related blank cells have the fewest available choices

        L - the cell whose related blank cells have the most available choices

        """

        if _nextCellMethod[ 0 ] in "ABCDEFGHIJKLMN":

            s.nextCellWeights_1 = getattr( s, "nextCellWeights_" + _nextCellMethod[0] )

        elif _nextCellMethod[ 0 ] == " ":

            s.nextCellWeights_1 = lambda x: None

        else:

            print( "(A) Incorrect optimization parameters provided" )

            return False



        if len( _nextCellMethod ) > 1:

            if _nextCellMethod[ 1 ] in "ABCDEFGHIJKLMN":

                s.nextCellWeights_2 = getattr( s, "nextCellWeights_" + _nextCellMethod[1] )

            elif _nextCellMethod[ 1 ] == " ":

                s.nextCellWeights_2 = lambda x: None

            else:

                print( "(B) Incorrect optimization parameters provided" )

                return False

        else:

            s.nextCellWeights_2 = lambda x: None



        # initialize optimization functions based on the optimization parameters provided

        """

        0 - the lowest digit

        1 - the highest digit

        2 - a randomly chosen digit

        3 - heuristically, the least used digit across the board

        4 - heuristically, the most used digit across the board

        5 - the digit that will cause related blank cells to have the least number of choices available

        6 - the digit that will cause related blank cells to have the most number of choices available

        7 - the digit that is the least common available choice among related blank cells

        8 - the digit that is the most common available choice among related blank cells

        9 - the digit that is the least common available choice across the board

        a - the digit that is the most common available choice across the board

        """

        if _nextChoiceMethod[ 0 ] in "0123456789a":

            s.nextChoiceWeights_1 = getattr( s, "nextChoiceWeights_" + _nextChoiceMethod[0] )

        elif _nextChoiceMethod[ 0 ] == " ":

            s.nextChoiceWeights_1 = lambda x: None

        else:

            print( "(C) Incorrect optimization parameters provided" )

            return False



        if len( _nextChoiceMethod ) > 1:

            if _nextChoiceMethod[ 1 ] in "0123456789a":

                s.nextChoiceWeights_2 = getattr( s, "nextChoiceWeights_" + _nextChoiceMethod[1] )

            elif _nextChoiceMethod[ 1 ] == " ":

                s.nextChoiceWeights_2 = lambda x: None

            else:

                print( "(D) Incorrect optimization parameters provided" )

                return False

        else:

            s.nextChoiceWeights_2 = lambda x: None



        # fill in all cells that have single choices only, and keep doing it until there are no left, because as soon as one cell is filled this might bring the choices down to 1 for another cell

        if _prefillSingleChoiceCells == True:

            while True:

                next = False

                for id in range( 81 ):

                    if s.getCell( id ) == 0:

                        cell_choices = s.getChoices( id )

                        if len( cell_choices ) == 1:

                            c = cell_choices.pop()

                            s.setCell( id, c )

                            next = True

                if not next: break



        # initialize set of empty cells

        for x in range( 0, 9, 1 ):

            for y in range( 0, 9, 1 ):

                if s.grid[ x ][ y ] == 0:

                    s.empty_cells.add( 9*x + y )

        s.empty_cells_initial = set( s.empty_cells ) # copy by value



        # calculate search space

        for id in s.empty_cells:

            s.search_space *= len( s.getChoices( id ) )



        # initialize the iteration by choosing a first cell

        if len( s.empty_cells ) < 1:

            if s.validate():

                print( "Sudoku provided is valid!" )

                return True

            else:

                print( "Sudoku provided is not valid!" )

                return False

        else: s.current_cell = s.getNextCell()



        s.choices[ s.current_cell ] = s.getChoices( s.current_cell )

        if len( s.choices[ s.current_cell ] ) < 1:

            print( "(C) Sudoku cannot be solved!" )

            return False







        # start iterating the grid

        while True:

            #if time.time() - _start_time > 2.5: return False # used when doing mass tests and don't want to wait hours for an inefficient optimization to complete



            s.iterations += 1



            # if all empty cells and all possible digits have been exhausted, then the Sudoku cannot be solved

            if s.empty_cells == s.empty_cells_initial and len( s.choices[ s.current_cell ] ) < 1:

                print( "(A) Sudoku cannot be solved!" )

                return False



            # if there are no empty cells, it's time to validate the Sudoku

            if len( s.empty_cells ) < 1:

                if s.validate():

                    print( "Sudoku has been solved! " )

                    print( "search space is {}".format( self.search_space ) )

                    print( "empty cells: {}, iterations: {}, backtrack iterations: {}".format( len( self.empty_cells_initial ), self.iterations, self.iterations_backtrack ) )

                    for i in range(9):

                        print( self.grid[i] )

                    return True



            # if there are empty cells, then move to the next one

            if len( s.empty_cells ) > 0:



                s.current_cell = s.getNextCell() # get the next cell

                s.history.append( s.current_cell ) # add the cell to history

                s.empty_cells.remove( s.current_cell ) # remove the cell from the empty queue

                s.choices[ s.current_cell ] = s.getChoices( s.current_cell ) # get possible choices for the chosen cell



                if len( s.choices[ s.current_cell ] ) > 0: # if there is at least one available digit, then choose it and move to the next iteration, otherwise the iteration continues below with a backtrack

                    s.nextChoice()

                    continue



            # if all empty cells have been iterated or there are no empty cells, and there are still some remaining choices, then try another choice

            if len( s.choices[ s.current_cell ] ) > 0 and ( s.empty_cells == s.empty_cells_initial or len( s.empty_cells ) < 1 ): 

                s.nextChoice()

                continue



            # if none of the above, then we need to backtrack to a cell that was previously iterated

            # first, restore the current cell...

            s.history.remove( s.current_cell ) # ...by removing it from history

            s.empty_cells.add( s.current_cell ) # ...adding back to the empty queue

            del s.choices[ s.current_cell ] # ...scrapping all choices

            s.current_choice = 0

            s.setCell( s.current_cell, s.current_choice ) # ...and blanking out the cell



            # ...and then, backtrack to a previous cell

            while True:

                s.iterations_backtrack += 1



                if len( s.history ) < 1:

                    print( "(B) Sudoku cannot be solved!" )

                    return False



                s.current_cell = s.history[ -1 ] # after getting the previous cell, do not recalculate all possible choices because we will lose the information about has been tried so far



                if len( s.choices[ s.current_cell ] ) < 1: # backtrack until a cell is found that still has at least one unexplored choice...

                    s.history.remove( s.current_cell )

                    s.empty_cells.add( s.current_cell )

                    s.current_choice = 0

                    del s.choices[ s.current_cell ]

                    s.setCell( s.current_cell, s.current_choice )

                    continue



                # ...and when such cell is found, iterate it

                s.nextChoice()

                break # and break out from the backtrack iteration but will return to the main iteration

Example call using the world's hardest Sudoku as per this article http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html

hardest_sudoku = [

    [8,0,0,0,0,0,0,0,0],

    [0,0,3,6,0,0,0,0,0],

    [0,7,0,0,9,0,2,0,0],

    [0,5,0,0,0,7,0,0,0],

    [0,0,0,0,4,5,7,0,0],

    [0,0,0,1,0,0,0,3,0],

    [0,0,1,0,0,0,0,6,8],

    [0,0,8,5,0,0,0,1,0],

    [0,9,0,0,0,0,4,0,0]]



mySudoku = Sudoku( hardest_sudoku )

start = time.time()

mySudoku.solve( "A", "0", time.time(), False )

print( "solved in {} seconds".format( time.time() - start ) )

And example output is:

Sudoku has been solved!

search space is 9586591201964851200000000000000000000

empty cells: 60, iterations: 49559, backtrack iterations: 49498

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

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

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

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

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

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

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

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

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

solved in 1.1600663661956787 seconds

Not gonna write full code, but I did a sudoku solver a long time ago. I found that it didn't always solve it (the thing people do when they have a newspaper is incomplete!), but now think I know how to do it.

• Setup: for each square, have a set of flags for each number showing the allowed numbers.


• Crossing out: just like when people on the train are solving it on paper, you can iteratively cross out known numbers. Any square left with just one number will trigger another crossing out. This will either result in solving the whole puzzle, or it will run out of triggers. This is where I stalled last time.


• Permutations: there's only 9! = 362880 ways to arrange 9 numbers, easily precomputed on a modern system. All of the rows, columns, and 3x3 squares must be one of these permutations. Once you have a bunch of numbers in there, you can do what you did with the crossing out. For each row/column/3x3, you can cross out 1/9 of the 9! permutations if you have one number, 1/(8*9) if you have 2, and so forth.


• Cross permutations: Now you have a bunch of rows and columns with sets of potential permutations. But there's another constraint: once you set a row, the columns and 3x3s are vastly reduced in what they might be. You can do a tree search from here to find a solution.