# The Beginning

I remember back when I started my journey to master Data Structures and Algorithms (still ongoing), I referred to various tutorials and solutions on sites like GeeksforGeeks, LeetCode etc. and although I could understand the solution, I couldn’t program it myself without referring.

Little did I realise at that point that all the practice I was doing, eventually would add up and I would be able to nail a backtracking problem on my own. For those on the track to learn, algorithms or solving problems on various problems, I can only say keep moving forward. Every new problem you encounter, spend some time thinking about it and it is okay to refer to solutions in the beginning while learning algorithms.

Every problem you solve registers as a blip in your mind and once you’ve done enough problems, so many of these blips have been registered that when you encounter a new problem, your mind automatically connects the dots and you’ll be surprised that you solved it on your own.

This problem is special to me because this was the first big problem for me that I solved without referring to anything. I’d like to share my solution:

# The Sudoku Problem

The problem statement is simple: Given an unsolved sudoku puzzle, we have to generate all possible solutions of the sudoku.

The people familiar with the concept of Sudoku and Backtracking can skip to the solution where I have explained its implementation.

## Sudoku

A sudoku is a puzzle which contains 9 blocks. Each block further has 9 cells for a total of 81 cells. The rules of the puzzle are simple- every block should contain the numbers 1–9, one in each cell, such that the number appears only once in its row, column and block.

Initially, the grid is partially filled. Keeping in mind the constraints, one has to fill in the rest of the cells.

## Backtracking

Backtracking is a technique which basically tests all possible options recursively and returns all the correct ones. At any point if no possible option is valid or no further action can be taken, it backtracks to the last valid state.

It is used to solve various well known problems such as N-Queens, Rat in a Maze, Hamiltonian Cycle etc. (Tutorial for another day)

# Solution

So given an unsolved sudoku, we have to generate all the possible solutions. The language of the problem statement “all the possible solutions” is generally a hint towards applying backtracking algorithm. The solution has been listed in detail below.

## Input

We’ll take line separated input for each row of the board and space separated input for each digit in the row. The board will be stored in a 2D Matrix of 9x9 dimension. The empty cells are denoted by ‘0’ and the non-empty cells by their digits.

`board=[]for i in range(9):    print("Enter space separated elements of row {}".format(i))    row=[int(x) for x in input().strip().split()]    board.append(row)print()solveSudoku(board)`

## Functions

The program implements three functions namely:

1. isValid() : This function returns True if the current move is valid, i.e. if the digit can be placed in the current cell (board[i][j]). It checks the digit for all possible collision.

Collision can occur if :

i) digit x already occurs in the row

ii) digit x already occurs in the column

iii) digit x already occurs in the block

`def isValid(i,j,x,board):    #check row    for col in range(9):        if board[i][col]==x:            return False        #check column    for row in range(9):        if board[row][j]==x:            return False        #check block    startrow=i-i%3    startcol=j-j%3        p=startrow    while p<=startrow+2:        l=startcol        while l<=startcol+2:            if board[p][l]==x:                return False            l+=1        p+=1        return True`

2. sudokuSolverHelper(): this is the function which recursively implements the backtracking algorithm and searches for all possible solutions of the problem.

For ith row it recursively call itself for j+1

Each time j >8 we move to the next row i+1 and reset j to 0 (since there are only 9 columns: 0–8)

When i==8 and j==8, it means we have reached the final cell, and if the digit in the final cell is valid, we print the entire board and return.

It is important reset board[i][j] to 0 (unfilled) after we have returned so that we the algorithm can search for further possible solutions.

`def solveSudokuHelper(i,j,board):    if i==8 and j==8:        if board[i][j]!=0:            for row in board:                for ele in row:                    print(ele, end=" ")                print()        else:            for x in range(1,10):                if isValid(i,j,x,board) is True:                    board[i][j]=x                    for row in board:                        for ele in row:                            print(ele, end=" ")                        print()                    board[i][j]=0        print()        return        if j>8:        solveSudokuHelper(i+1,0,board)          return        if board[i][j]==0:        for x in range(1,10):            if isValid(i,j,x,board) is True:                board[i][j]=x                solveSudokuHelper(i,j+1,board)                 board[i][j]=0    else:        solveSudokuHelper(i,j+1,board)    return`

3. sudokuSolver(): This is the function that calls the helper function with appropriate arguments. A user while interacting does not want to bother with too many arguments but wants the solution and hence this function takes as argument the board and adds appropriate arguments for recursion purpose and calls the main helper function.

`def solveSudoku(board):    solveSudokuHelper(0,0,board)`

## Output

The output prints all the possible solutions of the given sudoku. In our case there is only possible solution for the given input and it is shown below.

## Complete Code:

`def isValid(i,j,x,board):    #check row    for col in range(9):        if board[i][col]==x:            return False        #check column    for row in range(9):        if board[row][j]==x:            return False        #check block    startrow=i-i%3    startcol=j-j%3        p=startrow    while p<=startrow+2:        l=startcol        while l<=startcol+2:            if board[p][l]==x:                return False            l+=1        p+=1        return Truedef solveSudokuHelper(i,j,board):    if i==8 and j==8:        if board[i][j]!=0:            for row in board:                for ele in row:                    print(ele, end=" ")                print()        else:            for x in range(1,10):                if isValid(i,j,x,board) is True:                    board[i][j]=x                    for row in board:                        for ele in row:                            print(ele, end=" ")                        print()                    board[i][j]=0        print()        return        if j>8:        solveSudokuHelper(i+1,0,board)          return        if board[i][j]==0:        for x in range(1,10):            if isValid(i,j,x,board) is True:                board[i][j]=x                solveSudokuHelper(i,j+1,board)                 board[i][j]=0    else:        solveSudokuHelper(i,j+1,board)    returndef solveSudoku(board):    solveSudokuHelper(0,0,board)board=[]for i in range(9):    print("Enter space separated elements of row {}".format(i))    row=[int(x) for x in input().strip().split()]    board.append(row)print()solveSudoku(board)`

# Ending Note

Backtracking is a fairly simple to implement algorithm once you do get a grip on it. Solving this problem gave a significant boost to my confidence and I hope it helps those who want to learn backtracking or solve this problem. This is the first article I’ve shared on medium. I am looking forward to submitting more.

## The Startup 