直接上代码
代码里面注释很清晰
传说中的最难数组大概是在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();
}
相关推荐
自定义数独题，通过递归回溯算法一键破解，可选择快速破解或可视化破解。使用说明已写在页面，直接运行index.html即可开始
请设计一个数独游戏，要求包括： 1， 基本要求：能按照不同难度级别设置随机的初始数独，允许用户在空格处填入数字完成数独游戏；...不使用回溯算法快速求解数独。 建议使用JavaScript／HTML／CSS编程，使用回溯算法。
数独求解器js 使用回溯算法的简单数独求解器。 最终它将支持所有常规boxsize。安装首先确保已安装nodejs，然后在projects目录中运行以下命令npm install测验npm install mocha -gcd app/solver mocha sudoku_solver_...
JavaScript 版数独游戏，数独是一种数字游戏，在9×9方... 数独游戏的原理算法：采用试填加回溯的方法，先得到一个完整数独，然后根据难度设置，从这个完整的数独中，挖去一定数量的数字，得到一个游戏局面，内祥……
数独规则 数独游戏，经典的为9×9=81个单元格组成的九宫格，同时也形成了3×3=9个小九宫格，要求在81个小单元格中填入数字1~9，并且数字在每行每列及每个小九宫格中都不能重复。 数独技巧 直观法 候选数法 相关...
一个简单JavaScript数独求解器 这是一个使用HTML，CSS和JavaScript的简单JavaScript数独求解器。 这里使用一种流行的回溯算法来解决这个难题。
使用回溯算法，以最快的速度提供数独求解器和生成器。 这是用C语言编写的本机node.js扩展。 安装 npm install sudoku-c 用法 var sudoku = require ( 'sudoku-c' ) ; // generate random grid - an array of 81 ...
一个有趣的数独游戏，用 vanilla javascript 编写。 现在就开始在上！ 编译 $ gulp build 您将在名为build/的文件夹中找到build/ 。 测试 $ gulp test或$ make test-all 执行 有一个client/js/app.js作为 UI 和数独...
CP476-最终项目我们如何编译：后端sudoku.html 我们使用回溯和AC3算法来解决数独难题。 以及一个随机的拼图生成器，以不断为用户提供新的拼图。app.py 该python函数包含已实现的flask功能。 我们使用get和post方法将...
它使用递归回溯算法来解决数独谜题。 因为 JavaScript 是单线程的，所以递归是在与主线程通信的工作线程（web worker）中完成的。 然后主线程可以更新 GUI 并为递归设置动画。 享受！兼容性 Chrome 31+ 火狐 31+ ...
这里使用的算法是一个简单的回溯算法。 它首先检查拼图是否有效，然后转到每个空方格并迭代从 1 到 9 的数字。如果与当前数字没有矛盾，它将移动到网格上的下一个空白点（注意该算法的迭代顺序是从左到右，从上到下...
数独解算器 :globe_with_meridians: 数独是一个算法项目，它是使用回溯构建的。使用的技术栈 :laptop: 在这个项目中，我使用了以下技术堆栈。 HTML： JavaScript： CSS： 如何运行项目 :bookmark_tabs: 您也可以一瞥...
Rails API从精选的“种子”谜题中生成数独谜题，并使用回溯算法解决每个谜题。 它使用React-Redux，通过一个干净的响应式UI来显示来自Rails API的数据。 安装 要设置此Web应用程序的本地实例，请克隆此存储库。 请...
可视化器（以各种速度）用于回溯算法，用于求解有效的数独板。 步骤执行 安装依赖项 npm install 运行开发服务器 npm run dev 上的服务器（检查webpack.config.js） 没有可视化器的优化求解器位于“优化”分支中
数独游戏matlab代码我的专案 该页面包含我到目前为止完成的所有项目（或实践代码）的链接。 项目 关联 语 AuthAPI Express框架和MongoDB 节点JS QwikCheck API基于PHP的Rest-API PHP QwikCheck APP Android应用 ...
它还包括另一种模式，玩家可以使用我们的回溯算法来解决任何给定的数独难题。 大多数难题可以在几秒钟之内解决，并且所花费的时间和递归步骤都将输出到屏幕上。 最困难的一个过程耗时超过10分钟，具有超过6000万个...
JSudoku是数独游戏的Java版本。 回溯算法根据Sudoku-Puzzle JavaScript照顾随机谜题。 可选地，JSudoku生成X-Sudoku拼图。
数独检查WinJS 这是我们可以在浏览器中玩的数独游戏的前端实现。 可以根据您所需的难度级别随机生成拼图。 有一种算法可以为屏幕上的给定难题生成解决方案。 这允许提示（填充一个正方形... 该算法使用回溯来解决难题。