递归:JS中的回溯数独求解器
Recursion: Backtracking sudoku solver in JS
我无法让这个递归算法工作。它应该解决一个数独网格(一个由int组成的2d数组)。我在Java中也做了同样的事情(当然是OOP),它运行得很好。但在JS中则不然。网格中的值不会更改,也不会达到基本情况。该算法是solveSudoku——基本情况是,当它在网格中搜索但没有找到任何"空"单元格(值为"0")时。
我已将所有代码放在一个文件中。你能发现错误吗?我已经试了一个星期了,即将放弃这个小项目。
"use strict";
var grid = [
[0,0,8,4,0,3,5,0,6],
[0,0,3,1,0,2,0,0,4],
[0,4,5,7,0,0,0,9,0],
[6,9,0,0,0,5,0,0,7],
[0,8,0,0,0,0,0,5,0],
[4,0,0,3,0,0,0,1,8],
[0,7,0,0,0,6,2,4,0],
[1,0,0,5,0,7,8,0,0],
[8,0,6,9,0,1,3,0,0]
];
// recursive algo
function solveSudoku(grid, row, col) {
var cell = findUnassignedLocation(grid, row, col);
row = cell[0];
col = cell[1];
// base case: if no empty cell
if (row == -1) {
console.log("solved");
return true;
}
for (var num = 1; num <= 9; num++) {
if ( noConflicts(grid, row, col, num) ) {
grid[row][col] = num;
if ( solveSudoku(grid, row, col) ) {
return true;
}
// mark cell as empty (with 0)
grid[row][col] = 0;
}
}
// trigger back tracking
return false;
}
function findUnassignedLocation(grid, row, col) {
var done = false;
var res = [-1, -1];
while (!done) {
if (row == 9) {
done = true;
}
else {
if (grid[row][col] == 0) {
res[0] = row;
res[1] = col;
done = true;
}
else {
if (col < 8) {
col++;
}
else {
row++;
col = 0;
}
}
}
}
return res;
}
function noConflicts(grid, row, col, num) {
return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num);
}
function isRowOk(grid, row, num) {
for (var col = 0; col < 9; col++)
if (grid[row][col] == num)
return false;
return true;
}
function isColOk(grid, col, num) {
for (var row = 0; row < 9; row++)
if (grid[row][col] == num)
return false;
return true;
}
function isBoxOk(grid, row, col, num) {
row = (row / 3) * 3;
col = (col / 3) * 3;
for (var r = 0; r < 3; r++)
for (var c = 0; c < 3; c++)
if (grid[row + r][col + c] == num)
return false;
return true;
}
function printGrid(grid) {
var res = "";
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
res += grid[i][j];
}
res += "'n";
}
console.log(res);
}
很难找到。。。但问题出在
row = (row / 3) * 3;
col = (col / 3) * 3;
Javascript只使用浮点数,所以这并不是在做你认为正在做的事情。
解决方案是
row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;
在javascript中,数字不能强制为整数,所以像(a / 3) * 3
这样的东西与a
没有什么不同。在isBoxOk
中,您需要更换
row = (row / 3) * 3;
col = (col / 3) * 3;
通过
row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;
此外,我认为您可以简化findUnassignedLocation
函数:
function findUnassignedLocation(grid, row, col) {
for (; row < 9 ; col = 0, row++)
for (; col < 9 ; col++)
if (grid[row][col] == 0)
return [row, col];
return [-1, -1];
}
相关文章:
- 可以't让我的if语句处理js中的html表单输入
- 使用agility.js进行页面布局和合成
- 使用Clipboard.js复制span文本
- 使用JS如何动态更改显示的html文件中的文本背景颜色
- 强制模板刷新ember.js
- 如何编写HTML输入的JS内联
- Angular JS IE9 Hashbang url rewriting
- 使用JS将数组转换为json对象
- Node.js v6.2.0类扩展不是函数错误
- 当js函数's已执行
- 要求未定义JS回调参数
- 在自定义mean.io包中使用angular-chart.js作为依赖项
- 无法在数据endVal中设置值=“”;{{ucount}}”;使用Angular JS的CountUp
- 如何从Java/scala调用js美化程序
- 如何更改<svg>标记为<img>用js标记
- 如何使用 node.js 比较两个 json 数组
- chrome扩展:尽管运行了at:documentidle,js脚本还是过早启动
- 节点Js:How to catch a“;没有这样的文件或目录“;读取线模块出错
- Selectize.js:如何对整数值的选项进行排序
- 递归:JS中的回溯数独求解器