用 JS 做一个数独游戏(一)

用 JS 做一个数独游戏(一)

数独的棋盘由 9x9 的方格组成,每一行的数字包含 1 ~ 9 九个数字,并且每一列包含 1 ~ 9 这 9 个不重复的数字,另外,整个棋盘分为 9 个 3x3 的块,每个块中包含的数字也是 1 ~ 9。数独棋盘是非常对称的,所以行和列实际上通过旋转一定的角度就可以相互转换。

数独终盘

生成步骤

生成数独终盘有多种方法,其中一种是挖洞法:先生成一个随机的数独终盘,然后随机隐藏某几个位置的数字,让用户进行填空。这里我们用到的方法就是挖洞法,以行为单位进行数字的填充。

初始的挖洞法步骤:


  1. 生成的一个空的数独棋盘,棋盘中每个格子的数字都是 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. 生成 1~9 的乱序排列并填充第一行(填充第一列的效果和填充第一行再进行旋转其实是一样的效果,由于填充第一行元素时,其它各行都没有填充过数字,因此第一行的约束条件是最少的);
// populate the first row
let row0 = this.getRowGrids(0);
let randomArray = Utils.getRandomValue();
randomArray.forEach( (element, index ) => {
row0[index].setValue( element );
});

填充完第一行的数独棋盘:

用 JS 做一个数独游戏(一)

  1. 填充第 2 行时,计算第 1 个格子可以使用的数字集合;

这个集合是从一个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9] (把它称为 基本数组)中剔除掉已经被用过的数字。这些用过的数字是从这个格子所在的行、列及块中有效的数字。例如上图中,第 2 行,第 1 列(在数组中序号分别是 1,0)已经用过的数字是 2, 4, 7,那么第 2 行第 1 列可以使用的数字就只能在剩下未使用过的数字中随机选择一个;

  1. 从 (2, 1) 格子处选择可用数字集合中的一个,填充至该位置;

  2. 重复 3~4 步,填充完第 2 行;

  3. 重复第 3~5 步,依次填充完其它行;

  4. 完成数独终盘。


错误的示例

然而上面的算法步骤有一个致命的缺陷:在某些位置(第一个出现的位置是第二行最后一列)可能出现 1~9 所有数字都被该格子所在的行、列和块使用过了,那么这个格子就没有可用的数字。如下图:

用 JS 做一个数独游戏(一)

可以看到,第 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];
}
}

修正的算法步骤:


  1. 生成的一个空的数独棋盘,棋盘中每个格子的数字都是 0;

  2. 生成 1~9 的乱序排列并填充第一行;

  3. 填充第 2 行时,计算第 1 个格子,其位置为 (2,1),可以使用的数字集合;

  4. 从 (2, 1) 格子处选择可用数字集合中的一个,填充至该位置,将用过的数字标记为不可用;

  5. 若某个位置 (i, j) 的格子已无可用的数字集合,若该格子位于第 1 列,则返回上一行,从第一列进行回溯,否则只需返回到上一列进行回溯。

  6. 重复 3~5 步,填充完第 2 行;

  7. 重复第 3~6 步,依次填充完其它行;

  8. 完成数独终盘。


修正后的算法实现:

整体的填充步骤没有变化,在填充时首先判断 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 种数独终盘所用的时间如下:

用 JS 做一个数独游戏(一)

其他

在使用 JavaScript 编写数独时,使用了 QUnit 进行代码测试,在编写测试代码时不仅提高了代码的准确性,也帮助我在测试时完善逻辑代码,用更好的函数封装组织逻辑。

可以直接在 Node 中使用 QUnit,也可以通过浏览器执行测试。用浏览器执行时,视觉效果更好:

用 JS 做一个数独游戏(一)

引入的 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>

代码

能够正确生成数独终盘的 代码

测试代码

参考资料

https://www.cnblogs.com/wangqinze/p/7501716.html

上一篇:(Demo分享)利用原生JavaScript-随机数-实现做一个烟花案例


下一篇:(Demo分享)利用原生JavaScript-ScrollLeft-实现做轮播广告通知