直接上代码代码里面注释很清晰传说中的最难数组大概是在20ms左右解决 ```js /** * 数独算法 */ 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; ``` 调用方法 ```js 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(); } ```