Sudoku Solver – 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.