content: // https://leetcode.com/problems/sudoku-solver
  // T: O(n^2 * k) but n = 9 and k = 9 so just O(1)
  // S: O(n^2) but n = 9 so just O(1)
  
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Map;
  import java.util.Set;
  
  public class SudokuSolver {
      private record Position(int row, int column) {
          private static final Position start = new Position(0, 0);
  
          private boolean isValid() {
              return row >= 0
                      && row < 9
                      && column >= 0
                      && column < 9;
          }
  
          private Position next() {
              if (column == 8) return new Position(row + 1, 0);
              return new Position(row, column + 1);
          }
      }
  
      private static final Map<Integer, Set<Integer>> rows = new HashMap<>();
      private static final Map<Integer, Set<Integer>> columns = new HashMap<>();
      private static final Map<Integer, Set<Integer>> subGrids = new HashMap<>();
  
      public static void solveSudoku(char[][] board) {
          computeDigitsInRows(board);
          computeDigitsInColumns(board);
          computeDigitsInSubGrids(board);
          solveSudoku(board, Position.start);
      }
  
      private static boolean solveSudoku(char[][] board, Position position) {
          if (!position.isValid()) return true;
          if (isAlreadyFilled(board, position)) return solveSudoku(board, position.next());
  
          for (int i = 1 ; i <= 9 ; i++) {
              if (isInRow(i, position) || isInColumn(i, position) || isInSubGrid(i, position)) continue;
              insertInGrid(i, position, board);
              boolean solved = solveSudoku(board, position.next());
              if (solved) return true;
              removeFromGrid(i, position, board);
          }
          return false;
      }
  
      private static boolean isAlreadyFilled(char[][] board, Position position) {
          return board[position.row][position.column] != '.';
      }
  
      private static boolean isInRow(int digit, Position position) {
          return rows.get(position.row).contains(digit);
      }
  
      private static boolean isInColumn(int digit, Position position) {
          return columns.get(position.column).contains(digit);
      }
  
      private static boolean isInSubGrid(int digit, Position position) {
          return subGrids.get(getSubGridId(position)).contains(digit);
      }
  
      private static void insertInGrid(int digit, Position position, char[][] board) {
          rows.get(position.row).add(digit);
          columns.get(position.column).add(digit);
          subGrids.get(getSubGridId(position)).add(digit);
          board[position.row][position.column] = toChar(digit);
      }
  
      private static void removeFromGrid(int digit, Position position, char[][] board) {
          rows.get(position.row).remove(digit);
          columns.get(position.column).remove(digit);
          subGrids.get(getSubGridId(position)).remove(digit);
          board[position.row][position.column] = '.';
      }
  
      private static void computeDigitsInRows(char[][] board) {
          for (int row = 0 ; row < 9 ; row++) {
              final Set<Integer> digits = new HashSet<>();
              for (char element : board[row]) {
                  if (Character.isDigit(element)) {
                      digits.add(toInt(element));
                  }
              }
              rows.put(row, digits);
          }
      }
  
      private static void computeDigitsInColumns(char[][] board) {
          for (int column = 0 ; column < 9 ; column++) {
              final Set<Integer> digits = new HashSet<>();
              for (int row = 0 ; row < 9 ; row++) {
                  if (Character.isDigit(board[row][column])) {
                      digits.add(toInt(board[row][column]));
                  }
              }
              columns.put(column, digits);
          }
      }
  
      private static void computeDigitsInSubGrids(char[][] board) {
          for (int i = 0 ; i < 3 ; i++) {
              for (int j = 0 ; j < 3 ; j++) {
                  final int subGridId = getSubGridId(i, j);
                  final Set<Integer> digits = new HashSet<>();
                  for (int row = 3 * i ; row < 3 * i + 3 ; row++) {
                      for (int column = 3 * j ; column < 3 * j + 3 ; column++) {
                          if (Character.isDigit(board[row][column])) {
                              digits.add(toInt(board[row][column]));
                          }
                      }
                  }
                  subGrids.put(subGridId, digits);
              }
          }
      }
  
      private static int toInt(char c) {
          return c - '0';
      }
  
      private static char toChar(int digit) {
          return (char) ('0' + digit);
      }
  
      private static int getSubGridId(int i, int j) {
          return 10 * i + j;
      }
  
      private static int getSubGridId(Position position) {
          int i = position.row / 3;
          int j = position.column / 3;
          return getSubGridId(i, j);
      }
  }
  