Sudoku using BackTracking

Backtracking means switching back to the previous step as soon as we determine that our current solution cannot be continued into a complete one.

M = 9

def puzzle(a):

    for i in range(M):

        for j in range(M):

            print(a[i][j],end=" ")

        print()

        

def solve(grid, row, col, num):

    #Row wise check if num is there

    for x in range(9):

        if grid[row][x] == num:

            return False

    #column wise check if num is there         

    for x in range(9):

        if grid[x][col] == num:

            return False

 

    #check if num is in 3*3 grid

    startRow = row - row % 3 

    startCol = col - col % 3 

    for i in range(3):

        for j in range(3): 

            if grid[i + startRow][j + startCol] == num:            #0,0==4 0,1  0,2  1,0 1,1 1,2 2,0=4

                return False

    return True

 

def Suduko(grid, row, col):

    #Check end of row and column

    if (row == M - 1 and col == M     ):

        return True

    #Move to next row,first column when last column reached in row

    if col == M:

        row += 1

        col = 0

    #If element is already there move to next column    

    if grid[row][col] > 0:

        return Suduko(grid, row, col + 1)

    #Fill cells with 0 with a suitable number from 1 to 9

    for num in range(1, M + 1, 1):      

        if solve(grid, row, col, num):                                        

            grid[row][col] = num

            if Suduko(grid, row, col + 1): 

                return True

        grid[row][col] = 0

    return False

 

grid = [

 [2, 5, 0, 0, 3, 0, 9, 0, 1],

 [0, 1, 0, 0, 0, 4, 0, 0, 0],

 [4, 0, 7, 0, 0, 0, 2, 0, 8],

 [0, 0, 5, 2, 0, 0, 0, 0, 0],

 [0, 0, 0, 0, 9, 8, 1, 0, 0],

 [0, 4, 0, 0, 0, 3, 0, 0, 0],

 [0, 0, 0, 3, 6, 0, 0, 7, 2],

 [0, 7, 0, 0, 0, 0, 0, 0, 3],

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

 

 

if (Suduko(grid, 0, 0)):

    puzzle(grid)

else:

    print("Solution does not exist:(")

 

ALOGRITHM

In this method for solving the sudoku puzzle, first we assign the size of the 2D matrix to variable M (M*M).

Then we assign the utility function (puzzle) to print the grid.

Later it will assign num to the row and col.

If we find same num in the same row or same column or in the specific 3*3 matrix, ‘false’ will be returned.

Then we will check if we have reached the 8th row and 9th column and return true for stopping the further backtracking.

Next we will check if the column value becomes 9 then we move to the next row and column.

Further now we see if the current position of the grid has value greater than 0, then we iterate for next column.

After checking if it is a safe place , we move to the next column and then assign num in current (row ,col) position of the grid. 

Later we check for next possibility with next column.

As our assumption was wrong, we discard the assigned num and then we go for the next assumption with different num value

Source

Sudoku Solver in Python - AskPython

The above one takes less than half of a second to produce solution.

But below one takes more than one 

Hardest sudoku puzzle

----------------------------

grid =

[[8,5,0,0,0,2,4,0,0],

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

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

 [0,0,0,1,0,7,0,0,2],

 [3,0,5,0,0,0,9,0,0],

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

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

 [0,1,7,0,0,0,0,0,0],

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

]