🧩 Sudoku Solver Algorithm
The Sudoku Solver algorithm is designed to solve any valid 9 × 9 Sudoku puzzle using the backtracking technique. The algorithm systematically fills empty cells while ensuring Sudoku rules are followed.
🧠Understanding the Problem
In a Sudoku puzzle, numbers from 1 to 9 must be placed such that:
- No number repeats in any row.
- No number repeats in any column.
- No number repeats in any 3 × 3 subgrid.
⚙️ Implementation in JavaScript
Below is an efficient JavaScript implementation using backtracking:
const isValid = (board, row, col, k) => {
for (let i = 0; i < 9; i++) {
const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
const n = 3 * Math.floor(col / 3) + (i % 3);
if (board[row][i] === k || board[i][col] === k || board[m][n] === k) {
return false;
}
}
return true;
};
const sudokuSolver = (data) => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (data[i][j] === '.') {
for (let k = 1; k <= 9; k++) {
if (isValid(data, i, j, `${k}`)) {
data[i][j] = `${k}`;
if (sudokuSolver(data)) {
return true;
} else {
data[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
};
🚀 How the Algorithm Works
1️⃣ Start with an incomplete Sudoku board.
2️⃣ Scan the board for an empty cell.
3️⃣ Try placing a number (1-9) and check if it follows Sudoku rules.
4️⃣ If valid, move to the next empty cell; if not, backtrack and try another number.
5️⃣ Repeat until the board is fully solved or no solution exists.
🛠️ Time Complexity
The worst-case time complexity of this backtracking approach is O(9^(N)), where N is the number of empty cells.
✅ Example Output
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
---------------------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
---------------------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
🎯 Applications
- AI-based Sudoku solvers
- Constraint satisfaction problems
- Algorithmic problem-solving training
📌 Conclusion
The Sudoku Solver algorithm is a powerful example of backtracking, demonstrating how systematic trial and error can solve complex puzzles efficiently.
