how to solve sudoku in javascript

Here is a simple implementation of sudoku solver in JavaScript using backtracking algorithm:

index.tsx
function solveSudoku(board) {
  const n = board.length;
  const rows = new Array(n);
  const cols = new Array(n);
  const boxes = new Array(n);

  for (let i = 0; i < n; i++) {
    rows[i] = new Set();
    cols[i] = new Set();
    boxes[i] = new Set();
  }

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      if (board[r][c] == '.') continue;

      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      rows[r].add(board[r][c]);
      cols[c].add(board[r][c]);
      boxes[b].add(board[r][c]);
    }
  }

  function dfs(i, j) {
    if (i == n) return true;
    if (j == n) return dfs(i + 1, 0);
    if (board[i][j] != '.') return dfs(i, j + 1);

    const b = Math.floor(i / 3) * 3 + Math.floor(j / 3);

    for (let num = 1; num <= n; num++) {
      const ch = '' + num;
      if (rows[i].has(ch) || cols[j].has(ch) || boxes[b].has(ch)) continue;

      rows[i].add(ch);
      cols[j].add(ch);
      boxes[b].add(ch);
      board[i][j] = ch;

      if (dfs(i, j + 1)) {
        return true;
      }

      rows[i].delete(ch);
      cols[j].delete(ch);
      boxes[b].delete(ch);
      board[i][j] = '.';
    }

    return false;
  }

  if (!dfs(0, 0)) {
    return false;
  }

  return board;
}
1223 chars
59 lines

You can call this function with a 2D array of 9x9 grid with empty cells denoted by '.' character. The function uses backtracking algorithm to solve the sudoku puzzle. It checks each empty cell and tries to fill it with a number from 1 to 9 which satisfies the sudoku rules. If it finds a valid number, it moves to the next empty cell and repeats the process. If it reaches the end without any violations, then it has found a valid solution.

related categories

gistlibby LogSnag