Sudoku Solver

Introduction

37. Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution.

Reference source

Solution

Sudoku problems can be solved with backtracking strategy by trying all possible options for each empty cell, while a new assignment will further constraint its adjacent cells. The solution here uses a extra function findNext() to determine the next empty cell to fill, which has the least options under current constraints, then function solve() will fill one empty cell with some value and try to recursively solve the sub-problem until all cells are filled or no solution is found. Theoretically, this solution should be faster than a naive solution trying to randomly fill cells without any heuristics, because it always starts from a cell with least options, thus reduce the branches in search tree, but actually it doesn’t appear to be fast as heuristic calculation introduces some overhead and too many List and Set operations here are time-consuming. I’m too lazy to change them back to simple array operations.

class Solver {
  // Find next empty slot with largest constraints. Time complexity is O(m^2).
  public int[] findNext(char[][] grid, List<List<Set<Character>>> state) {
    int min = 9;
    int[] loc = {-1, -1};
    for(int i=0; i<9; i++) {
      for(int j=0; j<9; j++) {
        if(grid[i][j] == '.' && state.get(i).get(j).size() < min) {
          min = state.get(i).get(j).size();
          loc[0] = i;
          loc[1] = j;
        }
      }
    }
    return loc;
  }

  // Create board state based on new board layout. Time complexity is O(m^3).
  public List<List<Set<Character>>> getState(char[][] board) {
    List<List<Set<Character>>> state = new ArrayList<>();
    char[] charArray = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};

    // Initialize blank board state.
    for(int i=0; i<9; i++) {
      List<Set<Character>> rows = new ArrayList<>();
      for(int j=0; j<9; j++) {
        Set<Character> cols = new HashSet<>();
        for(int k=0; k<9; k++) {
          cols.add(charArray[k]);
        }
        rows.add(cols);
      }
      state.add(rows);
    }

    // Update effect of every determined cell on other adjacent cells.
    for(int row=0; row<9; row++) {
      for(int col=0; col<9; col++) {
        if(board[row][col] != '.') {
          char val = board[row][col];

          for(int m=0; m<9; m++) {
            state.get(row).get(m).remove(val);
          }							

          for(int m=0; m<9; m++) {
            state.get(m).get(col).remove(val);
          }

          for(int i=(row/3)*3; i<(row/3)*3+3; i++) {
            for(int j=(col/3)*3; j<(col/3)*3+3; j++) {
              state.get(i).get(j).remove(val);
            }
          }
        }
      }
    }

    return state;
  }

  // Recursively find solve Sudoku by backtracking.
  public boolean solve(char[][] board) {
    List<List<Set<Character>>> state = getState(board);
    int[] loc = findNext(board, state);
    int i = loc[0], j = loc[1];
    if(i == -1 && j == -1) return true;

    Set<Character> set = state.get(i).get(j);
    if(!set.isEmpty()) {
      for(char val : set) {
        board[i][j] = val;
        if(solve(board)) return true;
        else board[i][j] = '.';
      }
    }
    else {
      return false;
    }
    return false;
  }
}