In this module, we will discuss certain problems like Rat in a Maze, N-Queen, and Sudoku Solver with the help of backtracking in C++.
Rat in a maze:-
A Maze is given as N*N binary matrix of blocks where source block and destination block are at the top left most block i.e., maze which is a starting point and at bottom right block i.e., maze[N-1][N-1]. A rat starts from the source and must reach the destination. The rat will move solely in 2 directions: forward and down.
In the maze matrix, X suggests that the block may be a dead finish and 0, suggests that the block is utilized in the path from source to destination. Note that this is often an easy version of the standard Maze downside. As an example, an additional complicated version is the rat will move in four directions, and an additional complicated version is with a restricted range of moves. Approach: Form a recursive function, which can follow a path and check if the path reaches the destination or not. If the path does reach the destination then return and check out alternative ways.
Create a solution matrix, at the start crammed with X. Create a recursive function that takes the initial matrix, output matrix, and position of sol(i, j). If the position is out of the matrix or the position is not valid then come back. Mark the position output[i][j] as one and check. If the destination is reached print the output matrix and come back. Recursively demand position (i+1, j) and (i, j+1). Unused position (i, j), i.e ans[i][j] = zero.
The N Queen is the problem of placing chess queens on an N×N chessboard. Naive algorithmic rule finding all configurations of queens on board and print a configuration that satisfies the given constraints and finding no. of solution.
1) begin within the left column.
2) If queen placed then return true
3) attempt all rows within the current column. (a) If the queen is placed safely throughout this row then mark this [row, column] as a part of the answer and recursively check if the queen here finally, ends up in a solution. (b) If putting the queen in [row, column] ends up in an answer then come back true. c) If putting queen does not result in an answer then this [row, column] (backtrack) and head to step (a) to undertake alternative rows. 3) If all rows are tried and nothing worked, then return false to trigger backtracking.
Approach: The naive approach is to induce all configurations of numbers from 1 to 9 to fill the empty cells. Try every configuration one by one until the proper configuration is found, i.e. for every unassigned position fill the position with 1 to 9. Once filling all the unassigned position check if the matrix is safe or not? If safe print else recurs for various cases.