原题：解数独

思路：递归、回溯

思路

一看到这种组合+查重的问题，咱们就应该能想到用 递归、回溯 + 哈希表

1. 确认方格中的值是否合法

  • 在行中值唯一

    1
    2
    3
    for (let i = 0; i < 9; i++) {
      if (board[y][i] === value) return false;
    }

  • 在列中值唯一

    1
    2
    3
    for (let i = 0; i < 9; i++) {
      if (board[i][x] === value) return false;
    }

  • 在当前 3x3 区块中值唯一

    1
    2
    3
    4
    5
    6
    7
    const startY = Math.floor(y / 3) * 3;
    const startX = Math.floor(x / 3) * 3;
    for (let i = startY; i < startY + 3; i++) {
      for (let j = startX; j < startX + 3; j++) {
        if (board[i][j] === value) return false;
      }
    }

最终实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string[][]} board 棋盘
 * @param {number} x 当前值 x 坐标
 * @param {number} y 当前值 y 坐标
 * @param {string} value 当前值
 * @return {boolean} 是否合法
 */
var checkValue = function (board, x, y, value) {
  // 检查当前行、列上是否存在该值
  for (let i = 0; i < 9; i++) {
    if (board[y][i] === value || board[i][x] === value) return false;
  }
  // 检查当前 3x3 区块中是否存在该值
  const startY = Math.floor(y / 3) * 3;
  const startX = Math.floor(x / 3) * 3;
  for (let i = startY; i < startY + 3; i++) {
    for (let j = startX; j < startX + 3; j++) {
      if (board[i][j] === value) return false;
    }
  }
  return true;
};

2. 遍历每一个方格

1
2
3
4
5
for (let y = 0; y < 9; y++) {
  for (let x = 0; x < 9; x++) {
    ...
  }
}

  • 如果已有值，进入下一次循环

    1
    if (board[y][x] !== '.') continue;

  • 遍历字符串 "1" ~ "9"

    1
    2
    3
    for (let v = 1; v <= 9; v++) {
      ...
    }

    • 如果当前值在该方格合法

      1
      2
      3
      4
      5
      6
      7
      8
      const value = v.toString();
      if (checkValue(board, x, y, value)) {
        board[y][x] = value;
        // 以当前棋盘递归，如果当前值后面的组合成功了，返回 true
        if (search(board)) return true;
        // 否则回溯当前修改，循环尝试下一个值的组合
        board[y][x] = '.';
      }

  • 如果 "1" ~ "9" 中没有符合条件的，当前棋盘无解，返回 false

    1
    2
    3
    4
    for (let v = 1; v <= 9; v++) {
      ...
    }
    return false;

如果走完，说明每个格子都有已合法的值，返回 true

1
return true;

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * @param {string[][]} board
 * @param {number} x
 * @param {number} y
 * @param {string} value
 * @return {boolean}
 */
var checkValue = function (board, x, y, value) {
  // 检查当前行、列上是否存在该值
  for (let i = 0; i < 9; i++) {
    if (board[y][i] === value || board[i][x] === value) return false;
  }
  // 检查当前 3x3 区块中是否存在该值
  const startY = Math.floor(y / 3) * 3;
  const startX = Math.floor(x / 3) * 3;
  for (let i = startY; i < startY + 3; i++) {
    for (let j = startX; j < startX + 3; j++) {
      if (board[i][j] === value) return false;
    }
  }
  return true;
};

/**
 * @param {string[][]} board
 * @return {boolean}
 */
var search = function (board) {
  // 遍历每一个格子
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      // 如果格子有值，找下一个
      if (board[y][x] !== '.') continue;
      // 把每个值都试一次
      for (let v = 1; v <= 9; v++) {
        const value = v.toString();
        // 如果不存在才递归后面的组合
        if (checkValue(board, x, y, value)) {
          board[y][x] = value;
          // 如果当前值后的组合成功了，返回 true
          if (search(board)) return true;
          // 否则回溯当前修改，循环尝试下一个值的组合
          board[y][x] = '.';
        }
      }
      // 没有值能成功符合要求
      return false;
    }
  }
  return true;
};

/**
 * 解答入口
 * @param {string[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  search(board);
};