Sudoku Solver

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.

Java

This solution uses DFS (Depth First Search) Algorithm and looks for a unique solution to the given Sudoku Puzzle.

DFS Solution

class Solution {
  public void solveSudoku(char[][] board) {
    if (solve(board, 0, 0)) {
      System.out.println("Solved");
    }
  }

  public boolean solve(char[][] board, int row, int col) {
    if (row > 8)
      return true;
    if (col > 8)
      return solve(board, row + 1, 0);

    if (board[row][col] != '.') {
      return solve(board, row, col + 1);
    } else {
      for (int k = 1; k <= 9; k++) {
        board[row][col] = (char)(k + '0');
        if (isValid(board, row, col) && solve(board, row, col + 1)) {
          return true;
        } else
          board[row][col] = '.';
      }
    }
    return false;

  }

  public boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < 9; i++) {
      if (i != col && board[row][i] == board[row][col])
        return false;
    }

    for (int j = 0; j < 9; j++) {
      if (j != row && board[j][col] == board[row][col])
        return false;
    }

    int x = (row / 3) * 3;
    int y = (col / 3) * 3;
    for (int m = x; m < x + 3; m++) {
      for (int n = y; n < y + 3; n++) {
        if ((m != row || n != col) && board[m][n] == board[row][col])
          return false;

      }
    }

    return true;

  }
}

Using HashSet

Instead of running valid() for all possible values, we can pre-compute and check if the current value is valid.

class Solution {
  public void solveSudoku(char[][] board) {
    if (solve(board, 0, 0)) {
      System.out.println("Solved");
    }
  }

  public boolean solve(char[][] board, int row, int col) {
    if (row > 8)
      return true;
    if (col > 8)
      return solve(board, row + 1, 0);

    if (board[row][col] != '.') {
      return solve(board, row, col + 1);
    } else {
      HashSet < Character > set = new HashSet < Character > ();
      buildMaps(board, set, row, col);
      for (int k = 1; k <= 9; k++) {
        board[row][col] = (char)(k + '0');
        if (!set.contains(board[row][col]) && solve(board, row, col + 1)) {
          return true;
        } else
          board[row][col] = '.';
      }
    }
    return false;

  }

  public void buildMaps(char[][] board, HashSet < Character > set, int row, int col) {
    for (int i = 0; i < 9; i++) {
      set.add(board[row][i]);
    }
    for (int j = 0; j < 9; j++) {
      set.add(board[j][col]);
    }

    int x = (row / 3) * 3;
    int y = (col / 3) * 3;
    for (int m = x; m < x + 3; m++) {
      for (int n = y; n < y + 3; n++) {
        set.add(board[m][n]);
      }
    }
  }
}

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