Sudoku est un puzzle qui a connu une popularité mondiale depuis 2005. Pour résoudre un puzzle de Sudoku, il faut utiliser une combinaison de logique et d`essai et d`erreur. Plus de mathématiques est impliqué dans les coulisses: combinatoire utilisé dans le comptage des grilles de Sudoku valides, la théorie du groupe utilisé pour décrire les idées de quand deux grilles sont équivalentes, et la complexité de calcul en ce qui concerne la résolution de sudokus. 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] où chaque ligne de cette matrice donne l`index de ligne, l`index de colonne et la valeur entière de chaque élément apparaissant dans la matrice de Sudoku initiale. Le m-file Sudoku.
m appelle la fonction intégrée de Matlab, bintprog qui est disponible par l`intermédiaire de la boîte à outils d`optimisation. Sur un Mac G5 avec deux processeurs 2,7 GHz et 8 Go de mémoire, notre programme a trouvé la solution réalisable, présentée dans la figure 2, en 16,08 secondes. Certes, cette approche sera généralement plus lente qu`une technique qui exécute les étapes logiques qu`une personne utilise pour résoudre un puzzle Sudoku. Une telle implémentation est disponible à Sudoku Game-Wolfram démonstrations Project et est basé sur la mise en œuvre de Mathematica par Simons (Simons, 2005). En cliquant sur le graphique de la figure 2 va télécharger un fichier sudokuMatlab. jar qui est une application Java qui permet à l`utilisateur d`entrer dans Sudoku puzzles et les résoudre en utilisant Sudoku. m. Notez qu`un utilisateur doit posséder MATLAB et la boîte à outils d`optimisation pour utiliser l`application Java avec succès. 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. Notre BILP trouve au moins une solution réalisable, si elle existe. Alors que les puzzles de Sudoku sont définis comme ayant une solution unique, les auteurs ont parfois découvert des puzzles dans lesquels cette contrainte n`était pas remplie. Ces puzzles défectueux ont plusieurs solutions. Dans de tels cas, nous avons découvert que notre solution tout en étant correcte était distincte de la solution fournie par les créateurs de puzzle.