let puzzle = [
[0, 0, 7, 0, 0, 3, 5, 0, 0],
[6, 0, 5, 4, 0, 8, 3, 0, 2],
[0, 0, 4, 5, 2, 0, 9, 0, 6],
[0, 0, 0, 0, 7, 1, 2, 0, 9],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[8, 0, 9, 2, 3, 0, 0, 0, 0],
[9, 0, 1, 0, 8, 5, 6, 0, 0],
[7, 0, 3, 9, 0, 2, 8, 0, 5],
[0, 0, 8, 7, 0, 0, 1, 0, 0]
];
class Sudoku
{
constructor(puzzle)
{
this.sudoku = puzzle;
}
isPossible(y, x, n)
{
for (let i = 0; i < 9; i++)
{
if (this.sudoku[y][i] == n)
return false;
}
for (let i = 0; i < 9; i++)
{
if (this.sudoku[i][x] == n)
return false;
}
let y0 = (Math.floor(y / 3) * 3);
let x0 = (Math.floor(x / 3) * 3);
for (let i = 0; i < 3; i++)
{
for (let j = 0; j < 3; j++)
{
if (this.sudoku[y0 + i][x0 + j] == n)
return false;
}
}
return true;
}
solve()
{
for (let y = 0; y < 9; y++)
{
for (let x = 0; x < 9; x++)
{
if (this.sudoku[y][x] == 0)
{
for (let n = 1; n <= 9; n++)
{
if (this.isPossible(y, x, n))
{
this.sudoku[y][x] = n;
this.solve();
this.sudoku[y][x] = 0;
}
}
return;
}
}
}
console.table(this.sudoku);
}
}
let s = new Sudoku(puzzle);
s.solve();
This works fine the way it is written. However, debugging shows that after the console.table, the code keeps running and takes the matrix back to its original state. But, the console.table line is never executed again. So, outside of the solve method, this.sudoku is just the original puzzle matrix.
Why is this happening? After the output, what is causing the code to keep running? How come it never goes back to the end (console.table), and how can I stop it once it has actually solved the puzzle?
It is important to see that the console output is reached if and only if there are no if no more open fields in the table (programmatically. matrix elements set to zero).
In any other case the control flow returns from the current function invocation before the output statement is reached
The recursive algorithm dwells on the idea that to solve a given sudoku problem, you pick an open field, pick the first number between 1 and 9 that keeps the tableau consistent with the rules and try to solve this new puzzle by recursively calling the solver. Termination is guaranteed as with each recursive call there is one open field less.
After a recursive call has completed, the choice made immeidately before the call is retracted and the remaining possibilities to assign a number to the position are tried, once again ascertaining consistency and recursively calling the solver. This way, all solutions to the original puzzle will be found.
The solver is efficient in the sense that it visits every configuration that does not admit another level of recursion ( ie. which is a solution or a dead end ) only once. There is exactly 1 sequence in which the configuration's positions that are open in the start puzzle will be filled.
From a Troll
I will do that this way, simply adding some break...
const puzzle =
[ [ 0, 0, 7, 0, 0, 3, 5, 0, 0]
, [ 6, 0, 5, 4, 0, 8, 3, 0, 2]
, [ 0, 0, 4, 5, 2, 0, 9, 0, 6]
, [ 0, 0, 0, 0, 7, 1, 2, 0, 9]
, [ 0, 0, 0, 0, 0, 0, 0, 0, 0]
, [ 8, 0, 9, 2, 3, 0, 0, 0, 0]
, [ 9, 0, 1, 0, 8, 5, 6, 0, 0]
, [ 7, 0, 3, 9, 0, 2, 8, 0, 5]
, [ 0, 0, 8, 7, 0, 0, 1, 0, 0]
];
const Sudoku = (()=>
{
let
grid = null
, solved = false
;
const isPossible = (row, col, num) =>
{
for (let c in grid) if (grid[row][c] === num) return false;
for (let r in grid) if (grid[r][col] === num) return false;
let
row0 = 3*(0|row/3)
, col0 = 3*(0|col/3)
;
for (let c of [0,1,2])
for (let r of [0,1,2])
if (grid[row0 + r][col0 + c] === num) return false;
return true;
}
const solve = () =>
{
for (let row in grid)
{
if (solved) break
for (let col in grid)
{
if (grid[row][col] == 0)
{
if (solved) break
for (let num of [1,2,3,4,5,6,7,8,9])
if (isPossible(row, col, num))
{
grid[row][col] = num;
solve();
if (!solved) grid[row][col] = 0;
};
return;
};
}
}
solved = true
}
return (puzzle)=>
{
grid = puzzle
solved = false
solve()
// console.table(grid); doesn't work on snippet
for (let row of grid) console.log(JSON.stringify(row))
}
})()
Sudoku(puzzle);.as-console-wrapper {max-height: 100% !important;top: 0;}
.as-console-row::after {display: none !important;}