前言
如果想实现一个数独小游戏，可以先了解舞蹈链这个数据结构，还是很有意思的。我不准备再具体讲解 dance link 是什么，因为很难比其它文章写的更好，只提供一个 JavaScript 的实现在下面，如果你感兴趣的话，可以查阅，有问题可以留言讨论。
class Node {
left;
right;
up;
down;
row; // 所在行 index
col; // 所在列 index
}
class DanceLink {
ans = [];
removeNodes = [];
matrix = [];
head;
columnHead = [];
rowHead = [];
removeNodes = [];
lastRowFilledCol = false;
constructor(matrix) {
this.matrix = matrix;
this.buildLink();
this.dance();
}
buildLink() {
this.createHead();
this.createColumnHead();
this.createMatrixNode();
// this.showMatrixByColumn();
// this.showMatrixByRow();
}
// 把一行行节点展示出来
showMatrixByRow() {
let row = this.matrix.length;
let rowHead = this.rowHead;
for (let i = 0; i < row; i++) {
let head = rowHead[i];
let row = this.getARow(head);
console.log(i, row);
}
}
// 获取一行的节点
getARow(node) {
let head = node;
let cur = head.right;
let row = [head];
while (cur !== head) {
row.push(cur);
cur = cur.right;
}
return row;
}
// 获取一列的节点
getACol(colHead) {
let cur = colHead.down;
let col = [];
while (colHead !== cur) {
col.push(cur);
cur = cur.down;
}
return col;
}
// 把一列列节点展示出来
showMatrixByColumn() {
let columnHead = this.columnHead;
let col = columnHead.length;
for (let i = 0; i < col; i++) {
let colHead = columnHead[i];
let col = this.getACol(colHead);
console.log("column:", i, col);
}
}
createMatrixNode() {
let matrix = this.matrix;
let columnHead = this.columnHead;
let row = matrix.length;
let col = matrix[0].length;
let rowHead = [];
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (matrix[i][j]) {
let node = new Node();
if (!rowHead[i]) {
node.left = node.right = node;
rowHead[i] = node;
}
let colHead = columnHead[j];
let rowNodeHead = rowHead[i];
node.row = i;
node.col = j;
// right left
node.right = rowNodeHead;
node.left = rowNodeHead.left;
rowNodeHead.left.right = node;
rowNodeHead.left = node;
// up down
node.down = colHead;
node.up = colHead.up;
colHead.up.down = node;
colHead.up = node;
}
}
}
this.rowHead = rowHead;
}
createColumnHead() {
let head = this.head;
let col = this.matrix[0].length;
let arr = [];
for (let i = 0; i < col; i++) {
let node = new Node();
node.col = i;
node.type = "column head";
node.up = node;
node.down = node;
node.right = head;
node.left = head.left;
head.left.right = node;
head.left = node;
arr.push(node);
}
this.columnHead = arr;
}
// 创建一个头节点，默认指向自身
createHead() {
let head = new Node();
head.type = "head";
head.left = head;
head.right = head;
head.up = head;
head.down = head;
this.head = head;
}
// 从节点最少的列开始
getLeastColHead() {
let head = this.head;
let cur = head.right;
let min = Infinity;
let leastColHead = cur;
while (head !== cur) {
let len = this.getACol(cur).length;
if (len < min) {
leastColHead = cur;
min = len;
}
cur = cur.right;
}
return leastColHead;
}
// 回溯寻找答案
dance() {
let colHead = this.getLeastColHead();
if (colHead === this.head) {
return true;
}
let deepCount = this.getACol(colHead).length;
if (deepCount === 0) {
return false;
}
let cur = colHead.down;
while (colHead !== cur) {
this.ans.push(cur.row);
let nodes = this.remove(colHead, cur);
this.removeNodes.push(nodes);
let hasAns = this.dance();
if (hasAns) return true;
this.ans.pop();
let nodes2 = this.removeNodes.pop();
this.recovery(nodes2);
cur = cur.down;
}
return false;
}
// 将删除的节点进行恢复
recovery(recoveryNodes) {
let { allRemoved, allColHead } = recoveryNodes;
for (const node of allRemoved) {
this.recoveryNodeVertical(node);
}
for (const colHead of allColHead) {
this.recoveryNodeHorizontal(colHead);
}
}
/**
* 先拿到一行，这行中节点所属的每列需要删除，
* 每列对应着每行，在上下节点中删除
*/
remove(colHead, curVisite) {
let allRemoved = new Set();
let allColHead = new Set([colHead]);
let rows = this.getARow(curVisite);
for (const row of rows) {
let colHead = this.columnHead[row.col];
allColHead.add(colHead);
let cols = this.getACol(colHead);
for (const nodeCol of cols) {
allRemoved.add(nodeCol);
let rows2 = this.getARow(nodeCol);
for (const node of rows2) {
allRemoved.add(node);
}
}
}
for (const node of allRemoved) {
this.removeNodeVertical(node);
}
for (const node of allColHead) {
this.removeNodeHorizontal(node);
}
return { allRemoved, allColHead };
}
// 将节点从垂直删除 up、down
removeNodeVertical(cur) {
cur.up.down = cur.down;
cur.down.up = cur.up;
}
// 将节点从垂直恢复
recoveryNodeVertical(cur) {
cur.up.down = cur;
cur.down.up = cur;
}
// 将节点从水平删除 left、right
removeNodeHorizontal(cur) {
cur.left.right = cur.right;
cur.right.left = cur.left;
}
// 将节点从水平恢复
recoveryNodeHorizontal(cur) {
cur.left.right = cur;
cur.right.left = cur;
}
}
再写一个测试类来验证一下结果。
class TestCase {
constructor() {
for (const item of this.testData) {
let matrix = [];
let { X, S } = item.input;
for (const row of S) {
let arr = new Array(X.length).fill(0);
for (const n of row) {
arr[X.indexOf(n)] = 1;
}
matrix.push(arr);
}
let dlx = new DanceLink(matrix);
console.log(dlx.ans, item.output);
}
}
testData = [
{
input: {
X: [1, 3, 5, 8, 9, 17, 119],
S: [
[5, 9, 17], // 0
[1, 8, 119],
[3, 5, 17],
[1, 8], // 3
[3, 119], // 4
[8, 9, 119],
],
},
output: [0, 3, 4],
},
{
input: {
X: [1, 2, 3, 4, 5, 6],
S: [
[1, 3, 5],
[2, 4],
[2, 3, 4, 5, 6],
[2, 4, 6],
],
},
output: [0, 3],
},
{
input: {
X: [1, 2, 3, 4, 5, 6, 7],
S: [
[1, 4, 7],
[1, 4],
[4, 5, 7],
[3, 5, 6],
[2, 3, 6, 7],
[2, 7],
],
},
output: [1, 3, 5],
},
{
input: {
X: [1, 2, 3, 4, 5, 6, 7],
S: [
[1, 4, 7],
[1, 5],
[4, 5, 7],
[3, 5, 6],
[2, 3, 6, 7],
[2, 7],
],
},
output: [],
},
];
}
new TestCase();良心出品的参考文章
不花更多的时间，我不会比以下的文章写的更好，推荐阅读。
跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题
《舞蹈链 – JavaScript 实现》有一个想法