直接上代码
代码里面注释很清晰
传说中的最难数组大概是在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();
}
相关推荐
递归回溯算法是一种基于深度优先搜索（DFS）的策略，它适用于解决约束满足问题，如数独。该算法的特点是尝试填充数独格子，并在遇到矛盾时回退到上一步，尝试其他可能的值。以下是对递归回溯算法解决数独的详细步骤...
在这个js版数独游戏中，开发者利用JavaScript的特性创建了一个交互式的数独解决方案。 首先，游戏界面的实现通常涉及到HTML5的Canvas或DOM元素操作。开发者可能使用了CSS来设计布局，使游戏界面美观且用户友好。...
请设计一个数独游戏，要求包括： 1， 基本要求：能按照不同难度级别设置随机的初始数独，允许用户在空格处填入数字完成数独游戏；...不使用回溯算法快速求解数独。 建议使用JavaScript／HTML／CSS编程，使用回溯算法。
总的来说，《JS数独 v1.0.2》项目是一个很好的学习和实践JavaScript编程、前端开发以及算法设计的实例。通过分析和理解这个项目，开发者可以提升在实际开发中处理类似问题的能力，同时增强对JavaScript语法、浏览器...
总的来说，JavaScript实现的数独求解算法结合了逻辑推理、回溯搜索和位运算等技术，能够有效地解决各种难度的数独问题。通过深入理解数独的规则并巧妙地利用编程技巧，我们可以创建出高效且准确的求解程序。
数独求解器js 使用回溯算法的简单数独求解器。 最终它将支持所有常规boxsize。安装首先确保已安装nodejs，然后在projects目录中运行以下命令npm install测验npm install mocha -gcd app/solver mocha sudoku_solver_...
1. 初始化：首先，随机生成一个标准数独解决方案，然后进行部分填充，形成游戏盘面。为了保证填充的合法性，可以使用回溯算法。 2. 用户操作：当用户点击单元格时，JavaScript监听事件并获取选中的数字，然后更新...
在实际的面试中，熟悉并能熟练运用递归和回溯算法，对于解决类似解数独这样的复杂问题至关重要。这不仅能展现你的编程技巧，还能体现出你在面对复杂逻辑时的思考能力。因此，对于打算进入IT行业的求职者来说，熟练...
3. 回溯算法或递归解决问题的思路。 4. jQuery库的使用，以便更高效地操作DOM和处理用户交互。 最后，压缩包中的“shudu”文件可能是项目的源代码，包括HTML、CSS（样式表）和JavaScript文件。通过分析这些文件，...
通过上述思路和方法，JavaScript可以高效地遍历数独问题的解决方案，利用回溯算法的特点避免无效的尝试，大大减少了计算量。在实际编程时，还需注意代码的优化和调试，确保算法的正确性和效率。
在这个上下文中，`sudo_xx.c`可能包含了实现数独求解器的函数，这些函数可能采用了回溯法、递归或其它算法来确保填入的数字符合数独规则。数独求解器可以自动填充未完成的数独盘面，帮助用户找到唯一解决方案。 总...
回溯算法是解决数独问题的一种经典方法。它通过递归的方式逐步填入数字，如果发现当前填入的数字导致后续无法满足数独的规则，则回退（回溯）至上一步选择另一个数字。该过程反复进行，直到找到所有可能的解或者确认...
经典的回溯法（Backtracking）常用于解决数独问题，这是一种深度优先搜索策略，当遇到无法填入数字的情况时，会回溯并尝试其他可能性。 7. **动画效果**：为了增加用户体验，JavaScript还可以添加一些动画效果，如...
总的来说，JavaScript实现的数独解题算法通过模拟人类解题思路，结合回溯法，有效地解决了数独问题。它不仅考虑了数据初始化、猜测验证，还实现了友好的用户交互界面，使得用户能够方便地输入、解决和查看数独题目。
数独是一种广受欢迎的逻辑推理游戏，它基于9x9的格子，分为9个3x3的小九宫格。每个小九宫格、每行、每列都必须填入1到9...通过这一项目，开发者不仅可以提升JavaScript编程技能，还能深入理解逻辑推理和问题解决策略。
一般而言，数独的解决方案可以通过回溯法或者基于约束满足问题（CSP）的算法来实现。回溯法是一种试探性的解题方法，当遇到矛盾时会退回一步，尝试其他可能的值。CSP算法则更侧重于定义变量、约束和搜索策略，通过...
JavaScript 版数独游戏，数独是一种数字游戏，在9×9方... 数独游戏的原理算法：采用试填加回溯的方法，先得到一个完整数独，然后根据难度设置，从这个完整的数独中，挖去一定数量的数字，得到一个游戏局面，内祥……
5. **回溯算法**：对于自动求解功能，可以使用回溯算法来搜索所有可能的解决方案。当尝试填充一个数字导致违反规则时，回溯到上一步，尝试下一个可能的数字。 6. **界面效果**：为了让游戏体验更好，开发者可能会...
在这个项目中，Python可能被用来编写数独游戏的逻辑算法，包括生成随机数独谜题、检查解的正确性以及解决数独问题等功能。 2. **数独算法**：生成数独谜题需要一定的数学和逻辑技巧。一种常见的方法是回溯法，通过...
在JavaScript中，实现数独求解算法通常需要两种策略：回溯法和直观法（如X-Wing、XY-Wing、 swordfish等）。回溯法是一种试探性的方法，当填入数字后发现不符合规则时，会回退并尝试其他可能的数字，直到找到正确的...