Published in

Daily Python

# What exactly is a Sudoku Puzzle?

According to Wikipedia, Sudoku (originally called Number Place) is a logic-based, combinatorial number-placement puzzle.

The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9.

The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Note: The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in the OEIS), or around 6.67×1021.

So, generating all the grids and choosing the solution is not efficient. To minimize this task, we can use a Backtracking approach.

# What is Backtracking?

It is algorithmic-technique for finding all solutions to the same computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution.

In our problem, we need to traverse each block of the grid, check which digit can be placed in this block, repeat till we have a solution. If a digit cannot be placed in the current block, we go to the previous block and try placing another digit in that block, changing the next possible solution.

This basically means, whenever we arrive at a dead-end, we go back to the previous choice we made and change our choice, such that we will have a different possible solution.

# Let’s first find a sudoku problem to solve

You can either download the CSV file or copy a string of the sudoku puzzle problem and create a grid in the code.

# Forming the Puzzle

`#Forming the Puzzle Griddef form_grid(puzzle_string):    global grid    print('The Sudoku Problem')    for i in range(0, len(puzzle_string), 9):        row = puzzle_string[i:i+9]        temp = []        for block in row:            temp.append(int(block))        grid.append(temp)        printGrid()`

# Function to print the Grid

`#Function to print the griddef printGrid():    global grid    for row in grid:        print(row)`

# Function to check if a digit can be placed in the current block

`#Function to check if a digit can be placed in the given blockdef possible(row,col,digit):    global grid    for i in range(0,9):        if grid[row][i] == digit:            return False    for i in range(0,9):        if grid[i][col] == digit:            return False    square_row = (row//3)*3    square_col = (col//3)*3    for i in range(0,3):        for j in range(0,3):            if grid[square_row+i][square_col+j] == digit:                return False        return True`

# Traversing through all blocks w/ Backtracking

`def solve():    global grid    for row in range(9):        for col in range(9):            if grid[row][col] == 0:                for digit in range(1,10):                    if possible(row,col,digit):                        grid[row][col] = digit                        solve()                        grid[row][col] = 0  #Backtrack step                return    print('\nThe Solution')    printGrid()`

# Finally, passing the Grid and calling the function to Solve the Puzzle

`puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"grid = []form_grid(puzzle_string)solve()`