37.Sudoku-Solver

37. Sudoku Solver

题目地址

https://leetcode.com/problems/sudoku-solver/

题目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.

Note:
The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

代码

Approach 1: Backtracking

box_index = (row / 3) * 3 + column / 3

class Solution {
  // box size
  int n = 3;
  // row or column size
  int N = n * n;
  // index + value
  int [][] rows = new int[N][N + 1];
  int [][] columns = new int[N][N + 1];
  int [][] boxes = new int[N][N + 1];

  char[][] board;
  boolean sudokuSolved = false;

  public void solveSudoku(char[][] board) {
        this.board = board;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        char num = board[i][j];
        if (num != '.') {
          int d = Character.getNumbericValue(num);
          placeNumber(d, i, j);
        }
      }
    }
    backtrack(0, 0);
  }

  public boolean couldPlace(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
  }

  public void placeNumber(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    //  Place a number d in (row, col) cell
    rows[row][d]++;
    columns[col][d]++;
    boxes[idx][d]++;
    board[row][col] = (char)(d + '0');
  }

  public void removeNumber(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    rows[row][d]--;
    columns[col][d]--;
    boxes[idx][d]--;
    board[row][col] = '.';
  }

  public void placeNextNumbers(int row, int col) {
    if ((col == N - 1) && (row == N - 1) {
      sudokuSolved = true;
    } else {
      if (col == N - 1) {
        backtrack(row + 1, 0);
      } else {
        backtrack(row, col + 1);
      }
    }
  }

  public void backtrack(int row, int col) {
    if (board[row][col] == '.') {
      for (int d = 1; d < 10; d++) {
        if (couldPlace(d, row, col)) { // constrained programming
          //backtrack
          placeNumber(d, row, col);
          placeNextNumbers(row, col);

          if (!sudokuSolved) removeNumber(d, row, col);
        }
      }
    } else {
      placeNextNumbers(row, col);
    }
  }
}