Browse By

Modele de sudoku

Bien qu`il s`agit d`une application amusante pour les classes qui étudient l`optimisation, il n`est pas nécessaire d`utiliser un BILP ou même des techniques d`optimisation pour résoudre les puzzles de Sudoku. Pouvez-vous utiliser d`autres techniques mathématiques ou computationnelles pour résoudre ces énigmes? Écrivez votre propre algorithme. Peut-on résoudre des puzzles de Sudoku mathématiquement? En d`autres cas, un processus mathématique peut-il trouver la solution pour nous? Il y a deux approches que nous pourrions prendre à cette fin: lorsque les valeurs des variables de décision sont déterminées, nous saurons si chaque entier k (1 Le k Le 9) apparaît dans chaque élément (i, j) de la matrice n times n Sudoku. C`est-à-dire que la solution au puzzle Sudoku correspondant sera définie. Un Sudoku standard contient 81 cellules, dans une grille de 9 × 9, et a 9 cases, chaque boîte étant l`intersection de la première, du milieu, ou des 3 dernières lignes, et le premier, le milieu, ou les 3 dernières colonnes. Chaque cellule peut contenir un nombre de un à neuf, et chaque nombre ne peut se produire qu`une fois dans chaque ligne, colonne et boîte. Un Sudoku commence avec quelques cellules contenant des nombres (indices), et le but est de résoudre les cellules restantes. Les Sudokus appropriés ont une solution. Les joueurs et les enquêteurs peuvent utiliser un large éventail d`algorithmes informatiques pour résoudre Sudokus, étudier leurs propriétés, et faire de nouveaux puzzles, y compris Sudokus avec des symétries intéressantes et d`autres propriétés. Un Sudoku peut être construit pour travailler contre le backtracking.

En supposant que le solveur fonctionne de haut en bas (comme dans l`animation), un puzzle avec peu d`indices (17), pas d`indices dans la rangée supérieure, et a une solution “987654321” pour la première rangée, travaillerait en opposition à l`algorithme. Ainsi, le programme consacrait un temps significatif à «compter» vers le haut avant qu`il arrive à la grille qui satisfait le puzzle. Dans un cas, un programmeur a trouvé un programme de force brute a exigé six heures pour arriver à la solution pour un tel Sudoku (quoique utilisant un ordinateur de 2008-ère). [1] un tel Sudoku peut être résolu de nos jours en moins de 30 secondes en utilisant une routine de recherche exhaustive et des processeurs plus rapides. [citation nécessaire] Nous nous tournons maintenant vers la fonction objective et l`ensemble de contraintes toujours importants. Remarquez comment les contraintes exigent seulement une connaissance des règles des puzzles de Sudoku (avec l`addition d`une contrainte implicite qui est contrainte (4) ci-dessous) et ne nécessitent pas une compétence avec la logique nécessaire pour résoudre ces puzzles à la main. Une formulation BILP adaptée aux puzzles Sudoku est la suivante: nous allons modéliser mathématiquement le puzzle Sudoku trouvé dans la figure 1 comme un programme linéaire. Plus précisément, nous formulerons un programme linéaire d`entiers binaires (BILP) pour les puzzles généraux n times n.

Une fois que le programme est développé pour résoudre le BILP pour la figure 1, il peut être facilement adapté pour résoudre n`importe quel puzzle Sudoku. Retrouvez toutes les solutions au puzzle Sudoku ci-dessous. (Astuce: il y a 3.) La figure 2. Solution par exemple Sudoku Puzzle dans figure 1. Une méthode courante de recherche de sudokus avec une caractéristique particulière est appelée recherche voisine. En utilisant cette stratégie, un ou plusieurs Sudokus connus qui satisfont ou presque satisfont la caractéristique recherchée est utilisé comme point de départ, et ces Sudokus sont ensuite modifiées pour rechercher d`autres Sudokus avec la propriété recherchée. L`altération peut être de déplacer une ou plusieurs positions d`indice, ou de supprimer un petit nombre d`indices, et de les remplacer par un nombre différent d`indices. Par exemple, à partir d`un Sudoku connu, une recherche d`un nouveau avec un moins d`indices peut être effectuée en supprimant deux indices et en ajoutant un indice dans un nouvel emplacement. (Cela peut être appelé une recherche {-2, + 1}). Chaque nouveau modèle serait alors recherché de manière exhaustive pour toutes les combinaisons de valeurs d`indice, avec l`espoir qu`un ou plusieurs rendements un Sudoku valide (c.-à-d.