Algorithme de résolution de Sudoku C ++

J’essaie de faire un programme de résolution de sudoku pendant quelques jours mais je suis coincé avec les méthodes. J’ai trouvé cet algorithme ici mais je ne le comprends pas vraiment:

Commencez par la première cellule vide et mettez-y 1.

Vérifiez tout le tableau et voyez s’il y a des conflits

S’il y a des coflicts sur le tableau, augmentez le nombre dans la cellule actuelle de 1 (changez donc 1 en 2, 2 en 3, etc.)

Si le tableau est propre, recommencez à la première étape.

Si les neuf nombres possibles sur une cellule donnée provoquent un conflit dans le tableau, vous définissez cette cellule à vide, vous revenez à la cellule précédente et vous recommencez à partir de l’étape 3 (c’est ici que le ‘retour en arrière’ entre).

Voici mon code. Je pense que quelque chose ne va pas avec ma fonction Help_Solve (…) . Pouvez-vous m’aider à identifier le problème, s’il vous plaît?

#include  #include  #include  #include  #include  using namespace std; class Sudoku { private: int board[9][9]; int change[9][9]; public: Sudoku(); void Print_Board(); void Add_First_Cord(); void Solve(); void Help_Solve(int i, int j); bool Check_Conflicts(int p, int i, int j); }; Sudoku Game; void setcolor(unsigned short color) //The function that you'll use to { //set the colour HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAtsortingbute(hcon,color); } Sudoku::Sudoku() { for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++) board[i][j] = 0; } void Sudoku::Print_Board() { for(int i = 1; i <= 9; i++) { for(int j = 1; j <= 9; j++) { if(change[i][j] == 1) { setcolor(12); cout << board[i][j] << " "; setcolor(7); } else cout << board[i][j] << " "; if(j%3 == 0) cout << "| "; } cout << endl; if(i%3 == 0) cout << "------+-------+---------" << endl; } } void Sudoku::Add_First_Cord() { board[1][1] = 5; change[1][1] = 1; board[1][2] = 3; change[1][2] = 1; board[1][5] = 7; change[1][5] = 1; board[2][1] = 6; change[2][1] = 1; board[2][4] = 1; change[2][4] = 1; board[2][5] = 9; change[2][5] = 1; board[2][6] = 5; change[2][6] = 1; board[3][2] = 9; change[3][2] = 1; board[3][3] = 8; change[3][3] = 1; board[3][8] = 6; change[3][8] = 1; board[4][1] = 8; change[4][1] = 1; board[4][5] = 6; change[4][5] = 1; board[4][9] = 3; change[4][9] = 1; board[5][1] = 4; change[5][1] = 1; board[5][4] = 8; change[5][4] = 1; board[5][6] = 3; change[5][6] = 1; board[5][9] = 1; change[5][9] = 1; board[6][1] = 7; change[6][1] = 1; board[6][5] = 2; change[6][5] = 1; board[6][9] = 6; change[6][9] = 1; board[7][2] = 6; change[7][2] = 1; board[7][7] = 2; change[7][7] = 1; board[7][8] = 8; change[7][8] = 1; board[8][4] = 4; change[8][4] = 1; board[8][5] = 1; change[8][5] = 1; board[8][6] = 9; change[8][6] = 1; board[8][9] = 5; change[8][9] = 1; board[9][5] = 8; change[9][5] = 1; board[9][8] = 7; change[9][8] = 1; board[9][9] = 9; change[9][9] = 1; } bool Sudoku::Check_Conflicts(int p, int i, int j) { for(int k = 1; k <= 9; k++) if(board[i][k] == p) return false; for(int q = 1; q <= 9; q++) if(board[q][j] == p) return false; /* *00 000 000 */ if((j == 1 || j == 4 || j == 7) && (i == 1 || i == 4 || i == 7)) { if(board[i][j+1] == p || board[i][j+2] == p || board[i+1][j] == p || board[i+2][j] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || board[i+2][j+1] == p || board[i+2][j+2] == p)return false; } /* 000 000 *00 */ if((j == 1 || j == 4 || j == 7) && (i == 3 || i == 6 || i == 9)) { if(board[i-1][j] == p || board[i-2][j] == p || board[i][j+1] == p || board[i][j+2] == p || board[i-1][j+1] == p || board[i-1][j+2] == p || board[i-2][j+1] == p || board[i-2][j+2] == p)return false; } /* 000 *00 000 */ if((j == 1 || j == 4 || j == 7) && (i == 2 || i == 5 || i == 8)) { if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p || board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || board[i][j+2] == p || board[i+1][j+2] == p)return false; } /* 0*0 000 000 */ if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 5 || i == 7)) { if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p || board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p || board[i][j+2] == p || board[i+1][j+2] == p)return false; } /* 000 0*0 000 */ if((j == 2 || j == 5 || j == 8) && (i == 2 || i == 5 || i == 8)) { if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j+1] == p || board[i][j+1] == p || board[i][j-1] == p || board[i+1][j+1] == p || board[i][j] == p || board[i+1][j-1] == p)return false; } /* 000 000 0*0 */ if((j == 2 || j == 5 || j == 8) && (i == 3 || i == 6 || i == 9)) { if(board[i][j-1] == p || board[i][j+1] == p || board[i-1][j] == p || board[i-1][j+1] == p || board[i-1][j-1] == p || board[i-2][j] == p || board[i-1][j+1] == p || board[i-2][j-1] == p) return false; } /* 00* 000 000 */ if((j == 3 || j == 6 || j == 9) && (i == 1 || i == 4 || i == 7)) { if(board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p || board[i+1][j-1] == p || board[i+1][j-2] == p || board[i+2][j] == p || board[i+2][j-1] == p || board[i+2][j-2] == p) return false; } /* 000 00* 000 */ if((j == 3 || j == 6 || j == 9) && (i == 2 || i == 5 || i == 8)) { if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j-2] == p || board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p || board[i+1][j-1] == p || board[i+1][j-2] == p) return false; } /* 000 000 00* */ if((j == 3 || j == 6 || j == 9) && (i == 3 || i == 6 || i == 9)) { if(board[i][j-1] == p || board[i][j-1] == p || board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j-2] == p || board[i-2][j] == p || board[i-2][j-1] == p || board[i-2][j-2] == p) return false; } return true; } void Sudoku::Help_Solve(int i, int j) { if(j <= 0) { i = i-1; j = 9; } if(change[i][j] == 1) return Game.Help_Solve(i, j-1); for(int p = 1; p <= 9; p++) if(Game.Check_Conflicts(p, i, j)) { board[i][j] = p; return; } return Game.Help_Solve(i, j-1); } void Sudoku::Solve() { for(int i = 1; i <= 9; i++) { for(int j = 1; j <= 9; j++) { if(board[i][j] == 0 && change[i][j] == 0) { Game.Help_Solve(i, j); } } } for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++) if(board[i][j] == 0) Game.Help_Solve(i, j); } int main() { Game.Add_First_Cord(); Game.Solve(); Game.Print_Board(); system("pause"); return 0; }

Edit: J’ai besoin d’utiliser la récursivité non? Mais peut-être que les parameters que je donne à la fonction sont faux. Je ne sais vraiment pas. Dans Add_First_Cord (), je déclare les valeurs de départ que chaque sudoku a au début. Voici les valeurs que j’utilise: http://bg.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Sudoku-by-L2G-20050714.gif . Je m’attends à voir le sudoku résolu tel qu’il est montré dans wikipedia. Mais certaines valeurs résolues sont correctes, d’autres non. Voici ce que je reçois dans la console entrez la description de l'image ici

Approche suggérée

Implémenter un algorithme de recherche de graphes générique
- pourrait utiliser la recherche de graphes IDFS ou A *
  - Je préférerais le second
- faites cela pour un graphe général dirigé
  - type de noeud TNode
  - fonction successeur de noeud TNode => vector
Définissez vos états de Sudoku
- un état est un tableau 9×9 avec un nombre 1, 2, …, ou 9 ou un blanc dans chaque position
Définir ce qu’est un objective État du Sudoku
- les 81 cellules remplies
- les 9 rangées ont des nombres {1, 2, …, 9}
- les 9 colonnes ont des nombres {1, 2, …, 9}
- les 9 carrés 3×3 ont tous des nombres {1, 2, …, 9}
Définissez votre fonction de successeur d’état de Sudoku valide
- un état S peut avoir le numéro N ajouté à la ligne I , colonne J si:
  - la cellule (I,J) est vide
  - il n’y a pas d’autre N dans la rangée I
  - il n’y a pas d’autre N dans la colonne J
  - il n’y a pas d’autre N dans le carré 3×3 contenant (I,J)
- la fonction successeur d’état mappe un état S sur le vector d’états satisfaisant ces règles
Appliquez votre algorithme générique de recherche de graphes (1) au graphe d’état de Sudoku (2-4)
(facultatif) Si vous choisissez d’utiliser la recherche de graphes A *, vous pouvez également définir une heuristique sur votre espace d’état de Sudoku afin d’accroître considérablement les performances.
- comment concevoir l’heuristique est un autre problème, c’est plus un art qu’une science

Approche actuelle

Votre approche actuelle combine la spécification du graphique à rechercher et la mise en œuvre de l’algorithme de recherche . Vous allez avoir beaucoup de difficulté si vous mélangez les deux. Ce problème se sépare naturellement en deux parties distinctes – l’algorithme et le graphique – afin que vous puissiez et devriez l’exploiter dans votre implémentation. Cela simplifiera beaucoup les choses.

L’autre avantage que vous obtenez si vous optez pour cette séparation est que vous pourrez réutiliser votre algorithme de recherche de graphes sur un très grand nombre de problèmes – très cool!

Ce qui suit suppose que vous essayez de résoudre un tableau donné et non de générer un puzzle.

Approche de base (simple)

Créez une classe dont les objects peuvent contenir un tableau (appelé ici board_t ). Cette classe peut utiliser en interne un tableau, mais doit prendre en charge la copie de cartes.

Avoir une fonction void solve(board_t const& board); qui répète ce qui suit pour chaque nombre n :

Copie votre entrée
Entre n dans la première cellule vide du tableau copié
Si la carte copiée est une solution, imprimez la solution et return .
Sinon si le conseil est toujours viable (par exemple, aucun conflit):
- appel à solve(copied_board)

Performance

C’est une solution de retour arrière récursive, qui fonctionne horriblement pour les problèmes difficiles. Vous pouvez l’accélérer de manière significative en procédant à un élagage approprié ou à des étapes déductives (par exemple, si vous vous retrouvez avec 8 chiffres consécutifs après en avoir inséré un, vous pouvez entrer immédiatement le neuvième sans effectuer de recherche).

Raisonnement

Bien que ce ne soit certainement pas une technique impressionnante, elle a une forte probabilité de fonctionner correctement, car vous ne modifierez jamais une copie que pour append une valeur unique. Cela évite la corruption de vos structures de données (vous avez notamment pour objective de détruire les chiffres trouvés lors du retour arrière, ce ne sont pas nécessairement ceux que vous venez d’insérer, mais ils peuvent faire partie du puzzle initial).

Améliorer les performances est assez simple, une fois que vous avez commencé à sélectionner des heuristiques plus intelligentes (par exemple, au lieu de tester l’ordre des carrés, vous pouvez sélectionner ceux qui ont le moins de déplacements à leur disposition et essayer de les écarter – ou faire l’inverse … ) ou commencer à faire un peu de déduction et d’élagage.

Remarque: le manuel de conception d’algorithmes utilise un solveur de Soduko pour montrer l’impact de ces techniques sur le retour en arrière.

Une modification très importante est apscope aux algorithmes récursifs: utilisez la première approche la plus contrainte. Cela signifie d’abord résoudre une cellule avec le plus petit nombre de candidats possibles (lorsque les conflits directs entre lignes / colonnes / blocs sont supprimés).

Une autre modification consiste à: changer le tableau en place; ne le copiez pas. Dans chaque appel récursif, vous ne modifiez qu’une cellule du tableau et cette cellule était vide. Si cet appel n’aboutit pas dans un tableau résolu quelque part dans l’arborescence des appels récursifs, effacez à nouveau la cellule avant de retourner – le tableau reprend son état d’origine.

Vous pouvez trouver une solution très courte et rapide en C # à l’adresse: Sudoku Solver . Il résout le tableau de sudoku arbitraire en environ 100 étapes seulement, le tout grâce à la première heuristique la plus contrainte.

C’est un problème classique de satisfaction de contrainte. Je recommande de faire des recherches sur le sujet pour déterminer la stratégie réussie. Vous devrez utiliser l’algorithme AC-3 (cohérence d’arc 3) ainsi que les techniques de retour en arrière pour résoudre le problème.