Sorry for the code dump below...!
This algorithm does sovle the sudoku puzzle (as the log in solve if empty == -1 func) but the actual output once all of the recursion unwinds is either returning the original puzzle string or returning the default case of {error: 'Puzzle cannot be solved'}.
I think it's probably a final iteration error but I've refactored and reorganised till I'm blue in the face and can't work out why it's not returning the successful output as it unwinds.
Any help would be hugely appreciated.
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;Here's the output from the log:
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..The reason is that your code ignores the solution that is potentially returned from the recursive call, and instead just returns the incomplete puzzle it was initially called with:
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.
}
Instead do this:
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)
}