nodejs使用回溯算法解决数独问题
直接上代码 代码里面注释很清晰 传说中的最难数组大概是在20ms左右解决
/**
* 数独算法
*/
class Sudoku {
constructor({
display = false,
sudokuMap = []
}) {
// 是否展示算法过程
this.display = display;
// 原始数独数组
this.sudokuMap = sudokuMap;
// 回溯数组
this.stacks = [];
// 是否已经解答完成
this.resolved = false;
this.allTimes = 0; // 所有的循环次数统计
this.dataMap = new Map();
console.time('init:time');
this.init();
console.timeEnd('init:time');
this.testRuleTimes = {
ok: 0,
fail: 0,
};
this.currentOrder = 0 ;
}
/**
* 初始化确定每个可填写的格子可以的填入的数值,做成一个MAP
*/
init() {
let exsitTimes = {};
for(let i = 0 ; i < 9 ; i++ ) {
for(let j = 0 ; j < 9; j ++) {
this.allTimes++;
let node = this.sudokuMap[i][j];
if(node === 0) {
this.testMayFill(i, j);
}else{
// 记录每个数字出现的次数
exsitTimes[node] ? exsitTimes[node]++ : exsitTimes[node]=1;
}
}
}
// 进行一次可填入数字的排序
// 回溯的时候找下一个节点的时候从小到大进行搜索
let data = [];
for(let [key, value] of this.dataMap) {
this.allTimes++;
data.push({
x: parseInt(key.split('-')[0]),
y: parseInt(key.split('-')[1]),
value: value,
// value: value.sort((a, b) => {
// exsitTimes[a] - exsitTimes[b] > 0 ? 1:-1;
// })
})
}
//
// data.sort(function(a , b) {
// return a.value.length > b.value.length ? 1 : -1;
// })
//
// data.reverse();
this.orders = data;
}
/**
* 设置当前格子可能填入的值
*/
testMayFill(x, y) {
let mayFillNumber = new Set([1,2,3,4,5,6,7,8,9]);
// 横向查找
for (let i = 0; i < 9; i++) {
this.allTimes++;
let node = this.sudokuMap[i][y];
if (mayFillNumber.has(node)) {
mayFillNumber.delete(node);
}
}
// 纵向查找
for (let i = 0; i < 9; i++) {
this.allTimes++;
let node = this.sudokuMap[x][i];
if (mayFillNumber.has(node)) {
mayFillNumber.delete(node);
}
}
/* x为n所在的小九宫格左顶点竖坐标 */
let startX = Math.floor(x / 3) * 3;
/* y为n所在的小九宫格左顶点横坐标 */
let startY = Math.floor(y / 3) * 3;
/* 判断n所在的小九宫格是否合法 */
for (let i = startX; i < startX + 3; i++)
{
for (let j = startY; j < startY + 3; j++)
{
this.allTimes++;
let node = this.sudokuMap[i][j];
if (mayFillNumber.has(node)) {
mayFillNumber.delete(node);
}
}
}
this.dataMap.set(`${x}-${y}`, [...mayFillNumber]);
}
/**
* 如果某一个方格填写的测试数据能够经过校验
* 就寻找到一下个需要填写数的方格
* 这个方格的不能已经填写过数字
* 找到这个方格的坐标返回
*/
getNextPoint() {
let currentStack = this.stacks[this.stacks.length - 1];
let ret = {
x: -1,
y: -1,
value: 1,
}
this.currentOrder++;
let nextValue = this.orders[this.currentOrder];
if(!nextValue) {
this.resolved = true;
return ret;
// break;
}
ret.x = nextValue.x;
ret.y = nextValue.y;
ret.value = nextValue.value[0];
return ret;
}
/**
* 获取初始节点
* 初始节点为第一个不为0的方格
* 0 0 坐标节点上面可能已经填写了数字
*/
getFirstPoint() {
let ret = {
x: this.orders[0].x,
y: this.orders[0].y,
value: this.orders[0].value[0],
}
return ret;
}
/**
* 程序入口
* 开始执行
*/
start() {
let s = new Date();
// 清空命令行
let {
resolved: resolved,
stacks: stacks
} = this;
if(this.display) {
process.stdout.cursorTo(0, 0);
process.stdout.clearScreenDown();
}
// 如果记录填写数字的历史表为空,直接找第一个可以填写的方格填入
//
stacks.push(this.getFirstPoint());
while (resolved === false) {
let cStack = stacks[stacks.length - 1];
if (this.display) {
process.stdout.cursorTo(0,0);
console.log(this.sudokuMap);
console.log('已经填入数量',stacks.length);
console.log(`当前耗时${new Date()-s}ms`);
}
/**
* 结束判断
* 如果获取不到需要填写的方格
* 说明已经全部填写完成
*/
if (cStack.x === -1 && cStack.y === -1) {
resolved = true;
console.log(this.sudokuMap);
console.log('已经填入数量',stacks.length);
console.log(`当前耗时${new Date()-s}ms`);
console.log(this.testRuleTimes);
console.log('所有For循环次数',this.allTimes);
return this;
}
let valid = this.testRules(cStack);
if (valid) {
/**
* 填写的数字满足校验
* 先设置数独数组的值为当前测试的值
* 然后寻找下一个方格
*/
this.sudokuMap[cStack.x][cStack.y] = cStack.value;
stacks.push(this.getNextPoint());
} else {
/**
* 如果校验不通过
* 将当前方格的测试数据清空
*
* 在当前格子进行测试别的值
* 从1到9依次测试
* 如果全部失败
* 回溯到上一级
*
*/
//this.sudokuMap[cStack.x][cStack.y] = 0;
// console.log(stacks);
this.rollback();
}
};
}
/**
* 回退
* 取出数组最后一次填入的数据
* 1、如果当前位置是起始位置
* 并且值小于9
* 直接给这个值+1,并且推进堆栈数组中
* 2、如果不是起始位置
* 2.1 判定数值是否小于9,如果小于9直接进行+1并且推入堆栈进行计算
* 2.2 如果已经是9了,等于说这个格子填写任何数都不合适,所以需要继续回溯到上一个步骤
*/
rollback() {
let {
stacks, dataMap
} = this;
let currentStack = stacks.pop();
this.sudokuMap[currentStack.x][currentStack.y] = 0;
let cOrder = this.orders[this.currentOrder];
if(currentStack.value === cOrder.value[cOrder.value.length-1]) {
this.currentOrder--;
this.rollback()
}else{
let orderIndex = cOrder.value.indexOf(currentStack.value);
currentStack.value = cOrder.value[orderIndex+1];
stacks.push(currentStack);
}
}
/**
* 判断填入的数值是否满足数独规则
* 1、横向扫描,当前填入的数字是否有重复
* 2、纵向扫描,当前填入的数字是否有重复
* 3、扫描当前格子所在的3X3的小格子中是否有重复数字
*/
testRules(stack) {
let {
x: x,
y: y,
value: val
} = stack;
let ret = true;
let found = false;
for(let i = 0 ; i < 9 ; i++) {
this.allTimes++;
let node = this.sudokuMap[i][y];
if (node === val) {
this.testRuleTimes.fail++;
return false;
}
}
for(let j = 0 ; j < 9 ; j++) {
this.allTimes++;
let node = this.sudokuMap[x][j];
if (node === val) {
this.testRuleTimes.fail++;
return false;
}
}
/* x为n所在的小九宫格左顶点竖坐标 */
let startX = Math.floor(x / 3) * 3;
/* y为n所在的小九宫格左顶点横坐标 */
let startY = Math.floor(y / 3) * 3;
/* 判断n所在的小九宫格是否合法 */
for (let i = startX; i < startX + 3; i++)
{
for (let j = startY; j < startY + 3; j++)
{
this.allTimes++;
let node = this.sudokuMap[i][j];
if (node === val) {
this.testRuleTimes.fail++;
return false;
}
}
}
if(ret) {
this.testRuleTimes.ok++;
}else{
this.testRuleTimes.fail++;
}
return ret;
}
}
module.exports = Sudoku;
调用方法
let maps = {
easy: [
[ 0 , 1 ,0 , 0 ,0, 0 , 7 , 0 , 0 ],
[ 5 ,0 ,0 , 0 , 7, 3 , 0 , 0 , 0 ],
[0 ,0 ,0 , 9 , 2, 8 , 0 , 0 , 5 ],
[0 ,0 , 3 , 0 , 4, 0 , 0 , 8 , 6 ],
[0 , 9 ,0 , 0 ,0, 0 , 0 , 0 , 4 ],
[0 , 2 ,0 , 0 ,0, 0 , 9 , 0 , 7 ],
[0 , 8 ,0 , 0 ,0, 2 , 0 , 0 , 1 ],
[ 9 ,0 , 6 , 0 ,0, 0 , 0 , 0 , 3 ],
[0 ,0 ,0 , 0 ,0, 0 , 0 , 6 , 0 ]
],
normal: [
[0 , 0 ,0 , 0 ,0, 0 , 2 , 0 , 0 ,],
[0 , 9 , 8 , 0 ,0, 0 , 4 , 0 , 0 ,],
[ 4 , 0 ,0 , 0 , 2, 0 , 3 , 0 , 0 ,],
[0 , 4 ,0 , 9 ,0, 0 , 0 , 0 , 6 ,],
[ 5 , 0 ,0 , 1 ,0, 0 , 7 , 3 , 0 ,],
[0 , 0 ,0 , 0 ,0, 6 , 0 , 5 , 0 ,],
[ 9 , 8 , 4 , 0 ,0, 1 , 6 , 0 , 0 ,],
[0 , 0 ,0 , 0 ,0, 4 , 0 , 0 , 3 ,],
[0 , 2 ,0 , 0 , 9, 0 , 1 , 0 , 0 ,],
],
hard: [
[ 0 , 0 ,5 , 3 ,0, 0 , 0 , 0 , 0 ],
[ 8 , 0 ,0 , 0 ,0, 0 , 0 , 2 , 0 ],
[ 0 , 7 ,0 , 0 ,1, 0 , 5 , 0 , 0 ],
[ 4 , 0 ,0 , 0 ,0, 5 , 3 , 0 , 0 ],
[ 0 , 1 ,0 , 0 ,7, 0 , 0 , 0 , 6 ],
[ 0 , 0 ,3 , 2 ,0, 0 , 0 , 8 , 0 ],
[ 0 , 6 ,0 , 5 ,0, 0 , 0 , 0 , 9 ],
[ 0 , 0 ,4 , 0 ,0, 0 , 0 , 3 , 0 ],
[ 0 , 0 ,0 , 0 ,0, 9 , 7 , 0 , 0 ],
],
hard1: [
[8,0,0,0,0,0,0,0,0],
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]
]
}
for(let map in maps) {
let sdk = new Sudoku({
display: false, // 是否打印过程,打印的速度慢很多
sudokuMap: maps[map],
}).start();
}