javascript - 递归数独算法有效但返回错误
问题描述
对不起下面的代码转储......！
这个算法确实解决了数独难题（因为登录解决 if empty == -1 func）但是一旦所有递归展开，实际输出要么返回原始拼图字符串，要么返回 {error: 'Puzzle cannot解决'}。
我认为这可能是最终的迭代错误，但我已经重构和重组，直到我脸色发青，无法弄清楚为什么它在展开时没有返回成功的输出。
任何帮助将不胜感激。
class SudokuSolver {
validate(puzzleString) {
//console.log(puzzleString)
if (puzzleString.length === 0) {
return {
error: 'Required field missing'
}
}
if (puzzleString.length !== 81) {
return {
error: 'Expected puzzle to be 81 characters long'
}
}
if (!/^[0-9.]*$/.test(puzzleString)) {
return {
error: 'Invalid characters in puzzle'
};
}
return true
}
createBoard(puzzleString) {
//create a new row on 0th or 9th iteration
let puzzleBoard = [
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
let puzzle = puzzleString.split('');
let row = -1
for (let i = 0; i < puzzle.length; i++) {
if (i % 9 === 0) {
row++
}
puzzleBoard[row].push(puzzle[i])
}
return puzzleBoard
}
checkRowPlacement(board, row, column, value) {
for (let i = 0; i < 9; i++) {
if (board[row][i] == value) {
return {
valid: false,
conflict: 'row'
}
}
}
return {
valid: true
}
}
checkColPlacement(board, row, column, value) {
for (let i = 0; i < 9; i++) {
if (board[i][column] == value) {
return {
valid: false,
conflict: 'column'
};
}
}
return {
valid: true
};
}
checkRegionPlacement(board, row, column, value) {
let regionStartRow = parseInt(row / 3) * 3;
let regionStartCol = parseInt(column / 3) * 3;
for (let i = regionStartRow; i < regionStartRow + 3; i++) {
for (let j = regionStartCol; j < regionStartCol + 3; j++) {
if (board[i][j] == value) {
return {
valid: false,
conflict: 'region'
}
}
}
}
return {
valid: true
}
}
coordToBoard(input) {
let res = [];
// A1 -> A = 0, 1 = 0
res.push(input.toUpperCase().charCodeAt(0) - 65)
res.push(parseInt(input.charAt(1)) - 1)
return res
}
checkPlacement(puzzleString, coordinate, value) {
if (!puzzleString || !coordinate || !value) {
return {
error: 'Required field(s) missing'
}
}
if (this.validate(puzzleString) != true) {
return this.validate(puzzleString)
};
let coordSplit = coordinate.split('')
if (!/[A-Ia-i]/.test(coordSplit[0] || !/[0-9]/.test(coordSplit[1]))) {
return {
error: 'Invalid coordinate'
}
};
if (value < 1 || value > 9 || isNaN(value)) {
return {
error: 'Invalid value'
}
}
let boardCoords = this.coordToBoard(coordinate)
//console.log("boardCoords: " + boardCoords)
let board = this.createBoard(puzzleString)
//console.log(board)
let conflicts = []
if (this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
conflicts.push(this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
}
if (this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
conflicts.push(this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
}
if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
conflicts.push(this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).conflict)
}
//if value is the same as current coordinate make blank and check if valid and if so return true
if (board[boardCoords[0]][boardCoords[1]] == value) {
board[boardCoords[0]][boardCoords[1]] = '.'
if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid == true && this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid == true && this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid == true) {
return {
valid: true
}
}
}
if (this.checkRegionPlacement(board, boardCoords[0], boardCoords[1], value).valid != true || this.checkColPlacement(board, boardCoords[0], boardCoords[1], value).valid != true || this.checkRowPlacement(board, boardCoords[0], boardCoords[1], value).valid != true) {
return {
valid: false,
conflict: conflicts
}
}
return {
valid: true
}
}
findUnassignedLocation(puzzleString) {
return puzzleString.indexOf('.')
}
rowColToCoord(index) {
let col = (index % 9) + 1;
let row = String.fromCharCode(parseInt(index / 9) + 65)
return row + col
}
solve(puzzleString) {
if (!puzzleString) {
return {
error: 'Required field missing'
}
}
if (this.validate(puzzleString) != true) {
return this.validate(puzzleString)
}
let empty = this.findUnassignedLocation(puzzleString)
if (empty == -1) {
console.log('no empties: ' + puzzleString)
return {solution: puzzleString}
} else {
let coord = this.rowColToCoord(empty)
for (var num = 1; num <= 9; num++) {
if (this.checkPlacement(puzzleString, coord, num).valid ) {
if (!this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1))).error) {
console.log('no error: ' + puzzleString)
return {solution: puzzleString}
}
}
}
//console.log('Cannot be solved: ' + puzzleString)
return {error: 'Puzzle cannot be solved'}
}
}
}
module.exports = SudokuSolver;这是日志的输出：
Cannot be solved: 7692354188514763.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 7692354188514769.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 769235418851476..2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 76923541885147...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 7692354188514963724321785..1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
Cannot be solved: 76923541885149637243217895617456928339582..6.62.71...9......1945....4.37.4.3..6..
no empties: 769235418851496372432178956174569283395842761628713549283657194516924837947381625
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794738162.
no error: 7692354188514963724321789561745692833958427616287135492836571945169248379473816..
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794738.6..
no error: 7692354188514963724321789561745692833958427616287135492836571945169248379473..6..
no error: 76923541885149637243217895617456928339584276162871354928365719451692483794.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516924837.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516924.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836571945169.4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283657194516..4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928365719451...4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836571945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928365.1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492836..1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549283...1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871354928....1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135492.....1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713549......1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958427616287135.9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842761628713..9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162871...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276162.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584276.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395842.6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339584..6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789561745692833958...6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283395....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617456928339.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569283.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174569.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178956174.69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895617..69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789561...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217895.1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321789..1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432178...1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149637243217....1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963724321.....1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496372432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514963.2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235418851496..2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885149...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692354188514....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541885.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 76923541.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769235.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7692.5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 769..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: 7.9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..
no error: ..9..5.1.85.4....2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..解决方案
原因是您的代码忽略了可能从递归调用返回的解决方案，而只是返回最初调用它的不完整拼图：
if (!this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1))).error) {
console.log('no error: ' + puzzleString)
return {solution: puzzleString} // Wrong. This is not the solution, but the unfinished puzzle.
}
而是这样做：
let result = this.solve((puzzleString.substr(0, empty) + num + puzzleString.substr(empty + 1)));
if (!result.error) {
console.log('no error: ' + puzzleString)
return result; // Return what you got from the recursive call (the solution)
}
推荐阅读
- docker - 从 kubernetes 插件 / jenkins 中的 gcr 拉取 docker 图像的问题
- python - 将两个熊猫数据框放在一起
- clojure - 如何从 Clojure 中的打印行末尾读取输入？
- android - 多个dex文件定义Lcom/getkeepsafe/relinker/SystemLibraryLoader；
- php - PHP 表单（使用 POST）不提交或发送电子邮件，只显示一个空白页面
- geopandas - 运行 geopandas 身份时找不到模块
- mysql - 具有多个独立左连接的单个查询
- sql - 将数据从一个表访问到另一个表
- javascript - 如何将方法添加到字符串，当它不可变时使用它的原型？
- sql-server-2008 - 2列（字符串数组）之间的差异并显示差异在哪里