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?
CodePudding user response：
From a Troll
I will do that this way, simply add a solved test and a loop break...
const Sudoku = (()=>
{
let
grid = null
, solved = false
;
const
nums = [1,2,3,4,5,6,7,8,9]
, 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
row -= row %3
col -= col %3
for (let i=0, c=col; i<3; i ,c )
for (let j=0, r=row; j<3; j ,r )
if (grid[r][c] === num) return false
return true
}
, solve = () =>
{
for (let row in grid)
{
if (solved) break
for (let col in grid)
if (grid[row][col] == 0)
{
for (let num of nums)
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()
return solved
}
})()
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 ]
]
let resolved = Sudoku(puzzle)
console.log( resolved ? 'resolved !':'not resolved !','\n' )
console.log(JSON.stringify(puzzle).replaceAll('],[',']\n,['))
// console.table( ) doesn't work on snippet.as-console-wrapper {max-height: 100% !important;top: 0;}
.as-console-row::after {display: none !important;}CodePudding user response：
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 immediately 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.
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<meta http-equiv="expires" content="0">
<meta http-equiv="cache-control" content="private">
<meta http-equiv="pragma" content="no-cache">
<title>SO - Bitmap (svg)</title>
<!--
-->
<style type="text/css">
body {
background-color: #eee;
}
.board {
display: table;
border: solid 3px black
}
.board > div {
display: table-row;
}
.cell {
width: 16px;
height: 16px;
display: table-cell;
border: solid 1px lightgrey;
padding: 5px;
text-align: center;
vertical-align: middle;
font-size: 80%;
}
.last-square-column {
border-right: solid 2px black;
}
.last-square-row {
border-bottom: solid 2px black;
}
.preset {
color: blue;
background-color: #ddddff;
}
</style>
<script>
document.addEventListener('DOMContentLoaded', () => {
let puzzle_orig = [ // The original problem
[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]
]
;
let puzzle = [ // Multiple solutions
[0, 0, 7, 0, 0, 3, 5, 0, 0],
[6, 0, 5, 4, 0, 8, 3, 0, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[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;
this.base = puzzle.map ( a_row => { return a_row.map ( n_cell => n_cell ); });
this.n_solutions = 0;
}
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;
}
out () {
let e_body = document.querySelector('body')
, e_board = document.createElement('div')
, e_h = document.createElement('h3')
;
e_h.innerText = `Solution #${this.n_solutions }`;
e_board.setAttribute('class', 'board');
for (let y = 0; y < 9; y ) {
let e_row = document.createElement('div')
;
for (let x = 0; x < 9; x ) {
let e_cell = document.createElement('div')
;
e_cell.innerText = this.sudoku[y][x];
e_cell.setAttribute('class', 'cell');
if (this.base[y][x] !== 0) {
e_cell.classList.add('preset');
}
if ((x === 2) || (x === 5)) {
e_cell.classList.add('last-square-column');
}
if ((y === 2) || (y === 5)) {
e_cell.classList.add('last-square-row');
}
e_row.append(e_cell);
}
e_board.append(e_row);
}
e_body.append(e_h);
e_body.append(e_board);
} // out
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;
}
}
}
this.out();
}
}
let s = new Sudoku(puzzle);
s.solve();
});
</script>
</head>
<body>
</body>
</html>