Sudoku !

Bonjour à tous et bienvenue dans ce nouveau Défi de Clem !

Un jeu américain

Eh oui, mesdames et messieurs, je vous parle du célèbre jeu inspiré du carré magique et du problème des 36 officiers d'Euler: le sudoku ! Inventé par un américain puis popularisé par les japonais !

Un rappel des règles du sudoku:

• Il s'agit d'une grille divisée en $3\times3$ carrés, eux-mêmes subdivisés en $3\times3$ autres carrés
• Dans chaque grand carré, les chiffres $1, 2, 3, 4, 5, 6, 7, 8$, et $9$ doivent être présent de manière unique (puisque c'est un carré de $3\times3$)
• Dans chaque ligne, les chiffres $1, 2, 3, 4, 5, 6, 7, 8$, et $9$ doivent être présent de manière unique (il y a $9$ petits carrés)
• Dans chaque colonne, les chiffres $1, 2, 3, 4, 5, 6, 7, 8$, et $9$ doivent être présent de manière unique (il y a $9$ petits carrés)
• Chaque grille a une solution unique.

Le défi

Notre objectif est d'écrire un programme qui résout n'importe quelle grille de sudoku, si cela est possible, de taille $N\times N$. Pour les plus motivés, je proposerai quelques défis qui approfondissent le sujet. Je vais vous guider et vous permettre de tester votre programme sur de nombreux exemples. Avant toute chose, définissons quelques normes pour que tout le monde ait les mêmes entrées et sorties.

I - Quelques normes

On va s'imposer à tous une manière unique de représenter ces grilles par des chaînes de caractères. Tout le monde pourra ainsi copier les grilles de sudoku qui vous seront fournies pour tester efficacement son programme.

Chaque grille se présentera comme suit (les guillemets indiquent qu'il s'agit de texte):

1

"1234567894567891237891.345623456789156789123489123456734.678912678912345912345678"

Vous constatez que cette représentation de grille est peu lisible. Un point signale une case de la grille vide. Chaque ligne de la grille de sudoku est composée de neuf chiffres ou points successifs. Une solution pour implémenter ceci est tout simplement de stocker le sudoku dans un tableau a 2 dimensions (il peut être plus simple de déclarer un tableau 1 dimension, mais de s'en servir comme d'un tableau à deux dimensions. Si vous ne savez pas comment faire, lancez vous et posez vos question. Utiliser un véritable tableau a deux dimensions fonctionne parfaitement aussi). Vous lisez donc les 9 premiers caractères et initialisez la première ligne du tableau d'entiers (fixons que quand le caractère lu est un "." alors on met 0 dans le tableau). Ensuite, passez à la deuxième ligne. Et ainsi de suite. En spoiler un petit pseudo code pour ceux qui aurait du mal à manipuler les tableaux (j'utilise la solution proposée en parenthèse plus haut).

1
2
3
4
5
6
7
8
9

/** sudoku est un vecteur (= tableau) de longueur 81 **/
Debut
    Pour i allant de 0 à 8
        Pour j allant de 0 à 8
           /** E(x) désigne la partie entière de x. E(1.987987) = E(1) = E(1.3232) = 1
            sudoku(i*9 + E(j/9)) = saisie_nombre_utilisateur()
        fin pour
    fin pour
Fin 

Voici une ressource avec pleins de sudokus (un par ligne) réputés difficile pour un humain.

Enfin, nous allons mettre en place une manière d'afficher de telles grilles, pour que l'on puisse aisément les lire:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

+---+---+---+
|469|253|871|
|426|173|985|
|891|725|634|
+---+---+---+
|163|587|492|
|384|592|167|
|495|731|628|
+---+---+---+
|518|269|473|
|842|719|356|
|687|345|219|
+---+---+---+

Une petite aide:

Nous voulons afficher un sudoku de manière un peu plus esthétique qu'une série de chiffres illisible. Pour ça nous devons définir comment nous voulons l'afficher. Nous voulons donc que la première ligne soit cette chaîne de caractères :

1

"+---+---+---+"

Puis pour les 3 lignes qui suivent nous voulons afficher (où "." est un nombre de notre sudoku) :

1

|...|...|...|

Et on recommence. En spoiler un petit pseudo code montrant comment faire tout ceci dans un langage utilisant une structure string (comme le C++ ou le Java, mais pas le C)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Début
    S = "+---+---+---+"
    Pour i allant de 0 a 8
        si ((i+1) % 3) == 0 alors
            S = S + "+---+---+---+"
        fin si

        S = S + "|"
        Pour j allant de 0 a 9
            si ((j+1) % 3) == 0 alors
                S = S + "|"
            fin si
            
            S = S + sudoku[i][j]
        fin pour
    fin pour

C'est tout pour uniformiser nos programmes sur les entrées et sorties. Passons aux vrais défis !

II - Vérifier une grille

Pour cette première étape je vous propose que vous fassiez un vérificateur de grille. En entrée vous avez une grille de sudoku et devez dire si la grille est valide. Une grille valide est une grille qui respecte les règles définies plus tôt dans ce défi. Je vous donne en spoiler quelques jeux de tests. Avant de vous lancer dans comment vous allez faire, n'oublier pas de réfléchir à comment vous aller représenter le sudoku dans votre programme.

1
2
3
4
5
6
7
8
9

"123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123.56789123456789123456789123456789123456789123456789123456789123456789"
"1234567894567891237891.345623456789156789123489123456734.678912678912345912345678"
"123456789456789123789123456234567891567891234891234567345678912678912345912345678"

// FAUX
// FAUX
// FAUX
// VRAI

Je ne détail pas plus car je pense que c'est relativement simple. Pour ceux qui auraient le plus de mal posez des questions et si vraiment il y à besoin je rajouterais une petite partie.

III - Résoudre une grille de Sudoku !

Ca y est ! On est paré. On a notre représentation, de quoi vérifier et de quoi générer. Allez y !

Bon.. D'accord je vous guide un petit peu. A ceux qui ne savent vraiment pas comment s'y prendre, voici un tuto qu'un membre a rédigé utilisant le backtracking, une bonne méthode pour des petites grilles ! Ceci est une méthode très lourde en calcul mais qui a l'avantage d'être rapide à implémenter et plutôt simple à comprendre.

Je vais vous proposer une autre approche qui me semble plus interessante. Cependant il va falloir sérieusement vous creuser la tête et je vous expliquerais pourquoi. Quand j'ai été confronté au problème (en cours en fait) j'avais le choix de "bêtement" faire le backtracking ou trouver ma propre méthode. Je me suis donc posé avec un stylo et une feuille et je me suis dit : "Comment je fais moi pour résoudre un sudoku ?". S'en est suivi une bonne heure où je décortiquais ma méthode de résolution. J'ai ensuite décidé de l'implémenter et.. Magie ça fonctionnait ! Ou presque. En effet, si vous avez déjà fait des sudokus, vous savez qu'il y à plusieurs méthodes pour savoir où placer un chiffre. Certaines sont simples, d'ailleurs les sudokus de difficulté 1 ne font appel qu'a une simple méthode. Certaines sont plutôt compliqué et demande beaucoup d'interprétation.

Les méthodes de résolutions "humaines" se basent sur l'analyse des nombres. "Comment les nombres sont-ils disposés dans la grille ?". Par exemple quand je fais un sudoku, je regarde ou est-ce que je peux placer un 1, puis un 2 etc. Ce que je fais souvent aussi c'est regarder pour chacune des cases si c'est évident de disposer un nombre (par exemple il ne reste qu'une seule case dans la ligne). Voici à quoi pourrais ressembler une algorithme de résolution (en pseudo code). Attention, tout n'est pas détaillé, il faut que le défi reste présent ;).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Début
    Tant que !est_resolu(sudoku)
        Pour i allant de 0 à 81
            nombres = trouver_nombres(sudoku, i)
            si nombres.size == 1 alors
                sudoku[i] = nombres[0]
            fin si
        fin pour
    fin tantque
    afficher(sudoku)
Fin

Voilà pour les petits conseils. Bien entendu, il ne s'agit pas des seules solutions pour résoudre un sudoku. Si vous voulez en connaître plus, Yoch (l'auteur du tutoriel sur le backtracking) m'a fourni une liste de différentes solutions à utiliser :

• Le module clpfd (Constraint Logic Programming over Finite Domains) de prolog qui est parfaitement adapté à ce type de problème.
• Le sudoku peut être modélisé comme un problème de couverture exacte de la théorie des graphes, pour lequel il existe un algorithme de résolution très efficace imaginé par D. Knuth : l'algoritme DLX. C'est un algorithme intéressant et relativement accessible.
• Le sudoku peut aussi être modélisé comme un problème SAT, et il existe aujourd'hui des dizaines de solveurs SAT extrêmement performants (par exemple minisat, picosat).
• Le sudoku peut encore être modélisé comme un système linéaire sur les entiers, pour lesquels il existe également des solveurs efficaces (par ex. GLPK).
• Et enfin, il est particulièrement intéressant de réaliser un système modélisant les techniques utilisées par des joueurs humains, pour permettre par exemple de classer des grilles en ordre de difficulté. Il y a plein de sites qui traitent ce sujet, par ex. ici.

IV - Générer une grille

Maintenant que vous savez résoudre des grilles, vous pouvez en créer et vérifier qu'elles sont valides ! Je ne met volontairement pas de solution mais uniquement des indications. Un avant goût des challenges !

Peu d'informations sont nécessaires pour pouvoir générer un sudoku. En réalité surtout une : le nombre de cases pleine (ou vide). Nous aurons donc une entrée qui sera le nombre de case pleine (sachez qu'une grille ayant moins de 17 cases pleines possède plusieurs solutions. Ce qui ne veut pas dire que toute les grilles a plus de 17 cases remplies ont une unique solution). Donc adaptez vous pour respecter l'ensemble des règles (y compris l'unicité de la solution !).

Il existe plusieurs méthodes pour créer une grille de sudoku. En spoiler des indices sur deux méthodes, à vos stylo pour réfléchir !

Pour les plus motivés, voici quelques challenges que je vous propose, ce sont des propositions ouverte.

V - Petits challenges supplémentaires

• Résoudre (et générer) des grilles Samouraï
• Résoudre (et générer) des grilles $N*N$
• Résoudre (et générer) des grilles à 3 dimensions de longueurs N ($N*N*N$)
• Résoudre (et générer) des grilles à M dimension de longueur $N$ ($N*N*N...N*N*N$)

Annexes

Voici quelques ressources si vous voulez testez vos programmes. Par exemple en regardant le temps que vous mettez à résoudre tout une série de sudokus, ou encore combien d'opération vous faites (la complexité).

• Voici des grilles lentes pour le backtracking

• Une liste de 1475 grilles difficiles pour un humain

• La liste de toutes les grilles connues avec 17 nombres révélés

• (si certains d'entre vous ont d'autres ressources à proposer, n'hésitez pas je les rajouterais !)

Merci pour le défi et amusez-vous bien ! J'espère que cette série va continuer longtemps, c'est vraiment cool et ça fait pratiquer ceux qui n'ont pas d'idées.

Je vais vous proposer une autre approche qui me semble plus interessante. Cependant il va falloir sérieusement vous creuser la tête et je vous expliquerais pourquoi. Quand j'ai été confronté au problème (en cours en fait) j'avais le choix de "bêtement" faire le backtracking ou trouver ma propre méthode. Je me suis donc posé avec un stylo et une feuille et je me suis dit : "Comment je fais moi pour résoudre un sudoku ?". S'en est suivi une bonne heure où je décortiquais ma méthode de résolution. J'ai ensuite décidé de l'implémenter et.. Magie ça fonctionnait ! Ou presque.

Ou presque, effectivement : à terme, tu ne peux pas faire l'économie d'un backtracking (ou d'un algorithme équivalent) si tu veux avoir l'assurance de trouver une solution pour chaque grille. Mais l'idée de commencer par des méthodes rapides et faciles pour améliorer le backtracking est bonne.

Oh, j'oubliais: l'autre défi est taggé "défis de clem" avex un S contrairement à celui-ci, il faudrait uniformiser ça. Le topic de discussions sur les défis est quant à lui taggé "défis".

Ce serait pas mal de fournir des grilles compatibles avec le format énoncé. Celles proposées en annexes utilisent des "0" pours les cases vides, et non des "."

Je viens de coder rapidement une solution C++ avec backtracking et une légère intelligence.

L'idée globale est qu'une case est soit connue, soit une valeur parmi un ensemble. On part initialement d'une grille où toutes les cases sont une valeur parmi l'ensemble 1..9. On intègre alors les informations de la grille donnée en paramètre en fixant la valeur de la case donnée. Ce faisant, on supprime cette valeur de la ligne, colonne et bloc, ce qui peut faire apparaître un ensemble contenant une unique valeur pour une case, qui est alors remplacé par sa valeur et ainsi de suite. Pour une grille simple, cela permet de réduire nettement la quantité de backtracking. De même, cela permet d'éviter au backtracking de tester toutes les valeurs et permet de repérer plus vite une grille invalide.

D'un point de vue technique, mes cases sont représenté par un tagged union, une valeur unique étant un int et l'ensemble un bitset de 9 booléens. Le backtracking se fait via des exceptions, ce qui n'est probablement pas super en terme de performance. Je n'ai pas non plus de vérification explicite du fait qu'une grille soit bonne ou non. C'est fait de manière implicite via le backtracking.

En parlant de performances, j'ai testé ma solution sur quelques grilles difficiles pour les humains et j'arrive en dessous des 0.25s sur 4 grilles testés. Sur celles difficiles pour le backtracking, ça varie beaucoup : sur les 3 testés, j'ai 0.25s, 6s et 8.5s.

D'ailleurs, en terme d'optimisations, il pourrait être (très) utile de vérifier toutes les lignes/colonnes/blocs pour voir s'il n'existe pas une case qui est la seul capable de contenir une valeur. De ce que je vois lorsque je résous une grille à la main, avec ma première solution, ça permet de résoudre la très grande majorité des grille avec maximum 1-2 niveaux de backtracking.

Voici mon code pour ceux qui sont intéressés :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

#include <array>
#include <bitset>
#include <iostream>
#include <string>

class bad_grid { };

struct Case {
  bool single;
  union U {
    int val;
    std::bitset<9> vals;
    U() : vals(511) { }
  } v;
};

std::ostream &operator<<(std::ostream &os, const Case &c) {
  if(c.single) {
    os << c.v.val+1;
  } else {
    os << ".";
  }
  return os;
}

typedef std::array<std::array<Case, 9>, 9> Grid;

void set(Grid &g, const int x, const int y, const int val);
void remove(Grid &g, const int x, const int y, const int val);
void display(const Grid &g);

void solve(Grid &g) {
  for(int x=0; x<9; ++x) {
    for(int y=0; y<9; ++y) {
      if(!g[x][y].single) {
        for(int i=0; i<9; ++i) {
          if(g[x][y].single) {
            break;
          }
          if(g[x][y].v.vals[i]) {
            Grid g2 = g;
            try {
              set(g2, x, y, i);
              solve(g2);
              g = g2;
              return;
            } catch(const bad_grid &e) {
              remove(g, x, y, i);
            }
          }
        }
      }
    }
  }
}

void set(Grid &g, const int x, const int y, const int val) {
  if(!g[x][y].single) {
    g[x][y].single = true;
    g[x][y].v.val = val;
    for(int i=0; i<9; ++i) {
      if(i != x) {
        remove(g, i, y, val);
      }
      if(i != y) {
        remove(g, x, i, val);
      }
    }
    const int bx = x - x%3;
    const int by = y - y%3;
    for(int dx=0; dx<3; ++dx) {
      for(int dy=0; dy<3; ++dy) {
        if(bx+dx != x || by+dy != y) {
          remove(g, bx+dx, by+dy, val);
        }
      }
    }
  }
}

void remove(Grid &g, const int x, const int y, const int val) {
  if(!g[x][y].single) {
    auto &vals = g[x][y].v.vals;
    vals[val] = false;
    bool single = false;
    int pos = -1;
    for(int i=0; i<9; ++i) {
      if(vals[i]) {
        if(!single) {
          pos = i;
          single = true;
        } else {
          single = false;
          break;
        }
      }
    }
    if(single) {
      set(g, x, y, pos);
    } else if(pos == -1) {
      throw bad_grid();
    }
  } else {
    if(val == g[x][y].v.val) {
      throw bad_grid();
    }
  }
}

void display(const Grid &g) {
  std::cout << "+---+---+---+" << std::endl;
  for(int bx=0; bx<9; bx+=3) {
    for(int dx=0; dx<3; ++dx) {
      std::cout << "|";
      for(int by=0; by<9; by+=3) {
        for(int dy=0; dy<3; ++dy) {
          std::cout << g[bx+dx][by+dy];
        }
        std::cout << "|";
      }
      std::cout << std::endl;
    }
    std::cout << "+---+---+---+" << std::endl;
  }
}

int main() {
  std::string line;
  std::getline(std::cin, line);
  if(line.size() != 9*9) {
    std::cout << "Incorrect size: " << line.size() << std::endl;
    return 1;
  }
  Grid grid;
  grid[0].fill({false, Case::U()});
  grid.fill(grid[0]);
  int i = 0;
  for(const char c : line) {
    if(c >= '1' && c <= '9') {
      int val = c-'1';
      int x = i/9;
      int y = i%9;
      try {
        set(grid, x, y, val);
      } catch(const bad_grid &e) {
        std::cout << "Bad grid" << std::endl;
        return 1;
      }
    } else if(c != '.' && c != '0') {
      std::cout << "Invalid case: " << c << std::endl;
      return 1;
    }
    ++i;
  }
  try {
    solve(grid);
  } catch(const bad_grid &e) {
    std::cout << "Bad grid" << std::endl;
    return 1;
  }
  display(grid);

  return 0;
}

J'aurais bien aimé voir une petite question en plus qui est très lié à la résolution par backtracking : déterminer si une grille possède une unique solution.

Sinon, si des gens sont prêts à utiliser des solveurs, ça pourrait être intéressant de faire un benchmark.

@Gaah Effectivement, mais c'est plus simple de changer l'énoncé Je n'ai pas souhaité le modifier, au vu de la simplicité de la chose mais s'il ny à des demandes je le ferais.

@Saroupille Dans le sujet original (celui que j'avais eu en cours) il fallait le faire. Mais pour simplifier un peu j'ai omis cette partie

Ma solution

Pour l'instant j'ai une solution que vous trouverez probablement complexe et peu documentée (je vais arranger ça d'ici la fin). Elle est inutilement complexe à cause de Java et parce que c'était un exercice. Cependant voici le lien et je vous donne quelques explications en spoiler (c'est assez long à expliquer mais permet d'aller jusqu'à 10fois plus vite que certains backtracking mal codé et 4fois plus vite que les backtrackings correctement fait, ie : pas optimisé, implémenté naïvement correctement). Attention, vous devriez avoir codé le votre pour lire cette solution, sinon vous perdrez tout l'intérêt du défi !

1
2
3

grille[i][j] = (~ligne[i]) ^ allNumbers;
grille[i][j] &= (~colonne[j]) ^ allNumbers;
grille[i][j] &= (~carre[(i / 3) + (j / 3) * 3]) ^ allNumbers;

Si je comprends bien ta méthode, il y a deux « améliorations » orthogonales :

• Utiliser les opérations sur les bits pour aller plus vite qu'avec des entiers classiques
• Commencer par choisir toutes les cases avec un seul nombre possible pour réduire le backtracking que tu fais ensuite

Du coup c'est un peu trompeur de dire « regardez je fais mieux que du backtracking ! » : ça fait croire que tu as un algorithme plus efficace, alors que tu fais en réalité du backtracking, la structure sur laquelle tu travailles est juste plus efficace. Cela dit, c'est déjà un résultat intéressant, puisque comme la première étape ne sert à rien à part sur quelques grilles très faciles, les chiffres que tu donnes sont assez représentatifs de l'intérêt de ton astuce.

Ce serait intéressant d'aller aussi dans l'autre direction, à savoir « un algorithme qui allège le backtracking quand c'est possible ». Là tu commences par réduire la grille en affectant des nombres aux cases qui ne peuvent en contenir qu'un seul. Pourquoi ne pas faire ça à chaque étape du backtracking, plutôt qu'une fois seulement au début ?

En continuant sur le même genre de piste, est-ce que tu as essayé de faire un backtracking où, au lieu d'énumérer naïvement les cases dans l'ordre de lecture, on commence par essayer celles qui ont le moins de possibilités restantes ? Implémenter cet algorithme (où on change seulement la fonction « case suivante à essayer » du backtracking) permet d'ailleurs d'avoir gratuitement les deux astuces précédentes.

Choisir les cases qui ont le moins de possibilités restantes n'améliore pas forcément le backtracking. J'avais essayé cette technique sur la première grille difficile pour le backtracking et je suis passé de 0.25s à 1.25s. Par contre, ça améliorait le temps pour la troisième grille. Du coup, je n'ai pas trop cherché dans cette direction.

@Eusèbe En réalité, si tu prend une grille aléatoire dans l'ensemble des grilles qui existe, il y à peu de chance que les méthodes humaines qui n'utilisent pas le backtracking (ou un équivalent) ne suffisent pas. J'ai implémenté les deux méthodes de bases, et même les grilles réputés difficile n'utilisent pas le backtracking, ou alors pour les dernières cases (de mémoire d'un an c'est pour 5/6 cases). En fait j'utilise la backtracking qu'en dernier recours. Si j'y ait recours, oui un certains nombre de case auront pût être complétée, mais ce n'est même pas sûr. Je t'invite à faire les tests en prenant mon code (Java 7 windobe, mais ça devrait passer sous linux et en java 7 ou 8).

@Eusèbe En réalité, si tu prend une grille aléatoire dans l'ensemble des grilles qui existe, il y à peu de chance que les méthodes humaines qui n'utilisent pas le backtracking (ou un équivalent) ne suffisent pas.

Parmi l'ensemble des grilles prises dans les journaux, c'est évident, elles sont précisément conçues pour ça. Parmi l'ensemble des grilles existantes, c'est assez osé comme affirmation, et je pense qu'elle est fausse.

J'ai implémenté les deux méthodes de bases, et même les grilles réputés difficile n'utilisent pas le backtracking, ou alors pour les dernières cases (de mémoire d'un an c'est pour 5/6 cases). En fait j'utilise la backtracking qu'en dernier recours. Si j'y ait recours, oui un certains nombre de case auront pût être complétée, mais ce n'est même pas sûr.

Bien sûr, il faut utiliser le baxktracking en dernier recours, et si ton but est de résoudre uniquement les sudoku de Direct Matin, ce n'est même pas nécessaire. Mais je pense qu'il est plus intéressant de chercher à résoudre des grilles vraiment difficiles, comme il en existe beaucoup. Et sur ces grilles, les méthodes faciles ne marcheront pas : il faut faire une vraie refléxion algorithmique, qui est à mon avis plus intéressante qu'une énumération de raisonnements triviaux. Ça n'enlève pas l'intérêt de l'astuce des champs de bits, qui est utilisable quelque soit l'algorithme derrière et qui permet d'avoir des performances encore plus intéressantes.

En Prolog, c'est même outrageusement facile à écrire . Pour ceux qui veulent le faire en C++, vous pouvez regarder du solveur de contraintes Gecode.

@Ricocotam : je reviens sur une part de ce que je t'ai écris par MP, et que d'ailleurs Eusèbe a également souligné.

Les chiffres que tu donne pour le backtracking ne sont vrais que dans le cas le plus naïf possible. En optimisant un peu l'approche, un test est en $O(1)$ également.

Le coté réellement intéressant de ton approche (celle que tu n'as pas détaillé ici), selon moi, est que tu emploie un consistency-check plus fort que dans l'approche classique, ce qui aurait été justement intéressant si tu l'avais intégré au backtracking, ce qui n'est pas le cas.

Si tu veux montrer que ton approche est véritablement meilleure, il faudrait montrer qu'elle passe à l'échelle sur des grilles un peu plus sérieuses qu'un sodoku normal (16x16 ou même 25x25), qu'un backtracking est généralement incapable de résoudre.

C'est le genre d'heuristique qui marche dans le cas général (first-fail), il est fort possible que tu sois tombé sur un cas particulier. Et si le coût te semble supérieur au gain, on peut encore l'appliquer partiellement en triant les cases à visiter avant le backtracking (ce que je fais dans mon tuto).

Je suis curieux de savoir comment l'intégré au backtracking. Mais je te propose d'en parler en mp pour éviter de poluer le thread

Ça polluerait pas le topic je trouve. C'est intéressant.

Alors répondons ici

Mais je ne voudrait pas que ça "effraie" certains débutant de poster leur solution. Notamment à la génération de grille, qui est une première étape.

Comme je l'ai proposé plus haut, par exemple :

Ce serait intéressant d'aller aussi dans l'autre direction, à savoir « un algorithme qui allège le backtracking quand c'est possible ». Là tu commences par réduire la grille en affectant des nombres aux cases qui ne peuvent en contenir qu'un seul. Pourquoi ne pas faire ça à chaque étape du backtracking, plutôt qu'une fois seulement au début ?

Ça ressemble à ce que ferait un SAT-solver DPLL, non ?

@Ricocotam: Exactement comme dit Eusèbe, sans oublier de revenir en arrière une fois le backtrack fait (ie. annuler les changements effectués en cas de blocage). C'est surtout ce point qui risque d'être un peu délicat à gérer, mais rien de bien insurmontable.

En fait, c'est exactement comme ce que tu fais déja avec la contrainte de base dans le backtrack, mais là tu ajoute une contrainte supplémentaires (c'est ce que je voulais dire par "consistency-check plus fort"). La difficulté supplémentaire vient du fait qu'il peut y avoir plusieurs cases modifiées à chaque étape.

Si c'est bien fait, tu n'as même plus besoin de 2 étapes, tout se passe au sein du backtrack. (je crois que tu peux partir d'une grille vide, puis remplir les cases connues en premier dans le backtrack)

@Grimur: Pas trop. Tout ce qu'on peut dire, c'est qu'un SAT-solver DPLL emploie effectivement du backtracking (tout comme pas mal d'autres types de solvers de CSP), mais directement sur les contraintes exprimées en logique booléenne, et avec tout un tas d'optimisations pour une propagation des contraintes efficace. Et bien sûr, on y ajoute généralement des heuristiques avancées pour accélérer la recherche.

Exactement comme dit Eusèbe, sans oublier de revenir en arrière une fois le backtrack fait (ie. annuler les changements effectués en cas de blocage). C'est surtout ce point qui risque d'être un peu délicat à gérer, mais rien de bien insurmontable.

Une solution assez simple pour résoudre cela, c'est de garder une copie de la grille avant chaque descente dans le backtracking et de la récuperer lorsqu'on remonte.