I recently wrote this same code in Golang with some help from here.
If you are familiar with go you can see the working code here.
Here is what I am trying to accomplish in python. Computerphile Video
I am now trying to port this to javascript.
I initialize the gameState.
var gameState = [
[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]
]
This is the grid taken from the sudoku Wikipedia page.
I wrote the following helper functions to get the row, column and block units of anywhere on the grid. I've tested them all and they all seem to work fine.
function isUnitUnique(unit) {
for (let value = 1; value <= 9; value++) {
let tally = 0;
for (let index = 0; index < 9; index++) {
if (unit[index] == value) {
tally++;
}
}
if (tally > 1) {
return false;
}
}
return true;
}
function getColumnUnit(board, column) {
let unit = [];
for (let row = 0; row < 9; row++) {
unit.push(board[row][column]);
}
return unit;
}
function getBlockUnit(board, x, y) {
let unit = []
if (x >= 0 && x <= 2) { j = 1; }
else if (x >= 3 && x <= 5) { j = 4; }
else if (x >= 6 && x <= 8) { j = 7; }
if (y >= 0 && y <= 2) { i = 1; }
else if (y >= 3 && y <= 5) { i = 4; }
else if (y >= 6 && y <= 8) { i = 7; }
unit.push(board[i - 1][j - 1]);
unit.push(board[i - 1][j]);
unit.push(board[i - 1][j + 1]);
unit.push(board[i][j - 1]);
unit.push(board[i][j]);
unit.push(board[i][j + 1]);
unit.push(board[i + 1][j - 1]);
unit.push(board[i + 1][j]);
unit.push(board[i + 1][j + 1]);
return unit;
}
I then use the helper functions with the following code to try and solve the puzzle. This is a recursive backtracking algorithm.
function solve() {
for (let row = 0; row < 9; row++) {
for (let column = 0; column < 9; column++) {
if (gameState[row][column] == 0) {
for (let value = 1; value <= 9; value++) {
if (possible(row, column, value)) {
gameState[row][column] = value;
solve();
gameState[row][column] = 0;
}
}
return;
}
}
}
console.log(gameState);
return;
}
function possible(y, x, n) {
let boardCopy = JSON.parse(JSON.stringify(gameState));
boardCopy[y][x] = n;
return isUnitUnique(boardCopy[y]) && isUnitUnique(getColumnUnit(boardCopy, x)) && isUnitUnique(getBlockUnit(boardCopy, x, y))
}
This console logs the initial game state unchanged. From doing some debugging I can see that the algorithm is going through the grid however it doesn't seem to keep the changes that I make to the grid.
Thanks in advance.
As suggested here is a runnable version of my code. It works when I run it in the snippet. When using chrome it doesn't.
var gameState = [
[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 solve() {
for (let row = 0; row < 9; row++) {
for (let column = 0; column < 9; column++) {
if (gameState[row][column] == 0) {
for (let value = 1; value <= 9; value++) {
if (possible(row, column, value)) {
gameState[row][column] = value;
solve();
gameState[row][column] = 0;
}
}
return;
}
}
}
console.log(gameState);
return;
}
function possible(y, x, n) {
let boardCopy = JSON.parse(JSON.stringify(gameState));
boardCopy[y][x] = n;
return isUnitUnique(boardCopy[y]) && isUnitUnique(getColumnUnit(boardCopy, x)) && isUnitUnique(getBlockUnit(boardCopy, x, y))
}
function isUnitUnique(unit) {
for (let value = 1; value <= 9; value++) {
let tally = 0;
for (let index = 0; index < 9; index++) {
if (unit[index] == value) {
tally++;
}
}
if (tally > 1) {
return false;
}
}
return true;
}
function getColumnUnit(board, column) {
let unit = [];
for (let row = 0; row < 9; row++) {
unit.push(board[row][column]);
}
return unit;
}
function getBlockUnit(board, x, y) {
let unit = []
if (x >= 0 && x <= 2) { j = 1; }
else if (x >= 3 && x <= 5) { j = 4; }
else if (x >= 6 && x <= 8) { j = 7; }
if (y >= 0 && y <= 2) { i = 1; }
else if (y >= 3 && y <= 5) { i = 4; }
else if (y >= 6 && y <= 8) { i = 7; }
unit.push(board[i - 1][j - 1]);
unit.push(board[i - 1][j]);
unit.push(board[i - 1][j + 1]);
unit.push(board[i][j - 1]);
unit.push(board[i][j]);
unit.push(board[i][j + 1]);
unit.push(board[i + 1][j - 1]);
unit.push(board[i + 1][j]);
unit.push(board[i + 1][j + 1]);
return unit;
}
solve()Thanks to @HereticMonkey for suggesting I use stack snippets to share my code. In doing so I realized that it worked in this environment, and that it had to do with running the code in the browser that was causing the issue (Chrome). Also thanks to @bcr666 who also mentioned that potentially the algorithm was zeroing itself out on the way back.
The code listed in the question was all correct. I added one check to prevent the function from continuing to execute after it reached its exit condition.
let solved = false
function solve() {
for (let row = 0; row < 9; row++) {
for (let column = 0; column < 9; column++) {
if (gameState[row][column] == 0) {
for (let value = 1; value <= 9; value++) {
if (possible(row, column, value)) {
gameState[row][column] = value;
solve();
if (!solved) {
gameState[row][column] = 0;
}
}
}
return;
}
}
}
solved = true;
console.log(gameState);
return;
}
Checking if the game has been solved before backtracking fixed this issue. Before it would log the results it was attempting to find more solutions.