Algorithme de backtracking JavaScript avec un comportement étrange

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();

Cela fonctionne bien tel qu'il est écrit. Cependant, le débogage montre qu'après le console.table, le code continue à s'exécuter et ramène la matrice à son état d'origine. Mais, la ligne console.table n'est jamais exécutée à nouveau. Ainsi, en dehors de la méthode solve, this.sudoku est simplement la matrice d'origine puzzle. Pourquoi cela se produit-il ? Après la sortie, qu'est-ce qui fait que le code continue à s'exécuter ? Comment se fait-il qu'il ne revienne jamais à la fin (console.table), et comment puis-je l'arrêter une fois qu'il a réellement résolu le puzzle ?

Answer 1

Il est important de noter que la sortie de la console est atteinte si et seulement si il n'y a plus de champs ouverts dans le tableau (programmation. éléments de la matrice mis à zéro).

Dans tous les autres cas, le flux de contrôle retourne de l'invocation de fonction actuelle avant que l'instruction de sortie ne soit atteinte

L'algorithme récursif repose sur l'idée que pour résoudre un problème de sudoku donné, vous choisissez un champ ouvert, choisissez le premier nombre entre 1 et 9 qui garde le tableau cohérent avec les règles et essayez de résoudre ce nouveau puzzle en appelant récursivement le solveur. La terminaison est garantie car à chaque appel récursif, il y a un champ ouvert de moins.

Après qu'un appel récursif ait été terminé, le choix fait juste avant l'appel est révoqué et les possibilités restantes d'assigner un nombre à la position sont essayées, vérifiant une fois de plus la cohérence et en appelant récursivement le solveur. De cette manière, toutes les solutions du puzzle original seront trouvées.

Le solveur est efficace dans le sens où il visite chaque configuration qui n'admet pas un autre niveau de récursion (c'est-à-dire une solution ou une impasse) une seule fois. Il y a exactement 1 séquence dans laquelle les positions de la configuration qui sont ouvertes dans le puzzle initial seront remplies.

        SO - Bitmap (svg)

            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;
            }

            document.addEventListener('DOMContentLoaded', () => {
let puzzle_orig = [  // Le problème d'origine
        [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 = [ // Plusieurs 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();

            });

Answer 2

Je ferai cela de cette manière, il suffit d'ajouter un test résolu et de casser quelques boucles...

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 ? 'résolu !':'non résolu !','\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;}