Probleme – Le sudoku : la même exploration, deux ordres de choix

1. Le solveur lexicographique.

(* Vrai si la grille g admet un remplissage ; g est alors modifiée en place et
   contient une solution. Précondition : g est un tableau 9 x 9, 0 = case vide,
   et les chiffres déjà posés respectent les règles. *)
let admissible g i j v =
  let ok = ref true in
  for k = 0 to 8 do
    if g.(i).(k) = v || g.(k).(j) = v then ok := false
  done;
  let bi = 3 * (i / 3) and bj = 3 * (j / 3) in
  for a = 0 to 2 do for b = 0 to 2 do
    if g.(bi + a).(bj + b) = v then ok := false done done;
  !ok

let resoudre g =
  let rec explorer k =
    if k = 81 then true
    else
      let i = k / 9 and j = k mod 9 in
      if g.(i).(j) <> 0 then explorer (k + 1)     (* case donnée : on passe *)
      else begin
        let fini = ref false and v = ref 1 in
        while not !fini && !v <= 9 do
          if admissible g i j !v then begin
            g.(i).(j) <- !v;
            if explorer (k + 1) then fini := true
            else g.(i).(j) <- 0                   (* on DÉFAIT *)
          end;
          incr v
        done;
        !fini
      end
  in explorer 0

Terminaison : variant $81-k$, qui décroît strictement à chaque appel récursif. Correction : à tout instant la grille est partiellement valide — l'appel n'est fait qu'après un test admissible —, et l'on n'atteint $k=81$ qu'avec les $81$ cases remplies, donc avec une solution.

2. La case la plus contrainte d'abord. On ne suit plus l'ordre des cases : à chaque appel, on choisit la case vide ayant le moins de candidats.

(* Même spécification que resoudre, autre ordre de choix des cases. *)
let resoudre_contrainte g =
  let candidats i j =
    let l = ref [] in
    for v = 9 downto 1 do if admissible g i j v then l := v :: !l done; !l in
  let rec explorer () =
    (* on cherche la case vide de plus petit nombre de candidats *)
    let meilleure = ref None and mini = ref 10 in
    for i = 0 to 8 do for j = 0 to 8 do
      if g.(i).(j) = 0 then begin
        let c = candidats i j in
        if List.length c < !mini
        then begin mini := List.length c; meilleure := Some (i, j, c) end
      end done done;
    match !meilleure with
    | None -> true                      (* plus aucune case vide : c'est gagné *)
    | Some (_, _, []) -> false          (* une case SANS candidat : échec immédiat *)
    | Some (i, j, cands) ->
        let fini = ref false in
        List.iter (fun v ->
          if not !fini then begin
            g.(i).(j) <- v;
            if explorer () then fini := true else g.(i).(j) <- 0
          end) cands;
        !fini
  in explorer ()

Le cas Some (_, _, []) est la clef : dès qu'une case n'a plus aucun candidat, la branche est morte, et l'on s'en aperçoit sans avoir posé un seul chiffre de plus.

3. La mesure. Les deux versions rendent la même grille, ce qui a été vérifié.

L'explication de l'écart, et elle vaut pour tout le chapitre. L'ordre lexicographique choisit une case sans regarder la grille ; il peut donc s'engager sur une case à huit candidats alors qu'une autre n'en a qu'un. Les sept mauvais choix seront découverts très bas dans l'arbre, après avoir rempli des dizaines de cases.

Choisir la case la plus contrainte, c'est faire remonter l'échec vers la racine. Une case à un seul candidat ne crée pas de branchement du tout ; une case sans candidat coupe immédiatement. Sur la grille facile, cela suffit à faire disparaître presque toute l'exploration : $52$ nœuds pour $51$ cases à remplir, c'est-à-dire un chiffre posé par nœud, sans un seul retour en arrière.

Et sur la grille difficile, le gain tombe à $7$. Ce n'est pas une déception, c'est la définition : une grille est difficile précisément quand aucune case n'est fortement contrainte, donc quand l'heuristique n'a plus de prise. L'élagage ne fait jamais mieux que ce que la structure de l'instance lui permet.