Programmation du Jeu SUDOKU "intelligent"

Bonjour à tous et à toutes :

Pour les passionné(e)s de l'intelligence Artificielle, est-ce que vous avez une idée sur le fameux jeu de réflexion "Sudoku" ?

Les problèmes "Sudoku", on en trouve des dizaines dans les journaux: La Presse par exemple...

Pour ceux/celles qui ne connaissent pas le jeu, aller voir ces sites:

http://www.grilles-sudoku.com/le-sudoku.html
http://www.sudoku-land.com/pres-sudoku/presentation-sudoku.php
http://www.zen-sudoku.be/presentation-sudoku.php
http://www.zen-sudoku.be/regles-sudoku.php



Bref, c'est un jeu de réflexion qui se joue en "solo" çàd: mono-joueur. Le but est de trouver les nombres manquants dans une grille en vérifiant certaines contraintes de difficulté croissante.

Où se trouve l'IA dans ce jeu ?
C'est essentiellement dans la résolution d'une grille, ou l'aide à la résolution d'une grille.

à suivre... (next: "Sudoku" intelligent : c'est quoi? )

Un mathématicien Finlandais a présenté lundi ce qui serait le sudoku connu le plus difficile à résoudre, un véritable casse-tête ayant requis trois mois de travail et l'examen d'un milliard de combinaisons. «AI Escargot est le Sudoku le plus difficile connu jusqu'à présent»,

a affirmé son créateur, Arto Inkala, 37 ans, docteur en mathématiques appliquées. «J'ai appelé ce puzzle AI Escargot parce qu'il ressemble à un escargot et que tenter de le résoudre s'apparente au plaisir de la cuisine», souligne ce spécialiste de modélisation environnementale dont les initiales, AI, forment l'acronyme anglais d'«intelligence artificielle». Un classement (en Anglais) confirme la suprématie d'«AI Escargot» au palmarès des fameuses grilles réputées les plus inextricables. Le Sudoku des Sudoku requiert en effet de prendre en compte huit causes et effets alors que les Sudoku grand public les plus compliqués n'exigent de considérer qu'une ou deux combinaisons à la fois, explique M. Inkala. La grille infernale a déjà été résolue par des amateurs autres que son concepteur, qui promet d'ores et déjà d'en produire de plus infernales encore à l'aide de logiciels informatiques.

News #13 - Auteur : AFP - Date : 9
nov. 2006
Source : Agence France Presse
“
AI Escargot”, le sudoku le plus dur au
monde

Télécharger le sudoku le plus difficile du monde

Télécharger la solution de la grille de sudoku la plus difficile

Mathématiques

Il est évident que le nombre de grilles complètes est inférieur au nombre de façons de placer neuf chiffres 1, neuf chiffres 2, ..., neuf chiffres 9 dans une grille de 81 cases. Le nombre de grilles est donc très inférieur à



En effet, dans ce décompte, on ne tient compte d'aucune des contraintes d'unicité. Le nombre de grilles complètes possibles est également inférieur au nombres de carrés latins de côté 9. Enfin, le nombre de grilles complètes possibles est inférieur à 9!⁹ qui correspondrait au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.

En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvé que ce nombre de grilles était de :



Ce nombre est égal à :



Le dernier facteur est un nombre premier. Ce résultat a été prouvé grâce à une recherche exhaustive. Frazer Jarvis a ensuite considérablement simplifié la preuve grâce à une analyse détaillée. La démonstration a été validée de manière indépendante par Ed Russell. Jarvis et Russell ont par la suite montré qu'en tenant compte des symétries, il y avait 5 472 730 538 solutions.

En revanche, à cette date, aucun résultat n'existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16). Si maintenant, on s'intéresse aux nombres de problèmes proposables, ce nombre est nettement plus important car il existe plusieurs façons de révéler les chiffres d'une même grille.

Le problème de savoir combien de cases remplies sont nécessaires au préalable pour rendre la résolution unique est, à ce jour, sans réponse. Le meilleur résultat, obtenu par des Japonais, est de 17 cases
sans contrainte de symétrie. Rien ne dit que ce ne soit pas possible avec moins de nombres. Gordon Royle indique que deux résolutions sont considérées comme différentes si elles ne peuvent pas être transformées l'une vers l'autre (ou l'inverse) grâce à une combinaison des opérations suivantes :

• permutations des 9 nombres
  
• échange des lignes avec les colonnes (transposition)
  
• permutation des lignes dans un seul bloc
  
• permutation des colonnes dans un seul bloc
  
• permutation des blocs sur une ligne de blocs
  
• permutation des blocs sur une colonne de blocs
  

On remarque l'analogie avec les opérations matricielles en algèbre linéaire.

Mathématiques

Le problème de placer des chiffres sur une grille de n²×n² comprenant n×n régions est NP-complet . Cela signifie qu'il n'existe pas d'algorithme efficace (polynomial) pour résoudre tous les Sudoku. Sur les grilles de taille finie, la résolution peut se faire via un automate fini qui connaît l'ensemble de l'arbre du jeu.

La résolution d'un Sudoku peut être formalisée par le problème de la coloration de graphe. Le but, dans la version classique du jeu, est d'appliquer 9 couleurs sur un graphe donné, à partir d'un coloriage partiel (la configuration initiale de la grille). Ce graphe possède 81 sommets, un par cellule. Chacune peut être
étiquetée avec un couple ordonné (x,y), où x et y sont des entiers compris entre 1 et 9. Deux sommets distincts étiquetés par (x,y) et (x',y') sont reliés par une arête si et seulement si :

• x=x' ou,
  
• y=y' ou,
  
• [x/3] = [x'/3] et [y/3] = [y'/3]
  

Le puzzle se complète en affectant un entier entre 1 et 9 pour chaque sommet, de façon que tous les sommets liés par une arête ne partagent pas le même entier.

Une grille solution est aussi un carré latin. Il y a notablement moins de grilles solutions que de carrés latins, car le Sudoku impose des contraintes supplémentaires. Néanmoins, le nombre de grilles solution valides de taille 9×9, calculé par Bertram Felgenhauer en 2005, serait de 6 670 903 752 021 072 936 960. Ce nombre est égal à 9! × 72² × 2⁷ × 27 704 267 971, ce dernier nombre étant un premier. Ce résultat est obtenu en partie par la logique et en partie par calculs en:brute force. Frazer Jarvis a notablement
simplifié la méthode de calcul et Ed Russell a confirmé le résultat.
Russell et Jarvis ont aussi démontré que lorsqu'il y a symétrie, il reste 5 472 730 538 solutions.

Le nombre maximum de dévoilés sans qu'une solution unique n'apparaisse immédiatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et que exactement deux cellules sont dans une région, alors il existe deux façons d'inscrire les candidats. L'opposé de ce problème, à savoir le nombre minimum de dévoilés pour garantir une solution unique, est un problème non résolu, bien que des enthousiastes japonais aient découvert une grille 9×9 sans symétrie qui contient seulement 17 dévoilés, alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.
__________
[source]

Quelques essais extraits du net :

Vous m'avez rappelé le 3ème DS d'informatique à l'IPEIEM (pour 2ème année préparatoire): Jetez un coup d'oeil sur le 2ème exercice:
http://www.sendspace.com/file/2hhc42

Lamice a écrit:Vous m'avez rappelé le 3ème DS d'informatique à l'IPEIEM (pour 2ème année préparatoire): Jetez un coup d'oeil sur le 2ème exercice:
http://www.sendspace.com/file/2hhc42

Oui c'est intéressant comme DS !!!