Sudoku !

Le classique !

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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.

Grille de sudoku "vide"

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 !

  • Une première méthode consiste à générer une grille aléatoire et enlever un certains nombre de case
  • Une deuxième méthode consiste à prendre une grille de départ résolue et à effectuer certaines opérations | dessus. Par exemple échanger les colonnes n°1 et n°2. Attention tout de même à ne pas échanger n'importe quoi (petit indice, les colonnes numéro n°3 et n°4 ne sont pas échangeable)

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

000000068900000002000400500041000000000035000050000000000800010300000700000100400 000000201004030000000000000370000080600200000000500000540000600000070040002001000 000000360430000000000500700000760000200000005000000100000042008070000040001000000 000000408900300000000100000000000530000005100200060000000720006054000000000000010 000000501100800000000000400005013000040000700000600000620000080000050020000004000 000000592080010000000000000600200400410000000000000000006504000300000010000700008 000000701060050000008000000000104000700000020030800000000070350004000600100000000 000000840000720000000100000200050006000004030100000000000200001040000500030007000 000001305600000100000020000004300070000005000000900000000070480510000000000600000 000010800050000000200000000800000100000207000000500004600300070000000350048000000 000040200030000800007000000040000001200080000000500070001700030600200400000000000 000050600104000000000003000020400000060080000000000010000300206300107000000000500 000060080020000000001000000070000102500030000000000400004201000300700600000000050 000071006500000030000000000000080100800300000000000007007400200010002000000500080 000081000300000500200000000060200300010000000000004000008000042500700000000060010 000100038200005000000000000050000400400030000000700006001000050000060200060004000 000107000900000200800000000002060000000400500000000701000030080070500000050000060 000200030060000040000000000070050900800300000000000000000067100400005070300000800 000200030060000040000000000090050800700300000000000000000069100400005060300000700 000200030070000040000000000060050900800300000000000000000067100400005070300000800 000200030090000040000000000060050800700300000000000000000069100400005060300000700 000300500200080000000000000063500000100000020000030040700002000000100004080000300 000309600200000050000000000500080000000400700000000001013000400000005030070020000 000358000600000100000000000160000005000700030200004000030500070000010200000000000 000400100250000000600050000070300000000800004000000020400020000030000700000006010 000400100250000000600050000070300000000800004000000020400020000030000900000006010 000400200083000000000000006010070000600000400000008300500320000007000080000000010 000500900000703000100000000000400037900020000000000040030060000000008100045000000 000600045300007000000000000600000007000002500040080000001050000020000060000700300 000600200100000000000030000000200609710000000000800000009504000080000300000070010 000600302040001000000000000203050000000000480006000000810000050000020700000300000 000600302040001000000000000203050000000000490006000000810000050000020700000300000 000600720810000000000040000200000801004500000000000200000300060700080000000000050 000620900801000000000000000400108000030000700000200000590070000000005020000000001 000700005300800000000000600000060300700000020000001000430050000060000001000200070 000800600070400000200000000300001000000020070001000400150000002004600000000000030 000810000300000040000000000670100000500000930000200000408003000020000001000000600 000870600200000000000100000060054000000000021400000000070000050000200300500001000 000900200450000000100000000008607000000000001000000040500021000070000600000040030 000940500210000000000008000302100000000000400800000000040000890000200030000060000 001430000700000080000000000000702000014000000000600020000060401850000000000000300 001700500600800000000000000000200004050000030090004000200000800400030000000050900 003100060080500000000000000007060200200000001000400500000082030040000000500000000 003400060500000001000000000000706400800000002000300000120080000000000630050000000 004036000100000500000000000062000000000050700000800200000002004700000030050700000 004600000000000780050000000010300500200000106000400000700010000008000040000000003 005000020000100000400000000000400108050000400009000000800620000030000700000009050 006005030020040000000000000300700000000010800005000400000200056040008000100000000 010009000000700200000000000000300160800400000000000502000010040200050000409000000 010050300000200000080000000020400800700620000300000100500000020000001000000000060 010050300000200000080000000020400800700620000300000100900000020000001000000000060 010050300000200000080000000060400800700620000300000100500000020000001000000000060 010050300000200000080000000060400800700620000300000100900000020000001000000000060 010050300000600000080000000060400800700260000300000100900000020000001000000000060 010050300000800000070000000020400700600280000300000100900000020000001000000000080 010050700000200000080000000020400800700620000300000100900000020000001000000000060 010050700000200000080000000060400800700620000300000100900000020000001000000000060 010050800000200000070000000020400700500620000300000100900000020000001000000000060 010050800000200000070000000060400700500620000300000100900000020000001000000000060 010400700000000280000000000208050000000001600005600000040000003000020050600000000 010400700000000290000000000209050000000001600005800000040000003000020050600000000 010500400000000290000000000209060000000001700006800000040000003000020060700000000 010500800000000290000000000209060000000001700006700000040000003000020060700000000 020001000000070800600000050000000021000630000080000000706000400500004000000200000 020001000000080900600000050000000021000630000040000000708000400500007000000200000 020500000000000308000000900300400050800030000000000010000020700050100000604000000 040000600000070100000080000050400000000000027000003000107200000000100530800000000 040060000000000350000010000009000100300800000000400060400200700060005000000000003 050000801003600000000000000204000060000071000000000008000400390070030000100000000 050060700008400000000000000400102000003000600000500200020070000000000034100000000 060300100007500000000000000000200005800000030040070000000018400002000800500000000 080000010004030000000600500600000003000020400010000000300108000000500070000000200 081020000030009000000000000700600500000180000000000001400005000000000130000000086 082700400000100000000000000310005000500040300000000000004093000600000010000000008 083000070000610000000000000601700000400000080000000002020408000500000100000000300 100000200003700000500400000200010000080000003000000040020300000600000100000007050 100030670720000000000000000000201400300000500000400000008000030040500000000000001 100300520080000000000000000005600000600000008000004070002000300070010000000080600 100600000407000000000800700003000500070000200000010000050302000600000040000000001 140000030000720000000000000080603000006000200000000100007500080200400000000080000 200000080000400030000005000000040006000700400800000500074000100030020000000008000 200000300000800500000001000080002040000030700000000000600070020057400000000000001 200100600004000500000000000030040000800000009000050700050700010000800030007000000 200500070060030000000000000000040501004008000050000020100700000003000400000200000 200500070060030000000000000000040501004009000050000020100800000003000400000200000 300050001000010000000000060002600300000204000000000005850000700000900020100000000 300600100007000008000000000080001000000300200005000060000540070020060000100000000 370000060000100000000000200000003400500000001000060000401500000000070058030000000 400600300200700000010000000000270000000000018000000050306000700050008000000010000 480001000000090200000000000050700008602030000000000010200400300030000000000008000 560100040000800000000000000301040000020000008000000700400000530700008000000200000 600050001000010000000000070002700300000204000000000005850000600000900020100000000 600130000004000800000000000007500000000020060080000030000400709300001000020000000 600400503000030700000000000000370100800000040200000000007000002000600080010000000 700000200030060000000000000060010000300000080000700500002400060500207000000000001 700040800000000390000000000013900000000070600000100000000050010600300000200000005 700081000000000530000000000000605200400300008000000000000070064005200000010000000 700600300000501000800000000040002000000070800010000000000400001006000020300050000 700800200050100000000000000300050060000400001006000080000026300001000000040000000 700800400000290000000000000021000090000500700000000010500000620300006000000010000 706080000900000001000400000000003600040200000000000900680009000000010040000000020 780200000000600500000000000050030000000001070006000020000050301200400000001000000 800093000000000601000000000500200040000701200000000000000020480010600000300000000 800094000000000701000000000300200050000701200000000000000030580010600000400000000 800100000000006400000000000680000020000050300700040000004300000000200080500000009 901006000800500000000000000040200000000000960000050000050000402300010000000009070 020000350000010000040000000800205000000000906000400000901060000700009000000000020 190000200000037000000000000607000800000100000300000000020400010005028000000000003 100000800000060200000300000200070000000001040080000030007000560040803000000000000 708000065000200400000000000000060001300000080040500000270000500000081000000000000 004000200010500000000000060600010000000020070030000000200000140007800000000300600 300500070060020009000000000000300500800000040010009000500470000000000901000000000 060205700000300000000000000300000200700001000001090000820600000000040009000000010 010600420000800000000050000005000030700400000000001000200030700000000504040000000 000010003450000000000000080000400700900000500008000006000701020060000400000080000 040030000000000201000000800001400000200000600000070000000506040600002000070000080 040030000000000801000000200001400000200000600000070000000506040600002000070000080 200304000000000070800000000000610700004000900600500000070000060000200003010000000 200405000000000010800000000000730100005000900700600000030000070000200004010000000 800405000000000010200000000000730100005000900700600000030000070000200004010000000 450060300070010000000000000600000050000003700001800000700000010000200008000009000 006000300040000050000080000000603500400200000100000000005700000000010004090000800 500100006000430000000000080000200300000007040100000000020000500040008000000050001 680010000000000250000000000000004006004500000070000100500200040003070000100000000 620000000000100500000000000200040050000020100070008000100000040005300000000700002 100500400000000680000000000020608000000000700000200000306070000000010020700000009 600200090000150000000000000510000700000800040070000008800000100400003000000070000 500040320000170000000000000830000600000720000000000000000008001020600000007000040 000570013400000000000000008000600420810000000000000000100420000050000600000001000 083000060000720000000000000000003010520000000700050000009004500000000204000100000 083000070000420000000000000000003010640000000200060000009005600000000405000100000 680000200000340000000000000050700080000000023900100000000008500003020000700000000 000600804301000000000000000700500030000200001000007000260000700040010000000000020 800000020000100800000070000420000600500700000000300001000040050000050007010000000 200400600000500010000000000500080004300020000000000080000705300008000002010000000 800600001000400020000000000053000000002050000040700000700001000000000250000020300 050000270000830000100000000020700000000040008500000300301000006000200050000000000 600020500900000030000000000001000007020060000000400010480000600000001002000300000 200500080001020000000000000070008000003000020000070600600200001040000700000300000 100000300060007000000080004500000710010800000000020000200001000000300008000000060 701000000000500020000040600540000010030060000000800000000000306900100000000000400 100800050000040030000600000060020900000003001000000000000900400300000200507000000 020008500000700060000000000400000007000020030000010000308600000000500002600000100 003090400800700000000000000500000904700200000000001600090060000000300020060000000 000060200080300000100000000064000300000500040000001000700100000002000600000040080 007000501200400000000000000820600000000010700000000000000200380005000060010004000 000007401200300000000000000080530000004000700000000000030000650000004080700010000 040000058300010000000000000501008000000000620600000000007000005000600100020300000 603200000000040001000000000002000940700001000000050000070400080150000000000000300 400000670050100000000000000070030000000000260080500000201000005600002000000080000 020000308000010000400000000500060010803000000000700000000800400070400000005000090 000300501080070000000000000000080200100500000004000070000401060350000000000000300 205700000800050300000000000090000100000200000000000030030081000400000020000900007 800600000000000450000001000000040700600000300000020000074000020000800001020300000 000360000020000800000100000100000060000002500000000007008000240300700000000040005 300040500000000001200000000070000300000108000400600000000070230008000060010000000 005000003000700400010080000040005200000300000200000000000020610703000000000004000 000600450070001000000300000000080600100000000000002000038040000000700010400000002 400700005000000070000200000630000800500000200000010000000004100070500000001000090 240000060000051000000000300000040800700500000000000001000200075018000000000900000 260000007000031000000000400000050030800100000000000900000600018039000000000500000 302400006500009000010000000000700400080000010000300000000080060700000300000010000 402500006300009000010000000000700500080000010000300000000080060700000400000010000 760000000000000408000010000000640100300000500008000000000500023000003060040000000 000200040800000300010000000002004000000080050070000100000710600400500000000000001 000300062010000000000000000050400100600050000000000008700208000300000500000040010 000306700820000000000000000006050020200000030050007000300200000000480000000000100 600000903000401000000000000000100080000073000900000004540030000080000010000000200 000940700021000000000000000700001300800000004000200000040005020300080060000000000 130000900000005008000200000000130000400000070000900000002007080000040100090000000 020100000000000050000060000500002070000400600001000000860007000000030001200000400 150000000600000800000900000302000070700000010000200000040017000000050900000000200 634000000000250000000000070250000030000100000300000000001000800070004000000030200 000000209300000010400000000000301000000600400000400500025080000070050000000000040 800300000050000040700010000100605700000400000000000000024000030000020800000001000 041000000600030000000200000700500008000004000000100000020000910000090200800003000 080500300000000240000000000500000001000007060300020000000300700004060000062000000 000401000005000700000000840000610003240000000500000000000200050001070000030000000 800010000000000053060000000000402600100000000000000002023600000000870010000000500 080000400300600000000700005100200000000000052400000000700000300000080060020050000 080000100300500000000600004100200000000000042700000000600000300000080050020040000 000200400005000800030070000000108030100400000000000050024000100000050000600000000 400750000002030000000000000000500064010000000000000080570000300000002100600400000 050003600200700000000000000830400000000020070000000100000001200700000040040060000 000040230800500000000000000060001000000020700300000400000300068002400000010000000

  • 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 !)

Édité par Ricocotam

+8 -0

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.

+2 -0

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".

Édité par anonyme

+1 -0

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

+0 -0
Staff

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.

+0 -0
Auteur du sujet

@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 !

Je vais essayer de vous expliquer comment j'ai fait de la manière la plus concise mais explicite possible, n'hésitez pas à poser vos questions !

La plus grande particularité de "ma méthode" réside dans la manière de stocker le sudoku. Accroché vous ce n'est pas forcément évident, surtout si vous êtes débutant.

Quand se pose la question de comment stocker l'ensemble des nombres du sudoku, on va presque automatiquement et naturellement faire un tableau à 2 dimensions. C'est donc ce que j'ai fais dans un premier temps. Et puis j'ai commencé avec la première méthode de résolution "humaine".

Cette méthode de résolution consiste a un simple algorithme : Pour chaque case, on regarde tout les nombres qu'il est possible de mettre (les nombres qu'on met en petit sur du papier) en respectant les règles du jeu. S'il n'y à qu'une seule possibilité alors on peut "inscrire" (les nombres qu'on met en gros sur du papier) ce nombre sur la grille pour avancer. De cette manière on va résoudre une très grande partie des grilles de Sudoku.

Pour cette méthode, il a fallut rajouté une troisième dimension à notre tableau à 2 dimensions de départ. En effet, pour chaque case il fallait stocker l'ensemble des possibilité (soit en utilisant un tableau de booléens, soit une liste des possibilités). On se retrouve donc avec 9x9x9 informations. Je trouvais ça vraiment beaucoup trop. En plus je me suis dit qu'on devait pouvoir aller plus vite que des comparaisons. En effet pour chaque case il fallait en parcourir 24 autre case ! ce qui fait au plus 2481 (1944) opérations par passage. On est pas à l'abri de faire 81 passages (ceci n'est bien sur que théorique). Soit 2481*81 (157 464) comparaisons. Et je vous passe toutes les autres opérations du style écriture dans le tableau. J'ai donc pensé à autre chose.

Comme vous le savez probablement, les nombres que vous gérez dans un programme ne sont en réalité que des séries de bits. Or une série de bits c'est un peu comme un tableau de bits non ? C'est ce que je me suis dit. J'ai donc décidé de totalement changé la manière de stocker mon information. Maintenant je possède toujours un tableau à 2 dimensions mais très différent. En effet, dans chacune de mes cases j'ai un nombre qui est une puissance de 2 (par exemple : 000000010, soit 4 en décimal) qui n'est pas le vrai nombre affiché. Si on prend 000000010 qui vaut 4 en décimal, il représente 2 dans mon programme. En fait dans chacune des cases c'est le nombre $2^x$ qui est inscrit, où x est le "vrai" nombre inscris dans la case (allant de 1 à 9 dans un sudoku classique). Cela peut vous paraître inutilement compliqué mais attendez de voir ce qui suit !

Une fois que j'avais fait ça, je me suis dit qu'il devait être possible de stocker plus intelligemment les "possibilités" d'une case. En effet, si ma case est un nombre comme : 110010010, donc qui n'est pas une puissance de 2, alors c'est qu'il y à différentes possibilités (en l’occurrence : 2, 5, 8 et 9). Toujours en me disant que ça pouvait être encore mieux, je me suis demander comment obtenir toute les possibilité d'une case pour une ligne, une colonne et un "carre" (un carré de 3x3) en le minimum d'opération logique (puisqu'on travail avec des bits). J'ai donc pensé à stocker mes lignes, colonnes et carrés de la même manière que chacune de mes petites cases. Ainsi chaque ligne (colonne et carré) est représenté par un seul nombre (par exemple : 110010010) et ce nombre représente toute les cases qui sont remplies (en l'occurrence, les nombres 2, 5, 8 et 9 sont présents dans la ligne).

Petit récapitulatif des informations stockées :

  • un tableau à 2 dimensions (9x9) contenant l'ensemble des cases (chaque case est un bit de la forme 110010010 qui stock toute les possibilités de la case)
  • 3 tableaux à une dimension chacun (de 9 cases) représentants les lignes, colonnes et carrés (chaque case est un bit de la forme 110010010 qui stock tout les nombres présent sur ce(tte) ligne, colonne ou carré.

Passons à l'utilité de tout ça. Maintenant, pour chaque case, il me suffit de 4 opérations pour connaître l'ensemble des possibilités de la dite case (plus quelques mises à jour mais on est bien en dessous des 24 opérations de comparaisons). Voici à quoi ressemble ce passage dans le code (c'est du Java). Ce n'est pas très important si vous ne comprenez pas tout, c'est juste pour vous montrer le nombre d'opération :

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;

Voici à quoi servait toutes ces complications. On arrive a faire exactement 8 opérations logique et 4 opérations mathématiques et 6 lectures pour chacune des cases. Contre (au pire des cas) 24 comparaisons, 24 lectures et (si c'est mal codé) 24 écritures. Le très gros avantage de ma méthode c'est que la taille de la grille n'influe pas sur les temps de calculs, la complexité (de cette opération) est en $O(0)$ c'est à dire qu'on ne peut pas faire mieux sur des très grandes grilles (on peut probablement faire mieux mais les temps de calculs ne sont pas très éloignés).

Maintenant que vous avez compris ma méthode, je l'ai appliqué à une autre technique pour des grilles plus compliquée mais avec des comparaisons beaucoup plus complexe (que je n'ai pas réussis à faire seul, merci à Lmghs). En espérant que ma méthode vous ait plu !

+0 -0

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.

+0 -0

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.

+0 -0
Auteur du sujet

@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).

+0 -0

@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.

+0 -0

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

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+2 -0

@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.

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.

Berdes

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).

+0 -0

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 ^^

Ricocotam

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 ?

+1 -0

@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.

Édité par yoch

+0 -0

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.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte