As promised in my recent article on how to design an algorithm, I am here to take a closer look at another popular technique for algorithm design called backtracking.
Backtracking is a useful algorithm for solving problems with recursion by building a solution incrementally. Generally speaking, backtracking involves starting with a possible solution and if it doesn't work, you backtrack and try another solution until you find something that works. Backtracking is particularly helpful when solving constraint satisfaction problems such as crosswords, verbal arithmetic, and Sudoku.
In general, backtracking algorithms can be applied to the following three types of problems:
- Decision problems to find a feasible solution to a problem
- Optimization problems to find the best solution to a problem
- Enumeration problems to find a set of feasible solutions to a problem
In this article, I will be demonstrating the backtracking strategy by solving a popular problem known as the Sudoku Solver.
Sudoku Solver
As a Sudoku fan myself, I was excited to dive into this problem. The backtracking algorithm for this problem will try to place each number in each row and column until it is solved. Let's start with the main method:
function sudokuSolver(matrix) {
if (solveSudoku(matrix) === true) {
return matrix;
}
return 'NO SOLUTION';
}
Now, let's get into the main logic of our algorithm:
const UNASSIGNED = 0;
function solveSudoku(matrix) {
let row = 0;
let col = 0;
let checkBlankSpaces = false;
/* verify if sudoku is already solved and if not solved,
get next "blank" space position */
for (row = 0; row < matrix.length; row++) {
for (col = 0; col < matrix[row].length; col++) {
if (matrix[row][col] === UNASSIGNED) {
checkBlankSpaces = true;
break;
}
}
if (checkBlankSpaces === true) {
break;
}
}
// no more "blank" spaces means the puzzle is solved
if (checkBlankSpaces === false) {
return true;
}
// try to fill "blank" space with correct num
for (let num = 1; num <= 9; num++) {
/* isSafe checks that num isn't already present
in the row, column, or 3x3 box (see below) */
if (isSafe(matrix, row, col, num)) {
matrix[row][col] = num;
if (solveSudoku(matrix)) {
return true;
}
/* if num is placed in incorrect position,
mark as "blank" again then backtrack with
a different num */
matrix[row][col] = UNASSIGNED;
}
}
return false;
}
Next, let's take a closer look at some helper methods:
function isSafe(matrix, row, col, num) {
return (
!usedInRow(matrix, row, num) &&
!usedInCol(matrix, col, num) &&
!usedInBox(matrix, row - (row % 3), col - (col % 3), num)
);
}
function usedInRow(matrix, row, num) {
for (let col = 0; col < matrix.length; col++) {
if (matrix[row][col] === num) {
return true;
}
}
return false;
}
function usedInCol(matrix, col, num) {
for (let row = 0; row < matrix.length; row++) {
if (matrix[row][col] === num) {
return true;
}
}
return false;
}
function usedInBox(matrix, boxStartRow, boxStartCol, num) {
for (let row = 0; row < 3; row++) {
for (let col = 0; col < 3; col++) {
if (matrix[row + boxStartRow][col + boxStartCol] === num) {
return true;
}
}
}
return false;
}
Lastly, let's put our algorithm to the test:
const sudokuGrid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
];
console.log(sudokuSolver(sudokuGrid));
Here's our sudoku example being solved by backtracking:
Conclusion
I had a lot of fun with this article and hope that you found it helpful for getting a basic understanding of backtracking. Here are some additional resources:
- Overview of Backtracking from Wikipedia
- Video Explanation of Backtracking by V. Anton Spraul
Oldest comments (3)
Thank you very much for the useful article
Could you please explain more about the number 3 in the code, I could not figure out where you get that number from?
It's a 9 x 9 matrix and each boxes are 3 x 3.
Thanks for the article
It would have been better if you displayed a complete listing of a working program, not in your language which resembles C
Best wishes, Jerry