题目

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

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. 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 '.'.
image.png
A sudoku puzzle…
image.png
…and its solution numbers marked in red.

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.

题意

完成数独。

思路

典型的“试错型”问题，使用回溯法：遍历每个空格，每次先插入一个有效的数字(有效性通过isValid()进行判断)，再向后递归，如果递归能够解出数独，说明当前填入的数字是正确的，问题已解决直接返回即可；否则将填入的数字恢复为空格，等待填入下一个数字。不断的“试错”后就能得到正确答案。

代码实现

Java

无hash

  1. class Solution {
  2.     public void solveSudoku(char[][] board) {
  3.         solve(board, 0, 0);
  4.     }
  6.     private boolean solve(char[][] board, int i, int j) {
  7.            // 每一格都填上了数字，说明已经解出数独
  8.         if (i == board.length) {
  9.             return true;
  10.         }
  12.         int nextI = j == board.length - 1 ? i + 1 : i;
  13.         int nextJ = j == board.length - 1 ? 0 : j + 1;
  15.         // 已有数字则不需要处理，直接向后递归
  16.         if (board[i][j] != '.') {
  17.             return solve(board, nextI, nextJ);
  18.         }
  20.         for (int k = 1; k <= 9; k++) {
  21.             char c = (char) ('0' + k);
  22.             if (isValid(board, i, j, c)) {
  23.                 board[i][j] = c;
  24.                 boolean solved = solve(board, nextI, nextJ);
  25.                 // 如果递归能解出数独，说明当前填入的数字是正确的
  26.                 // 否则恢复原状，以免影响下次循环有效性判断的正确性
  27.                 if (solved) {
  28.                     return true;
  29.                 } else {
  30.                     board[i][j] = '.';
  31.                 }
  32.             }
  33.         }
  35.         return false;
  36.     }
  38.     private boolean isValid(char[][] board, int i, int j, char c) {
  39.         for (int k = 0; k < 9; k++) {
  40.             // 注意要排除自身
  41.             if (k != j && c == board[i][k] || k != i && c == board[k][j]) {
  42.                 return false;
  43.             }
  44.         }
  46.         // x、y的初始值为对应九宫格左上顶点的坐标
  47.         for (int x = 3 * (i / 3); x < 3 * (i / 3) + 3; x++) {
  48.             for (int y = 3 * (j / 3); y < 3 * (j / 3) + 3; y++) {
  49.                 // 注意要排除自身
  50.                 if (c == board[x][y] && (x != i || y != j)) {
  51.                     return false;
  52.                 }
  53.             }
  54.         }
  56.         return true;
  57.     }
  58. }

hash

  1. class Solution {
  2.     List<Set<Character>> row = new ArrayList<>();
  3.     List<Set<Character>> col = new ArrayList<>();
  4.     List<Set<Character>> nine = new ArrayList<>();
  6.     public void solveSudoku(char[][] board) {
  7.         initialize(board);
  8.         solve(board, 0, 0);
  9.     }
  11.     private boolean solve(char[][] board, int i, int j) {
  12.         if (i == board.length) {
  13.             return true;
  14.         }
  16.         int nextI = j == board.length - 1 ? i + 1 : i;
  17.         int nextJ = j == board.length - 1 ? 0 : j + 1;
  19.         if (board[i][j] != '.') {
  20.             return solve(board, nextI, nextJ);
  21.         }
  23.         for (int k = 1; k <= 9; k++) {
  24.             char c = (char) ('0' + k);
  25.             if (!row.get(i).contains(c)
  26.                     && !col.get(j).contains(c)
  27.                     && !nine.get(3 * (i / 3) + j / 3).contains(c)) {
  28.                 board[i][j] = c;
  29.                 row.get(i).add(c);
  30.                 col.get(j).add(c);
  31.                 nine.get(3 * (i / 3) + j / 3).add(c);
  32.                 boolean flag = solve(board, nextI, nextJ);
  33.                 if (flag) {
  34.                     return true;
  35.                 } else {
  36.                     board[i][j] = '.';
  37.                     row.get(i).remove(c);
  38.                     col.get(j).remove(c);
  39.                     nine.get(3 * (i / 3) + j / 3).remove(c);
  40.                 }
  41.             }
  42.         }
  44.         return false;
  45.     }
  47.     private void initialize(char[][] board) {
  48.         for (int i = 0; i < 9; i++) {
  49.             row.add(new HashSet<>());
  50.             col.add(new HashSet<>());
  51.             nine.add(new HashSet<>());
  52.         }
  53.         for (int i = 0; i < 9; i++) {
  54.             for (int j = 0; j < 9; j++) {
  55.                 char c = board[i][j];
  56.                 if (c != '.') {
  57.                     row.get(i).add(c);
  58.                     col.get(j).add(c);
  59.                     nine.get(3 * (i / 3) + j / 3).add(c);
  60.                 }
  61.             }
  62.         }
  63.     }
  64. }

JavaScript

无Hash

  1. /**
  2.  * @param {character[][]} board
  3.  * @return {void} Do not return anything, modify board in-place instead.
  4.  */
  5. var solveSudoku = function (board) {
  6.   dfs(board, 0, 0)
  7. }
  9. let dfs = function (board, row, col) {
  10.   if (row === board.length) {
  11.     return true
  12.   }
  14.   let nextRow = col === 8 ? row + 1 : row
  15.   let nextCol = col === 8 ? 0 : col + 1
  17.   if (board[row][col] !== '.') {
  18.     return dfs(board, nextRow, nextCol)
  19.   }
  21.   for (let i = 1; i <= 9; i++) {
  22.     let c = '' + i
  23.     if (isValid(board, row, col, c)) {
  24.       board[row][col] = c
  25.       if (dfs(board, nextRow, nextCol)) {
  26.         return true
  27.       }
  28.       board[row][col] = '.'
  29.     }
  30.   }
  32.   return false
  33. }
  35. let isValid = function (board, row, col, c) {
  36.   for (let i = 0; i < 9; i++) {
  37.     if ((row !== i && board[i][col] === c) || (col !== i && board[row][i] === c)) {
  38.       return false
  39.     }
  40.   }
  42.   let topLeftX = Math.trunc(row / 3) * 3
  43.   let topLeftY = Math.trunc(col / 3) * 3
  45.   for (let i = topLeftX; i < topLeftX + 3; i++) {
  46.     for (let j = topLeftY; j < topLeftY + 3; j++) {
  47.       if (c === board[i][j] && (i !== row || j !== col)) {
  48.         return false
  49.       }
  50.     }
  51.   }
  53.   return true
  54. }

Hash

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  let rows = new Array(9).fill(0).map(v => new Set())
  let cols = new Array(9).fill(0).map(v => new Set())
  let boxes = new Array(9).fill(0).map(v => new Set())

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      let c = board[i][j]
      rows[i].add(c)
      cols[j].add(c)
      boxes[Math.trunc(i / 3) * 3 + Math.trunc(j / 3)].add(c)
    }
  }

  dfs(board, 0, 0, rows, cols, boxes)
}

let dfs = function (board, i, j, rows, cols, boxes) {
  if (i === 9) {
    return true
  }

  let nextI = j === 8 ? i + 1 : i
  let nextJ = j === 8 ? 0 : j + 1

  if (board[i][j] !== '.') {
    return dfs(board, nextI, nextJ, rows, cols, boxes)
  }

  let boxIndex = Math.trunc(i / 3) * 3 + Math.trunc(j / 3)
  for (let num = 1; num <= 9; num++) {
    let c = num + ''
    if (rows[i].has(c) || cols[j].has(c) || boxes[boxIndex].has(c)) {
      continue
    }
    board[i][j] = c
    rows[i].add(c)
    cols[j].add(c)
    boxes[boxIndex].add(c)
    if (dfs(board, nextI, nextJ, rows, cols, boxes)) {
      return true
    }
    board[i][j] = '.'
    rows[i].delete(c)
    cols[j].delete(c)
    boxes[boxIndex].delete(c)
  }

  return false
}