Understanding Backtracking with the Famous Chess Puzzle
Backtracking, a powerful problem solving technique in computer science. In this article we will try to understand backtracking concept by solving one of the famous chess puzzle of arranging N Queens on an “NxN” chessboard.
What is N-Queen Puzzle?
Given the recent surge in chess interest, I presume many of you are familiar with its basics. However, if you’re not, fret not. To tackle N-Queens problem, it’s crucial to grasp how queens navigate the chessboard. The queen, a unique piece, possesses the ability to move horizontally, vertically, and diagonally. Moreover, if any opponent’s piece lies in its path, the queen can threaten it.
In the N-Queen problem, the task is to arrange N queens on an NxN chessboard in a manner where no queen poses threat to another.
How backtracking technique can help in this?
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
All backtracking problems can be solved by following three step pattern.
Choose
Start by choosing a possible option or move. In the N-Queens puzzle, this involves placing a queen on an empty square.
Explore
Move forward with the chosen option and explore the solution space. This might involve placing more queens, each time making a choice.
Un-choose / Backtrack
If the chosen path leads to a dead end, undo the last choice and explore an alternative. This process continues until a solution is found or all possibilities are exhausted.
Solution
As per the rules we discussed earlier, two queens cannot share the same row, column, or the diagonal on the chessboard. We have three constraints in our hand. Checking the vertical and horizontal constraint is straightforward — we examine the columns and rows where the queens are placed. However, for diagonal, we need to find out a pattern.
- Consider Left-to-Right diagonal (Blue arrow): If we subtract column from the row and add the size of the board it should give the same result for any box lying on the same diagonal.
Formula: row — column + N - Consider Right-to-Left diagonal (Black arrow): If we add column and row it should produce the same result for any box lying on the same diagonal.
Formula: row + column
Code
Code is quite self-explanatory. We’ve created a backtrack method that systematically attempts to place a queen in each row, adhering to three constraints discussed before. The rules of “choose, explore and un-choose” are applied to navigate various possibilities.
The method takes six parameters: a list of chessboards storing different arrangements, a temporary chessboard for the current arrangement, the current row, three boolean arrays for checking vertical and diagonals constraints, and the size of the board.
When the method reaches the final row, signifying a valid arrangement, it’s added to the list of chessboards. For each column, constraint checks are performed. Only when there’s no violation, the backtracking steps of choosing, exploring, and un-choosing are executed.
class Solution {
public List<List<String>> solveNQueens(int n) {
// resultant chessboards
List<List<String>> chessboards = new ArrayList<>();
// calling backtrack method which will update the chessboards
backtrack(chessboards, new ArrayList<String>(), 0, new boolean[n], new boolean[2*n], new boolean[2*n], n);
drawChessboards(chessboards);
// return all possibilities of chessboards
return chessboards;
}
// Method to print all possibilities of chessboards
private void drawChessboards(List<List<String>> chessboards) {
for (List<String> chessboard: chessboards) {
for (String row: chessboard) {
System.out.println(row);
}
System.out.println("\n****\n");
}
}
// Main method which will find out all possibilities of arranging N queens over NxN chessboard
public void backtrack(
List<List<String>> chessboards,
List<String> chessboard,
int row,
boolean[] columns,
boolean[] leftToRightDiagonals,
boolean[] rightToLeftDiagonals,
int n
) {
// if we are on last row, it means we have covered the board
if (row == n) {
chessboards.add(new ArrayList<>(chessboard));
} else {
// we will check for each column
for (int column = 0; column < n; column++) {
int leftToRightDiagonal = row - column + n; // left to right diagonal
int rightToLeftDiagonal = row + column; // right to left diagonal
// We will skip if it is already covered
if (columns[column] || leftToRightDiagonals[leftToRightDiagonal] || rightToLeftDiagonals[rightToLeftDiagonal]) continue;
// CHOOSE
char[] boardRow = new char[n];
Arrays.fill(boardRow, '.');
boardRow[column] = 'Q'; // we will place the queen at column col
chessboard.add(String.valueOf(boardRow));
columns[column] = true;
leftToRightDiagonals[leftToRightDiagonal] = true;
rightToLeftDiagonals[rightToLeftDiagonal] = true;
// EXPLORE
backtrack(chessboards, chessboard, row+1, columns, leftToRightDiagonals, rightToLeftDiagonals, n); // backtrack
// UN-CHOOSE
chessboard.remove(chessboard.size() - 1);
columns[column] = false;
leftToRightDiagonals[leftToRightDiagonal] = false;
rightToLeftDiagonals[rightToLeftDiagonal] = false;
}
}
}
}After running this algorithm for a 5x5 chessboard. These are the possibilities which we get.
Q....
..Q..
....Q
.Q...
...Q.
****
Q....
...Q.
.Q...
....Q
..Q..
****
.Q...
...Q.
Q....
..Q..
....Q
****
.Q...
....Q
..Q..
Q....
...Q.
****
..Q..
Q....
...Q.
.Q...
....Q
****
..Q..
....Q
.Q...
...Q.
Q....
****
...Q.
Q....
..Q..
....Q
.Q...
****
...Q.
.Q...
....Q
..Q..
Q....
****
....Q
.Q...
...Q.
Q....
..Q..
****
....Q
..Q..
Q....
...Q.
.Q...
****To sum up, we have explored how Backtracking technique can be used to solve the famous N-Queen Chess problem. It’s not only limited to Chess problems, it can be leveraged to solve other famous puzzles like Sudoku and Crosswords. Beyond puzzles, it can be used in real-life challenges as well offering solution to optimization problem, scheduling dilemmas, and more.
