This solution uses DFS (Depth First Search) Algorithm and looks for a unique solution to the given Sudoku Puzzle.
DFS Solution
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
const solveSudoku = function(board) {
canSolveCheck(board, 0, 0);
};
// sudoku solver (backtracking) Time complexity = O(9^m) m = number of spaces to be filled.
const canSolveCheck = (board, x, y) => {
if (x === 9) {
return true;
} else if (y === 9) {
return canSolveCheck(board, x + 1, 0);
}
if (board[x][y] !== '.') {
return canSolveCheck(board, x, y + 1);
} else {
for (let i = 1; i <= 9; i++) {
board[x][y] = i + '';
if (valid(board, x, y) && canSolveCheck(board, x, y + 1)) {
return true;
}
board[x][y] = '.';
}
return false;
}
};
const valid = (board, x, y) => {
const i = board[x][y];
for (let k = 0; k < 9; k++) {
if (k !== y && board[x][k] === i) {
return false;
}
if (k !== x && board[k][y] === i) {
return false;
}
const row = Math.floor(x / 3) * 3 + Math.floor(k / 3);
const col = Math.floor(y / 3) * 3 + (k % 3);
if (!(row === x && col === y) && board[row][col] === i) {
return false;
}
}
return true;
};
Using a Map
Instead of running valid() for all possible values, we can pre-compute and check if the current value is valid.
const solveSudoku = function(board) {
canSolveCheckMemoryOptimized(board, 0, 0);
};
const canSolveCheckMemoryOptimized = (board, x, y) => {
if (x === 9) {
return true;
} else if (y === 9) {
return canSolveCheck(board, x + 1, 0);
}
if (board[x][y] !== '.') {
return canSolveCheck(board, x, y + 1);
} else {
const obj = {};
buildObj(board, x, y, obj);
for (let i = 1; i <= 9; i++) {
board[x][y] = i + '';
if (!(board[x][y] in obj) && canSolveCheck(board, x, y + 1)) {
return true;
}
board[x][y] = '.';
}
return false;
}
};
const buildObj = (board, x, y, obj) => {
for (let k = 0; k < 9; k++) {
obj[board[x][k]] = true;
obj[board[k][y]] =true;
const row = Math.floor(x / 3) * 3 + Math.floor(k / 3);
const col = Math.floor(y / 3) * 3 + (k % 3);
obj[board[row][col]] = true;
}
};
Another alternate solution would be to precompute these values into lists of Maps.