javascript backtracking algorithm with strange bahavior

Question

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?

user_588916 · Answer

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.



    
        
        
        
        
        SO - Bitmap (svg)

user_10669010 · Answer

I will do that this way, simply add a solved test and some 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 (solved) break
          if (grid[row][col] === 0)
            {
            for (let num of nums)
              if (isPossible(row, col, num))
                {
                grid[row][col] = num
                solve()
                if (solved) break 
                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 !','
' )

console.log(JSON.stringify(puzzle).replaceAll('],[',']
,['))

// console.table( )  doesn't work on snippet

.as-console-wrapper {max-height: 100% !important;top: 0;}
.as-console-row::after {display: none !important;}

javascript backtracking algorithm with strange bahavior

2 Answers