介绍

数独（日语：数独／すうどく Sūdoku */?）是一种数学逻辑游戏，游戏由 9×9 个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少 17 个数字使得解答谜题只有一个答案。

规则：

• 游戏一般由 9 个 3×3 个的九宫格组成。
• 每一列的数字均须包含 1～9，不能缺少，也不能重复。
• 每一宫 (粗黑线围起来的区域，通常是 3*3 的九宫格) 的数字均须包含 1～9，不能缺少，也不能重复。

有几种计算机算法可以在几分之一秒内解决 9×9 的谜题（n=9），但是随着 n 的增加会出现组合爆炸，从而对可以构建、分析和解决 n 增加的 Sudokus 的属性造成限制。

Backtracking

一些业余爱好者开发了计算机程序，将使用回溯算法来解决数独谜题，这是一种蛮力搜索（brute force）。

蛮力算法以某种顺序访问空单元格，按顺序填入数字，或者在发现数字无效时进行回溯。简而言之，一个程序会通过在第一个单元格放置数字 "1" 并检查是否允许它出现在那里来解决一个谜题。如果没有违反规定（检查行、列和框的约束），那么算法就会推进到下一个单元格，并在该单元格中放置一个 "1"。在检查违规情况时，如果发现 "1" 是不允许的，该值就会被推进到 "2"。如果发现一个单元格中的 9 位数字都不允许，那么该算法将该单元格留空，并移回前一个单元格。然后，该单元格中的值将被增加 1。如此反复，直到发现最后一个（第 81 个）单元格中的允许值。

这种方法的优点是：

• 保证有一个解决方案（只要谜题是有效的）。
• 解题时间大多与难度无关。
• 该算法（也就是程序代码）比其他算法更简单，尤其是与确保最难的谜题得到解决的复杂算法相比。

实现

JavaScript

class Sudoku {
  // Sudoku Class to hold the board and related functions
  constructor (board) {
    this.board = board
  }

  findEmptyCell () {
    // Find a empty cell in the board (returns [-1, -1] if all cells are filled)
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (this.board[i][j] === 0) return [i, j]
      }
    }
    return [-1, -1]
  }

  check ([y, x], value) {
    // checks if the value to be added in the board is an acceptable value for the cell

    // checking through the row
    for (let i = 0; i < 9; i++) {
      if (this.board[i][x] === value) return false
    }
    // checking through the column
    for (let i = 0; i < 9; i++) {
      if (this.board[y][i] === value) return false
    }

    // checking through the 3x3 block of the cell
    const secRow = Math.floor(y / 3)
    const secCol = Math.floor(x / 3)
    for (let i = (secRow * 3); i < ((secRow * 3) + 3); i++) {
      for (let j = (secCol * 3); j < ((secCol * 3) + 3); j++) {
        if (y !== i && x !== j && this.board[i][j] === value) return false
      }
    }

    return true
  }

  solve () {
    const [y, x] = this.findEmptyCell()

    // checking if the board is complete
    if (y === -1 && x === -1) return true

    for (let val = 1; val < 10; val++) {
      if (this.check([y, x], val)) {
        this.board[y][x] = val
        if (this.solve()) return true
        // backtracking if the board cannot be solved using current configuration
        this.board[y][x] = 0
      }
    }
    // returning false the board cannot be solved using current configuration
    return false
  }

  getSection (row, [start, end]) {
    return this.board[row].slice(start, end)
  }

  printBoard (output = (...v) => console.log(...v)) {
    // helper function to display board
    for (let i = 0; i < 9; i++) {
      if (i % 3 === 0 && i !== 0) {
        output('- - - - - - - - - - - -')
      }
      output(
        ...this.getSection(i, [0, 3]), ' | ',
        ...this.getSection(i, [3, 6]), ' | ',
        ...this.getSection(i, [6, 9]))
    }
  }
}

扩展

使用 Bit Masks 解决 Sudoku 问题：

对于每一行 / 每一列 / 每一个 Box 都创建一个 Bit Mask，对于网格中的每一个元素，在相应的 Bit Mask 中把位置 ' 值' 的比特设置为 1，进行 O（1）检查。

按照下面的步骤来解决问题：

• 创建 3 个大小为 N 的数组（行、列、盒各一个）。
• 盒子的索引从 0 到 8。（为了找到一个元素的盒子索引，我们使用以下公式：行 / 3*3 + 列 / 3）。
• 首先映射网格的初始值。
• 每次我们向 / 从网格中添加 / 删除一个元素时，都要把相应的位掩码设置为 1/0。

const N = 9
 
// Bitmasks for each row/column/box
let row = new Array(N), col = new Array(N), box = new Array(N);
let seted = false;
 
// Utility function to find the box index
// of an element at position [i][j] in the grid
function getBox(i,j) {
  return Math.floor(i / 3) * 3 + Math.floor(j / 3);
}
 
// Utility function to check if a number
// is present in the corresponding row/column/box
function isSafe(i,j,number) {
  return !((row[i] >> number) & 1) && !((col[j] >> number) & 1) && !((box[getBox(i,j)] >> number) & 1);
}
 
// Utility function to set the initial values of a Sudoku board
// (map the values in the bitmasks)
function setInitialValues(grid) {
  for (let i = 0; i < N;i++)
      for (let j = 0; j < N; j++)
          row[i] |= 1 << grid[i][j],
          col[j] |= 1 << grid[i][j],
          box[getBox(i, j)] |= 1 << grid[i][j];
}
 
/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in
such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */
function SolveSudoku(grid ,i, j) {
  // Set the initial values
  if(!seted){
      seted = true,
      setInitialValues(grid);
  }

  if(i == N - 1 && j == N) return true;
  if(j == N){
      j = 0;
      i++;
  }

  if(grid[i][j]) return SolveSudoku(grid, i, j + 1);

  for (let nr = 1; nr <= N;nr++) {
      if(isSafe(i, j, nr)) {
        /* Assign nr in the current (i, j) position and add nr to each bitmask */
        grid[i][j] = nr;
        row[i] |= 1 << nr;
        col[j] |= 1 << nr;
        box[getBox(i, j)] |= 1 << nr;

        if(SolveSudoku(grid, i,j + 1)) return true;

        // Remove nr from each bitmask and search for another possibility
        row[i] &= ~(1 << nr);
        col[j] &= ~(1 << nr);
        box[getBox(i, j)] &= ~(1 << nr);
      }

      grid[i][j] = 0;
  }

  return false;
}

Crook’s Algorithm

温斯洛普大学计算机科学教授詹姆斯 - 克鲁克发表了一篇名为《解决数独谜题的纸笔算法 (opens new window)》的论文。在论文中，Crook 提到，如果没有进一步的可能步骤，猜测是必要的。这种猜测并没有加入到如下算法中。因此，当你使用这个算法来解决数独问题时，有可能无法得到答案。

步骤：

• Markup：列出每个单元格中所有可能的数字。
• Find singleton：找到如果有一个行、列或框，里只有一个可能的值，成为 singleton。所以你在这个单元格里填上这个数字，然后在受影响的行、列或框里更新标记。
• Find Preemptive Sets：
• Eliminate possible numbers outside preemptive sets。

参考：

• Solve Sudoku more elegantly with Crook’s algorithm in Python | by WY Fok | Towards Data Science (opens new window)
• wyfok/Solve_Sudoku_with_Crook_algorithm: Apply Sudoku rules and Crook's algorithm to solve Sudoku (opens new window)
• Mathematics and Sudokus: Solving Algorithms (II) (opens new window)
• www.ams.org/notices/200904/rtx090400460p.pdf (opens new window)

参考

• Sudoku - Wikiwand (opens new window)
• Sudoku solving algorithms - Wikiwand (opens new window)
• Sudoku | Backtracking-7 - GeeksforGeeks (opens new window)