Backtracking: Mazes, NQueens, and NKnights
Table of contents
Backtracking is a fascinating and versatile algorithmic technique. It involves exploring all potential solutions to a problem by recursively attempting to build a solution one step at a time while removing the previous step if it doesn't lead to a valid solution. Here, we'll dive into some compelling examples involving mazes, NQueens, and NKnights problems.
Let’s understand the Mazes first and move to Backtracking afterwards. Let’s consider a 3×3 maze like this.
Case 1: Maze Traversal (Right and Down Only)
Imagine a simple 3x3 maze where we start at the top-left corner (0,0) and need to reach the bottom-right corner (2,2). Movement is restricted to right and down directions. The goal is to print all possible paths to the destination.
Approach:
Base Condition: If the current coordinates are (2,2), print the accumulated path string and return.
Recursive Calls:
Move right by appending 'R' to the path string and incrementing the column index.
Move down by appending 'D' to the path string and incrementing the row index.
The recursion builds the path step by step.
This approach ensures all valid paths are explored, leveraging recursion to track the state of the journey.
static void maze(String p, int a, int b){
if (a==2 && b==2){
System.out.println(p);
return;
}
if (a<2) {
maze(p+'D',a+1,b);
}
if (b<2){
maze(p+'R',a,b+1);
}
}
Output:
DDRR DRDR DRRD RDDR RDRD RRDD
Case 2: Maze Traversal with Diagonal Movement
Now, let’s allow diagonal movements in the maze. In addition to moving right ('R') and down ('D'), you can also move diagonally ('d'). The function should return all paths as a list of strings.
Approach:
Base Condition: When at (2,2), return a list containing the accumulated path.
Recursive Calls:
Move right by appending 'R' to the path and updating the column index.
Move down by appending 'D' and updating the row index.
Move diagonally by appending 'd' and updating both row and column indices.
Merge results from all recursive calls to produce the final list of paths.
The additional diagonal movement increases complexity, but recursion handles all permutations seamlessly.
static ArrayList<String> mazeRetListDiagonal(String p, int a, int b){
if (a==2 && b==2){
ArrayList<String> list = new ArrayList<>();
list.add(p);
return list;
}
ArrayList<String> list = new ArrayList<>();
if (a<2) {
list.addAll(mazeRetListDiagonal(p+'D', a+1, b)); // L = left
}
if (b<2){
list.addAll(mazeRetListDiagonal(p+'R',a,b+1)); // R = right
}
if (a<2 && b<2){
list.addAll(mazeRetListDiagonal(p+'d',a+1,b+1)); // d = diagonal
}
return list;
}
Output:
[DDRR, DRDR, DRRD, DRd, DdR, RDDR, RDRD, RDd, RRDD, RdD, dDR, dRD, dd]
Case 3: Maze Traversal with Obstacles
In real-world scenarios, mazes often contain obstacles. Let’s assume a 3x3 maze with a blocked cell at (1,1).
Here, we represent the maze as a 2D boolean array where false indicates an obstacle.
Approach:
Base Condition: If the current cell is (2,2), print the path and return.
Obstacle Check: If the current cell is
false, terminate the recursion.Recursive Calls:
- Move right ('R'), down ('D'), or diagonally ('d') if valid and not blocked.
Recursion ensures paths that navigate around the obstacle are printed while invalid paths are pruned early.
This adaptation demonstrates the power of recursive backtracking in dynamically handling constraints.
static void mazeRetListObstacles(String p, boolean[][] maze, int a, int b){
if (a==maze.length-1 && b==maze[0].length-1){
System.out.println(p);
return;
}
if (!maze[a][b]){
return;
}
if (a<maze.length-1) {
mazeRetListObstacles(p+'D',maze,a + 1, b);
}
if (b<maze[0].length-1){
mazeRetListObstacles(p+'R',maze, a,b+1);
}
if (a<maze.length-1 && b<maze[0].length-1){
mazeRetListObstacles(p+'d',maze,a+1,b+1);
}
}
Output:
DDRR DdR RRDD RdD
Case 4: Maze Traversal with All Directions (Using Backtracking)
What if we allow movement in all four directions (up, down, left, and right) in a boolean maze with obstacles? This could lead to infinite loops if we revisit the same cell. To prevent this, we use backtracking.
Approach:
Mark Visited: As we traverse a cell, mark it
falseto prevent revisiting.Recursive Calls:
- Explore all four directions (up, down, left, right) while ensuring the move is valid.
Unmark on Backtrack: Once all recursive calls for a cell are complete, revert it to
trueto enable other paths to explore it.
Additionally, this approach can be extended to visualize the path in the maze using a step matrix, showcasing the order in which cells are visited. Backtracking ensures all possible paths are explored efficiently.
static void mazeObstaclesPrintAllDir(String p, boolean[][] maze, int r, int c, int[][] path, int step){
if (r==maze.length-1 && c==maze[0].length-1){
path[r][c] = step;
for(int[] arr : path){
System.out.println(Arrays.toString(arr));
}
System.out.println(p);
System.out.println();
return;
}
if (!maze[r][c]){
return;
}
// I am considering this block in my path
maze[r][c] = false;
path[r][c] = step;
if (r<maze.length-1) {
mazeObstaclesPrintAllDir(p+'D',maze,r + 1, c, path,step+1);
}
if (c<maze[0].length-1){
mazeObstaclesPrintAllDir(p+'R',maze, r,c+1, path,step+1);
}
if (r>0){
mazeObstaclesPrintAllDir(p+'U',maze, r-1,c, path,step+1);
}
if (c>0){
mazeObstaclesPrintAllDir(p+'L',maze, r,c-1, path,step+1);
}
// this line is where the function will be over
// so before the function gets removed, also remove the changes that were made by that function
maze[r][c] = true;
path[r][c] = 0;
}
Output:
NQueens Problem
The NQueens problem involves placing N queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can be in the same row, column, or diagonal.
Approach:
Step-by-Step Explanation:
Defining the Problem:
The chessboard is represented as a 2D array, where
1denotes a queen's position, and0denotes an empty square.Queens threaten other pieces in their row, column, and diagonals.
Base Condition:
- If all queens are placed successfully (i.e., if we've reached the last row), print the current board configuration.
Recursive Calls:
Start row-by-row. For each row, attempt to place a queen in every column.
For each potential position:
Check if it is safe to place the queen.
If safe, mark the cell and recurse to the next row.
If placing the queen leads to a solution, continue. If not, backtrack by removing the queen.
Safety Check:
- Ensure no queen exists in the current column or diagonals of the cell being evaluated.
Backtracking:
- Remove the queen from the current position before returning to try the next possibility in the previous row.
This algorithm efficiently explores all possible configurations, pruning invalid branches early.
static int queens(boolean[][] board, int row){
if (row == board.length){
display(board);
System.out.println();
return 1;
}
int count =0;
for (int col = 0; col < board[0].length; col++) {
if (isSafe(board,row,col)){
board[row][col]=true;
count += queens(board,row+1);
board[row][col]=false;
}
}
return count;
}
private static boolean isSafe(boolean[][] board, int row, int col) {
//Check above straight paths
for (int i = 0; i < row; i++) {
if (board[i][col]){
return false;
}
}
//Check above diagonal left
int maxLeft = Math.min(row,col);
for (int i = 1; i <= maxLeft; i++) {
if (board[row-i][col-i]){
return false;
}
}
//Check above diagonal right
int maxRight = Math.min(row, board.length-col-1);
for (int i = 1; i <= maxRight; i++) {
if (board[row-i][col+i]){
return false;
}
}
return true;
}
private static void display(boolean[][] board) {
for (boolean[] arr : board){
for (boolean ele : arr){
if (ele){
System.out.print("Q ");
}
else {
System.out.print("X ");
}
}
System.out.println();
}
}
Output:
NKnights Problem
The NKnights problem involves placing N knights on an N×N chessboard such that no two knights attack each other. Knights move in an L-shape, making their attack pattern unique.
Approach:
Step-by-Step Explanation:
Understanding the Problem:
Knights have a unique movement pattern (two squares in one direction and one square perpendicular, or vice versa).
No knight should threaten another.
Base Condition:
- If all knights are successfully placed (i.e., the required number of knights have been positioned), print the chessboard configuration.
Recursive Calls:
Iterate through every cell on the board.
For each cell:
Check if it is safe to place a knight.
If safe, mark the cell and recurse to place the next knight.
Safety Check:
- Evaluate potential knight attack positions based on the L-shaped movement. Ensure no other knight occupies these positions.
Backtracking:
- After exploring all possibilities from a position, unmark the cell and continue with the next cell.
The NKnights problem showcases backtracking's ability to handle highly specific constraints effectively.
static void knights(boolean[][] board, int row, int col, int knights){
if (knights == 0){
display(board);
System.out.println();
return;
}
if (row == board.length) {
return;
}
if (col == board.length){
knights(board, row+1, 0, knights);
return;
}
if(isSafe(board, row, col)){
board[row][col] = true;
knights(board, row, col+1, knights-1);
board[row][col] = false;
}
knights(board, row, col+1, knights);
}
private static boolean isSafe(boolean[][] board, int row, int col) {
if (isValid(board, row-2, col-1)) {
if (board[row-2][col-1]){
return false;
}
}
if (isValid(board, row-2, col+1)) {
if (board[row-2][col+1]){
return false;
}
}
if (isValid(board, row-1, col+2)) {
if (board[row-1][col+2]){
return false;
}
}
if (isValid(board, row-1, col-2)) {
if (board[row-1][col-2]){
return false;
}
}
return true;
}
static boolean isValid (boolean[][] board, int row, int col){
if (row < board.length && row>=0 && col>=0 && col< board.length){
return true;
}
return false;
}
private static void display(boolean[][] board) {
for (boolean[] arr : board){
for (boolean ele : arr){
if (ele){
System.out.print("K ");
}
else {
System.out.print("X ");
}
}
System.out.println();
}
}
Output:
GitHub Repository
Find the implementations of these backtracking problems in the following GitHub repository:
GitHub Repository: Backtracking Examples
Summary
Backtracking is like having a guide for solving puzzles, one step at a time. It allows us to try all possibilities by taking steps forward, and if we hit a dead-end, we simply backtrack and try another path. From navigating mazes with different types of movements to solving chessboard puzzles like NQueens and NKnights, backtracking proves its power to handle challenges systematically.
Whether it's avoiding obstacles, exploring all directions in a maze, or carefully placing pieces on a chessboard without conflicts, this technique showcases its versatility and adaptability.
This exploration forms a solid foundation for delving into more advanced backtracking problems, demonstrating how recursion and systematic exploration can solve intricate challenges.