我试图用Java编写Sudoku Solver。该代码确实解决了问题,但仍然存在一些空白。我使用Javascript,回溯和递归。
在第一个函数中,我检查我在空白点(0)上的数字是可能的,而在第二个函数中,我呼叫第一个函数检查空白点,并尝试在该点上输入1到9之间的数字
有人可以看到我在做什么错吗?
const userInput = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
];
function possible(y, x, n) {
for (let i = 0; i <= 8; i++) {
if (userInput[y][i] === n) {
return false;
}
}
for (let i = 0; i <= 8; i++) {
if (userInput[i][x] === n) {
return false;
}
}
let xSquare = Math.floor(x / 3) * 3;
let ySquare = Math.floor(y / 3) * 3;
for (let i = 0; i <= 2; i++) {
for (let j = 0; j <= 2; j++) {
if (userInput[ySquare + i][xSquare + j] === n) {
return false;
}
}
}
return true;
}
function solve() {
for (let y = 0; y <= 8; y++) {
for (let x = 0; x <= 8; x++) {
if (userInput[y][x] === 0) {
for (let n = 1; n <= 9; n++) {
if (possible(y, x, n)) {
userInput[y][x] = n;
solve();
}
}
}
}
}
}
您正在编写回溯算法,但是这里没有回溯。
要回溯,您需要将无法扩展到已解决状态的像元清零,并在所有可能性用尽后将false返回到父状态。
此外,函数最好采用参数并返回值,而不要改变全局状态。
应用这些最小的修改将得出以下结果。仍有改进的空间;例如,solve
功能必须反复“搜索”下一个开放正方形。
function possible(board, y, x, n) {
for (let i = 0; i <= 8; i++) {
if (board[y][i] === n) {
return false;
}
}
for (let i = 0; i <= 8; i++) {
if (board[i][x] === n) {
return false;
}
}
const xSquare = Math.floor(x / 3) * 3;
const ySquare = Math.floor(y / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[ySquare+i][xSquare+j] === n) {
return false;
}
}
}
return true;
}
function solve(board) {
for (let y = 0; y < 9; y++) {
for (let x = 0; x < 9; x++) {
if (board[y][x] === 0) {
for (let n = 1; n <= 9; n++) {
if (possible(board, y, x, n)) {
board[y][x] = n;
if (solve(board)) return board;
board[y][x] = 0;
}
}
return false;
}
}
}
return board;
}
const puzzle = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
];
console.log(solve(puzzle));