我是stackoverflow的新手。我搜索了相关的问题，但似乎没有人回答我的问题。我在计算机科学的第一个学期，目前正在修读编程1课程。我们只在整个课程中使用JavaScript，因此JavaScript是迄今为止我所知道的唯一编程语言。因此，我对整个编程的理解相当有限，直观或其他方面。英语也不是我的第一语言，请原谅我的错误。
尽管如此，这是我的问题：我需要编写一个数独求解器。我实际上成功地编写了一个被认为是“简单”的数独的解算器。这需要几分之一秒，所以我对结果非常满意。问题是：有一些无效的sudokus，即那些被认为是“硬”的人。不用说，解算器需要为所有的sudokus工作。以下是“简单”和“硬”数据板的示例代码片段，以及我的求解器的代码。我试图尽可能地注释来描述功能，但显然存在一个问题，因为它无法解决困难问题。它实际上陷入无限循环。
var easyBoard = [
[1,0,0,3,0,0,9,5,2],
[0,4,0,6,0,0,1,0,0],
[3,0,0,1,0,0,0,0,0],
[0,6,4,7,2,0,0,1,0],
[8,7,0,9,0,6,0,2,4],
[0,2,0,0,8,5,7,6,0],
[0,0,0,0,0,1,0,0,7],
[0,0,7,0,0,9,0,4,0],
[2,3,9,0,0,4,0,0,1]
];
var hardBoard = [
[4,0,0,6,0,7,0,8,5],
[0,0,0,0,0,0,6,0,0],
[0,0,7,0,0,0,0,0,0],
[0,5,0,0,0,3,0,0,4],
[3,7,0,0,0,8,0,0,0],
[6,0,0,2,0,0,0,0,0],
[8,0,0,0,0,0,3,1,0],
[0,3,1,0,4,9,0,0,0],
[0,0,0,0,0,0,0,0,9]
];
var solve = function (board) {
var empty = []; // We create an array for the 1x1 squares with no value, so we can call upon them with ease later on.
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
if (board[i][j] === 0) {
empty.push([i,j]);
}
}
}
for (var i = 0; i < empty.length;) { // We check every possible value for all empty 1x1 squares.
var row = empty[i][0]; // Used for row and 3x3 square checks
var column = empty[i][1]; // Used for column and 3x3 square checks
var value = board[row][column] + 1; // We start at 1, because obviously 0 is not a Sudoku value.
var found = false; // We assume the value is invalid, unless it passes all three tests.
while (!found && value <= 9) { // As long as the value is invalid, we increase by one until it reaches more than 9.
var equal = false; // We assume for now that the value is not equal to any other in its row, column or 3x3 square.
for (var y = 0; y < 9; y++) {
if (board[row][y] === value) {
equal = true;
}
}
for (var x = 0; x < 9; x++) {
if (board[x][column] === value) {
equal = true;
}
}
for (var x = 3*Math.floor(row/3); x < 3*Math.floor(row/3)+3; x++) {
for (var y = 3*Math.floor(column/3); y < 3*Math.floor(column/3)+3; y++) {
if (board[x][y] === value) {
equal = true;
}
}
}
if (!equal) { // If the value is not equal to any other in its row, column or 3x3 square, it is valid.
found = true; // We have found a valid value, for now.
board[row][column] = value; // We assign said value to the corresponding board 1x1 square, for now.
i++; // We then move on to the next empty 1x1 square.
}
else {
value++; // If the value is invalid, we simply try the next possible value.
}
}
if (!found) { // If, from 1 to 9, the value is invalid, it means the one before is invalid.
board[row][column] = 0; // We then re-assign an empty value to the 1x1 square, before backtracking.
i--; // We go back to the previous 1x1 square to try a different value.
}
}
};
// test routines
var clone2 = array => array.slice().map( row=>row.slice());
function easyTest() {
var board = clone2( easyBoard);
solve( board);
console.log( "easy board solution:");
console.log( board);
}
function hardTest() {
var board = clone2( hardBoard);
solve( board);
console.log( "hard board solution:");
console.log( board);
}<button type="button" onclick="easyTest()">Easy Test</button>
<button type="button" onclick="hardTest()">Hard Test</button>代码适用于第一个，但不适用于第二个。是因为回溯/暴力算法对于“硬”数独游戏还不够快？难道它只需要几个小时或者我的代码中是否存在问题导致第一块板出现问题，而不是第二块板出现问题？
如果有些事情不清楚，我很抱歉，我发誓我已经尝试了解其他类似问题的答案，但所有这些问题包含了几个概念或操作符/对象或我不知道的任何内容。如果有人可以在我的代码中指出问题，并告诉我是否可以用它解决第二块板，或者我是否需要另一种方法。
非常感谢你提前！
P.S。：很多人都在谈论JavaScript中的对象，或者面向对象的编程。我不知道它是否相关，但我们还没有看到任何相关内容。
第二个在~10秒内在我的电脑上得到解决
[4, 9, 3, 6, 1, 7, 2, 8, 5]
[2, 8, 5, 9, 3, 4, 6, 7, 1]
[1, 6, 7, 8, 5, 2, 4, 9, 3]
[9, 5, 8, 1, 6, 3, 7, 2, 4]
[3, 7, 2, 4, 9, 8, 1, 5, 6]
[6, 1, 4, 2, 7, 5, 9, 3, 8]
[8, 4, 9, 5, 2, 6, 3, 1, 7]
[5, 3, 1, 7, 4, 9, 8, 6, 2]
[7, 2, 6, 3, 8, 1, 5, 4, 9]
有些事情是不对的。您发布的代码在1800毫秒内解决了“硬”板。经过一些优化后，我在用于测试的同一台Windows笔记本电脑上将其降低到大约300毫秒。
我在这里提供优化版本来测试uni计算机是否可以运行它，如果你想尝试。如果您仍在使用强力解决方案，我非常谨慎地建议这样做，但它肯定是您的代码的一个版本！
最后，您可以测试uni计算机是否只是不允许暴力算法有足够的时间来完成（或在其运行的自定义JS引擎中实现指令“步骤”限制）。
function emptyCells( board) {
var empty = [];
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
if (board[i][j] === 0) {
var boxRow = 3* Math.floor( i/3);
var boxCol = 3* Math.floor( j/3);
empty.push([i,j, boxRow, boxCol]);
}
}
}
return empty;
}
function isUnique( board, empty, value) {
var row, col;
// test row
row = board[empty[0]];
for( col = 0; col < 9; ++ col) {
if( value == row[col]) {
return false;
}
}
// test col
col = empty[1];
for( var row = 0; row < 9; ++row) {
if( value == board[ row][col]){
return false;
}
}
// test box
var boxRow = empty[2];
var boxCol = empty[3];
for( var i = 3; i--;) {
row = board[ boxRow++];
for( var j = 3; j--;) {
if( row[boxCol + j] == value) {
return false;
}
}
}
return true;
}
var solve = function (board) {
var empty = emptyCells( board);
nextEmpty:
for (var i = 0; i < empty.length;) { // We check every possible value for all empty 1x1 squares.
var row = empty[i][0]; // Used for row and 3x3 square checks
var column = empty[i][1]; // Used for column and 3x3 square checks
var value = board[row][column] + 1; // We start at 1, because obviously 0 is not a Sudoku value.
var cell = empty[i];
while (value <= 9) { // test values up to 9.
if( isUnique( board, cell, value)) {
board[row][column] = value; // We assign said value to the corresponding board 1x1 square, for now.
i++; // Move on to the check next empty cell.
continue nextEmpty;
}
value++; // If the value is invalid, we simply try the next possible value.
}
board[row][column] = 0;
if( i == 0) { // board is not solvable
return null;
}
i--; // We go back to the previous 1x1 square to try a different value.
}
return board;
};
var board = [
[4,0,0,6,0,7,0,8,5],
[0,0,0,0,0,0,6,0,0],
[0,0,7,0,0,0,0,0,0],
[0,5,0,0,0,3,0,0,4],
[3,7,0,0,0,8,0,0,0],
[6,0,0,2,0,0,0,0,0],
[8,0,0,0,0,0,3,1,0],
[0,3,1,0,4,9,0,0,0],
[0,0,0,0,0,0,0,0,9]
];
var t0 = Date.now();
solve(board);
var t1 = Date.now();
console.log( " in " + (t1-t0) + "ms");
console.log( board.map( row=> row.join(',')).join('\n'));
console.log( "\n solved in " + (t1-t0) + "ms");