Categories

# Sudoku Solver – Javascript

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;
}
};``````

Demo

Another alternate solution would be to precompute these values into lists of Maps.