用 JS 做一个数独游戏（一）
数独的棋盘由 9x9 的方格组成，每一行的数字包含 1 ~ 9 九个数字，并且每一列包含 1 ~ 9 这 9 个不重复的数字，另外，整个棋盘分为 9 个 3x3 的块，每个块中包含的数字也是 1 ~ 9。数独棋盘是非常对称的，所以行和列实际上通过旋转一定的角度就可以相互转换。
数独终盘
生成步骤
生成数独终盘有多种方法，其中一种是挖洞法：先生成一个随机的数独终盘，然后随机隐藏某几个位置的数字，让用户进行填空。这里我们用到的方法就是挖洞法，以行为单位进行数字的填充。
初始的挖洞法步骤：
- 生成的一个空的数独棋盘，棋盘中每个格子的数字都是 0；
数独棋盘用 Board 对象表示，该对象中有 81 个 Grid 对象，表示 9x9 的方格。
// class Board
for( let i = 0; i < 9; i++ ) {
for( let j = 0; j < 9; j++ ) {
this.grids[i * 9 + j] = new Grid( i, j );
}
}
- 生成 1~9 的乱序排列并填充第一行（填充第一列的效果和填充第一行再进行旋转其实是一样的效果，由于填充第一行元素时，其它各行都没有填充过数字，因此第一行的约束条件是最少的）；
// populate the first row
let row0 = this.getRowGrids(0);
let randomArray = Utils.getRandomValue();
randomArray.forEach( (element, index ) => {
row0[index].setValue( element );
});
填充完第一行的数独棋盘：
- 填充第 2 行时，计算第 1 个格子可以使用的数字集合；
这个集合是从一个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9] （把它称为
基本数组）中剔除掉已经被用过的数字。这些用过的数字是从这个格子所在的行、列及块中有效的数字。例如上图中，第 2 行，第 1 列（在数组中序号分别是 1，0）已经用过的数字是 2， 4， 7，那么第 2 行第 1 列可以使用的数字就只能在剩下未使用过的数字中随机选择一个；
-
从 (2, 1) 格子处选择可用数字集合中的一个，填充至该位置；
-
重复 3~4 步，填充完第 2 行；
-
重复第 3~5 步，依次填充完其它行；
-
完成数独终盘。
错误的示例
然而上面的算法步骤有一个致命的缺陷：在某些位置（第一个出现的位置是第二行最后一列）可能出现 1~9 所有数字都被该格子所在的行、列和块使用过了，那么这个格子就没有可用的数字。如下图：
可以看到，第 2 行第 9 列没有可用的数字，无法进行填充。其它行也有可能出现这种情况。在这个数独棋盘中，所有为 0 的格子都是无法满足约束条件的。
实际上，出现 0 的位置是因为下面的函数在调用 getRandomValueArray 时返回的数组位空，或者说 used 数组已经是包含 1~9 这 9 个数字。
getRandomValidValue(pos) {
let used = this.getUsedValueArrayAt(pos);
let valueArray = this.getRandomValueArray(used);
return valueArray[0] === undefined ? 0 : valueArray[0];
}
在 github 上存有 错误示例的代码。
修正挖洞法
直接采用挖洞法生成的数独终盘不一定是有效的，如果把填充过程当作一棵树，填充的数字为树的节点，那么有些树枝的路径是无法满足数独的要求的。当填充过程中发现某个位置没有可选的数字时，应该返回上一个填充的节点，在上一个节点处选择其他的数字进行填充。也就是回溯方法。
回溯方法需要记录每个格子可用的数字集合，以及填充时用到的数字，以便在算法失败时（某个位置没有可用数字集合）进行回溯。回溯时已经尝试过的数字将被标记为不可用。有两点需要注意：
-
对每一行的格子而言，从左往右的顺序实际上构成了一个栈，因此不需要额外构建一个堆栈来存储填充时的情况。
-
另外需要注意的一点是，若在 (i, 1) 位置的格子没有可用的数字时，需要回溯到上一行的第 1 列重新选择。
为了记录每次分支时选择的数字，引入一个用于记录当前选择的对象 Choice：
class Choice {
/**
*
* @param {Array<Number>} choiceSet
*/
constructor(choiceSet) {
this.choiceSet = choiceSet;
this.attemptIndex = -1;
}
/**
* 将索引移至下一个位置，并返回该位置的数字
*/
next() {
this.attemptIndex++;
return this.choiceSet[this.attemptIndex];
}
}
修正的算法步骤：
-
生成的一个空的数独棋盘，棋盘中每个格子的数字都是 0；
-
生成 1~9 的乱序排列并填充第一行；
-
填充第 2 行时，计算第 1 个格子，其位置为 (2，1)，可以使用的数字集合；
-
从 (2, 1) 格子处选择可用数字集合中的一个，填充至该位置，将用过的数字标记为不可用；
-
若某个位置 (i, j) 的格子已无可用的数字集合，若该格子位于第 1 列，则返回上一行，从第一列进行回溯，否则只需返回到上一列进行回溯。
-
重复 3~5 步，填充完第 2 行；
-
重复第 3~6 步，依次填充完其它行；
-
完成数独终盘。
修正后的算法实现：
整体的填充步骤没有变化，在填充时首先判断 grid 对象的 choice 属性，若为 undefined，则需要计算 grid 所在的位置处可能的选择：
for(let i = 1; i < 9; i++) {
for(let j = 0; j < 9; j++) {
grid = this.grids[i*9+j];
// process.stdout.write( `i=${i}, j=${j}. `);
if( grid.choice === undefined ) {
used = this.getUsedValueArrayAt( {row: i, col: j} );
unused = Utils.getRandomValue( {exclude: used} );
grid.choice = new Choice( unused );
}
index = this.populateGrid(grid);
i = index.i;
j = index.j;
}
}
填充方法 populateGrid 完成了回溯部分：
/**
* 填充方格，并返回修正过的 i，j索引
*
* 该函数属于回溯部分，在方格没有可选数字时，修正索引，以便进行回溯
* @param {Grid} grid
* @returns {{i: Number, j: Number}}
*/
populateGrid(grid) {
let i = grid.row, j = grid.col;
let value = grid.choice.next();
if( value !== undefined ) {
// 有可以选择的数字
grid.setValue(value);
}
else {
// 没有可选的数字
// Utils.printRow(this, i);
grid.value = 0;
grid.choice = undefined;
if( j == 0 ) {
// i = (i > 0 ? i - 1 : i );
i -= 1;
j -= 1;
this.resetPartialGrids({rowStart: i, rowEnd: i+1, colStart: 1, colEnd: 9}); // 返回上一行后，清空该行其它列的数据
}
else {
j -= 2;
}
}
return {i, j};
}
需要回溯时，populateGrid 会返回修改后的索引，以便重入特定位置，进行回溯。
完成数独终盘
通过修正后的挖洞法，最终可以生成一个有效的数独终盘。生成 1000 种数独终盘所用的时间如下：
其他
在使用 JavaScript 编写数独时，使用了 QUnit 进行代码测试，在编写测试代码时不仅提高了代码的准确性，也帮助我在测试时完善逻辑代码，用更好的函数封装组织逻辑。
可以直接在 Node 中使用 QUnit，也可以通过浏览器执行测试。用浏览器执行时，视觉效果更好：
引入的 html 文件也比较简单，主要内容如下：
<body>
<div id="qunit"></div>
<div id="qunit-fixture"></div>
<script src="https://code.jquery.com/qunit/qunit-2.6.1.js"></script>
<script src="./NumberPlaceGame.js"></script>
<script src="./TestNumberPlaceGame.js"></script>
</body>