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.