Friends of the Alien

Introduction

Sudoku, aussi connu comme «Number Place» est un jeu de logique dont l'objectif est relativement simple: la base des chiffres déjà sont donnés à placer sur chacune de ses cellules, un nombre qui n'est pas déjà soit dans le même dans la même colonne ou ligne, ou dans le même quadrant ou un secteur.

Sudoku modèles varient, mais la plus répandue, est composée de 9 lignes sur 9 colonnes, 9 places, chacun de ses 9 quadrants et dans chacune de ses lignes et de colonnes doit être placée compose le numéro 1 à 9. Un exemple pourrait être:

Présentation de la solution

Le retour arrière est une technique de programmation qui peut commencer par la définition de la récursion (voir la définition de la récursion) avec la différence que dans le retour en arrière, car il ya des chemins différents à choisir, une fois atteint la finale et ne remplissait pas les mis en condition, retourner et continuer à rechercher des itinéraires de rechange ou différents et peut-être incorrecte.

L'idée de revenir en arrière si vous n'avez pas encore compris, il semble assez bon dans ces exemples tirés de l'évêque et le pion, les parcours du roi et de la N-Brouillons.

Je charger mon propre programme qui permet de résoudre des puzzles de sudoku posés par la technique de retours en arrière. Rappelez-vous que la meilleure technique est beaucoup moins pour résoudre des énigmes, mais pratiquement recourir à la force brutale pour résoudre les conflits avec la possibilité de revenir en arrière et en regardant plus de routes.

Processus de résolution

Le conseil d'Sudoku à résoudre est donné par un parent "Sol [1 .. 9,1 .. 9] de 0 .. 9" où Sun [i, j] représente la valeur que prend la cellule, correspondant à 0 avec une case vide. Il utilise une première matrice "auxiliaire [1 .. 9 1 .. 9] de Bool" où initiale [i, j] représente une cellule avec une valeur initiale peut ne changera pas et correspond à la cellule "Sol [i, j] ".

Lorsque l'arbre de branchement de l'exploration, nous ferons que si la solution partielle, c'est que nous traitons k-prometteur, qui est, si au bout solution partielle peuvent continuer à construire des solutions partielles. Pour traiter cette question, nous utilisons un assistant fonction appelée "es_factible.

L'arbre de navigation généré aura les caractéristiques suivantes:

• Hauteur = m + 1: Etre m le nombre de cases vides initialement.
• Nombre d'enfants de chaque node = 9: Un enfant pour chaque valeur possible de la cellule ij

Télécharger

Le programme que j'ai fait inclut tous les fichiers texte qui sont dans le dossier de débogage du projet et le processus génère un fichier de solution pour chaque sudoku et un fichier de résumé général avec le temps pris pour résoudre chacun d'eux. Je laisse le code source et d'un rapport au format pdf.