Swisslinux.org

jean@adimp.ch · 14 Jul 2008 09:44:46

Salut,
Je m'intéresse au sudoku, est-ce que quelqu'un connait un petit manuel de formules mathématiques sur ce jeu? Ou un programme open source dont je pourrais m'inspirer?
Meilleures salutations.

P.S.: trouvé ceci : http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

Dernière modification par jean@adimp.ch (14 Jul 2008 09:53:41)

BOFH · 14 Jul 2008 14:53:11

Hello,

Quel est le but ? les résoudre ou les générer ?

Pour les résoudres, je connais deux techniques: la programmation linéaire (qui est mathématiquement pure, et donne une solution instantanée, sans étapes intermédiaires), et l'algo dédié trivial.

Pour l'algo dédié, tu peux utiliser une simple itération sur deux contraintes de base (pas 2x le même chiffre dans un groupe, au moins 1x chaque chiffre dans un groupe), ce qui d'expérience suffit a résoudre toutes les grilles ~ jusqu'au niveau "difficile". Pour les autres, une descente récursive dans les possibilités restantes est assez rapide.

Voila mon implémentation en Perl:
http://xolus.net/hg/cudoku/file/c1458bf83a54/Sudoku/

Pour la génération, tu peux partir d'une grille canonique et lui appliquer des permutations aléatoires (colonnes, lignes, bandes de colonnes ou de lignes, substitution d'un chiffre par un autre, etc). Ensuite, pour déterminer la solvabilité c'est plus compliqué, mais si tu as déja un algorithme de résolution correct, j'imagine que tu peux itérer en enlevant des cellules dans la grille jusqu'a ce qu'elle devienne insolvable.

jean@adimp.ch · 14 Jul 2008 16:10:07

Salut,
Merci.
Est-ce que tu sais combien de grilles remplies possible il y a? D'après moi, j'aurais dit 9!+2*6!+3*3!.
Meilleures salutations.

fonji · 15 Jul 2008 19:26:02

J'aurai planché sur le backtracking moi...

jean@adimp.ch · 16 Jul 2008 10:58:18

Salut,
@Fonji : désolé, je ne suis pas ta réflexion, peux-tu argumenter un peu plus? Merci.
Meilleures salutations.

fonji · 19 Jul 2008 00:07:49

Le backtracking est une technique qui s'applique relativement bien à ce genre de problème.
L'idée est de créer la liste de possibilités pour la première case, tu choisis la première, tu passes à la case suivante, etc.
Si tu arrives à la dernière case avec une (ou plus) possibilité, c'est gagné.
Sinon, dès que tu bloques, tu retournes en arrière d'une case et tente la possibilité suivante (si t'es au bout de la liste, tu recules encore d'une, etc), jusqu'à ce que tu arrives à la solution.

Ça semble être un peu "brute force" mais ça permet de trouver une solution relativement rapidement (puisque, finalement, en moyenne c'est la moitié des solutions qui sont envisagées) ou de s'assurer d'avoir testé toutes les possibilités, le tout avec un minimum de code à taper.
Bon bien sûr faut assurer en récursivité hein...

C'est un peu décousu et abbrégé comme ça, ça m'a demandé 1h30 de cours et 1h30 de travail pratique pour commencer à comprendre, et c'était il y a plus de deux ans, alors si jamais ça t'intéresse, devrait il y avoir de quoi faire sur le net...

BOFH · 19 Jul 2008 03:23:35

Oui, c'est ce que moi j'ai appelé "descente récursive". Mais pour que ce soit raisonnablement performant, il faut que la recherche locale entre chaque étape soit efficace.

Pour accélérer la recherche, il est aussi souhaitable de ne pas fixer l'ordre des cases dans la descente, mais de commencer par la case qui a déja le nombre minimum de possibilités par rapport à la grille existante.

jean@adimp.ch · 20 Jul 2008 17:11:06

Salut,
Merci pour vos réponses, je vais faire des test avec 2x2 grilles de 2x2 cases avec des chiffres de 1 à 4.

exemple:

1 2 | 3 4
3 4 | 1 2
----------
4 1 | 2 3
2 3 | 4 1

Ce qui m'intéresse surtout, pour l'instant, c'est de trouver un moyen de générer toutes les grilles. Et aussi un moyen de savoir combien de grilles il y a.

Meilleures salutations.
Jean Tinguely Awais.

fonji · 20 Jul 2008 22:16:24

Ben générer toutes les grilles, ça marche comme dit avant, sauf qu'il n'y a pas de condition de base. Enfin c'est même encore plus simple.
Après pour générer les grilles, une fois que tu arrives à la dernière case, tu fais une sortie par possibilité restante (il doit y en avoir plus qu'une normalement), tu incrémentes un compteur et basta.

jean@adimp.ch · 08 Aug 2008 17:24:40

Salut,
Ci-dessous un petit programme en python. Le code est aussi diponible sur le svn.
Le programme génère toutes les grilles pleines et ensuite il teste si les grilles ont les propriétés des sudokus.

Code:

# coding=UTF-8
# test sur des sudokus simplifiés ( 4 lignes de 4 colones définissant 4 cellules )

def isSudoku(sudokuNumber, sudokuList, permutationList):
 ret=True
 allLines=sudokuList[sudokuNumber]
 # creer le modele
 modell=[]
 for x in allLines:
  modell.extend(permutationList[x])
 # tester les colones
 col1=[modell[0],modell[4],modell[8],modell[12]]
 col2=[modell[1],modell[5],modell[9],modell[13]]
 col3=[modell[2],modell[6],modell[10],modell[14]]
 col4=[modell[3],modell[7],modell[11],modell[15]]
 if not col1 in permutationList:
  ret=False
 if not col2 in permutationList:
  ret=False
 if not col3 in permutationList:
  ret=False
 if not col4 in permutationList:
  ret=False
 if ret:
   if col1==col2 or col1==col3 or col1==col4:
    ret=false
   if col2==col3 or col2==col4 or col2==col1:
    ret=false
   if col3==col1 or col3==col2 or col3==col4:
    ret=false
   if col4==col1 or col4==col2 or col4==col3:
    ret=false
 # tester les cellules
 if ret:
  if not [modell[0],modell[1],modell[4],modell[5]] in permutationList:
   ret=False
  if not [modell[2],modell[3],modell[6],modell[7]] in permutationList:
   ret=False
  if not [modell[8],modell[9 ],modell[12],modell[13]] in permutationList:
   ret=False
  if not [modell[10],modell[11],modell[14],modell[15]] in permutationList:
   ret=False
 return ret

# etape 1 : trouver les permutations 
set=[1,2,3,4]
rotateAllSet={}
permutation=0
for x in set:
 subset1=[]
 subset1.extend(set)
 subset1.remove(x)
 for y in subset1:
  subset2=[]
  subset2.extend(subset1)
  subset2.remove(y)
  #print str(permutation)+': '+str(x)+' '+str(y)+' '+str(subset2)
  #permutation+=1
  for z in subset2:
   subset3=[]
   subset3.extend(subset2)
   subset3.remove(z)
   rotateAllSet[permutation]=[x,y,z,subset3[0]]
   permutation+=1

allSudokus={}
permutation=0
# etape 2 : créer les sudokus possibles 255024 possibilitées
for x in rotateAllSet.keys():
 subset1=[]
 subset1.extend(rotateAllSet)
 subset1.remove(x)
 for y in subset1:
  subset2=[]
  subset2.extend(subset1)
  subset2.remove(y)
  for z in subset2:
   subset3=[]
   subset3.extend(subset2)
   subset3.remove(z)
   for v in subset3:
    allSudokus[permutation]=[x,y,z,v]
    permutation+=1   


# etape 2 : créer les sudokus possibles 331776 possibilitées
#for x in rotateAllSet.keys():
# for y in rotateAllSet.keys():
#  for z in rotateAllSet.keys():
#   for v in rotateAllSet.keys():
#    allSudokus[permutation]=[x,y,z,v]
#    permutation+=1


count=1
for x in allSudokus.keys():
 rotateAllSetSet=[]
 for z in rotateAllSet.keys():
  rotateAllSetSet.append(rotateAllSet[z])
 if isSudoku(x, allSudokus, rotateAllSetSet): 
  #print "---------------------------------"
  print str(count)+". Sudoku numero "+str(x)
  for z in allSudokus[x]:
   print str(rotateAllSet[z])
  print "---------------------------------"
  count+=1

Meilleures salutations.

jean@adimp.ch · 11 Aug 2008 12:41:21

Salut,
J'ai réussit à générer les grilles pleines, maintenant j'aimerais placer les espaces. Est-ce que quelqu'un a une idée ou connaît un truc?
Meilleures salutations.
Jean Tinguely Awais.

P.S. : liste des grilles pleines : http://www.t-servi.com/cgi-bin/trac.cgi … /4x4x4.txt

Edit : Lu!

BOFH a écrit:
Pour la génération, tu peux partir d'une grille canonique et lui appliquer des permutations aléatoires (colonnes, lignes, bandes de colonnes ou de lignes, substitution d'un chiffre par un autre, etc). Ensuite, pour déterminer la solvabilité c'est plus compliqué, mais si tu as déja un algorithme de résolution correct, j'imagine que tu peux itérer en enlevant des cellules dans la grille jusqu'a ce qu'elle devienne insolvable.

Dernière modification par jean@adimp.ch (11 Aug 2008 12:53:12)

Pygnol · 13 Aug 2008 14:39:03

J'ai eu cet ouvrage qui m'est passé dans les mains: http://www.amazon.com/Programming-Sudok … 1590596625

C'était intéressant et... amusant.

Thierry

jean@adimp.ch · 13 Aug 2008 15:59:25

Salut,
@Pygnol : Merci. En fait je serais plus intéressé par quelques articles mathématiques sur le sujet.
Actuellement j'ai deux questions en suspens :
1) Comment arriver mathématiquement à la quantité de grilles complètes ( pour l'exemple 4x4 = 288 ) ?
2) Comment faire pour générer les grilles vides?
Est-ce que ce livre peut répondre à ces questions?
Meilleures salutations.
Jean Tinguely Awais.

Edit :
D'après moi la réponse à la première question permet de trouver la réponse à la seconde question. Je vois bien que les probabilités se multiplient, mais je ne sais pas encore pourquoi les possibilités diminuent plus vite que prévu ( peut-être ne saurais-je jamais ).

Dernière modification par jean@adimp.ch (13 Aug 2008 16:06:27)

Pygnol · 13 Aug 2008 20:33:56

jean@adimp.ch a écrit:
Salut,
@Pygnol : Merci. En fait je serais plus intéressé par quelques articles mathématiques sur le sujet.
Actuellement j'ai deux questions en suspens :
1) Comment arriver mathématiquement à la quantité de grilles complètes ( pour l'exemple 4x4 = 288 ) ?
2) Comment faire pour générer les grilles vides?
Est-ce que ce livre peut répondre à ces questions?
Meilleures salutations.
Jean Tinguely Awais.

Edit :
D'après moi la réponse à la première question permet de trouver la réponse à la seconde question. Je vois bien que les probabilités se multiplient, mais je ne sais pas encore pourquoi les possibilités diminuent plus vite que prévu ( peut-être ne saurais-je jamais ).

D'après mes souvenirs, ce livre présentait comment générer une grille ainsi que les techniques à mettre en oeuvre pour les résoudre. L'auteur n'utilise pas de formalisme mathématique et implante les algos directement en Visual Basic. Je n'aime personnellement pas ce langage, mais les algorithmes sont relativement compréhensibles et il n'est pas trop difficile de généraliser. Je n'ai pas lu cet ouvrage très à fond. C'était juste par curiosité, et puis je l'avais sous la main. Mais c'est une resource qui tiens la route et Apress est une maison d'édition que j'apprécie en général pour la qualité de ces contributions. Maintenant, on doit certainement trouver d'autres resources sur le web qui abordent le problème sous un angle plus mathématique. Je jeterai un coup d'oeil si j'ai le temps.

Thierry

jean@adimp.ch · 14 Aug 2008 21:31:27

Salut,
J'ai eu une autre idée que je développe sur l'exemple ci-dessous :

Code:

--------------------------------------------------------------------------------------------------------------------------------------------------------
1. generation par casier indépendants
--------------------------------------------------------------------------------------------------------------------------------------------------------

exemples de génération d'une grille de sudoku sur l'ensemble [1..4]

grille du 1 grille du 2 grille du 3 grille du 4 grille finale
=========== =========== =========== =========== ===========
 0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0
 0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0
----------- ----------- ----------- ----------- -----------
 0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0
 0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0   0 0 | 0 0
=========== =========== =========== =========== ===========

Il y a une grille par chiffres et une grille finale.
Au départ, chaque grille est vide
Il y a 16 possiblités de commencer dans la grille 1.

--------------------------------------------------------------------------------------------------------------------------------------------------------
1.1 mettre un chiffre dans un casier
--------------------------------------------------------------------------------------------------------------------------------------------------------

grille du 1 grille du 2 grille du 3 grille du 4 grille finale
=========== =========== =========== =========== ===========
 1 1 | 1 1   0 0 | 2 2   0 3 | 0 0   0 0 | 4 0   1 0 | 0 0
 1 1 | 0 0   2 2 | 2 2   0 3 | 0 0   0 0 | 4 0   0 0 | 2 0
----------- ----------- ----------- ----------- -----------
 1 0 | 0 0   0 0 | 2 0   3 3 | 0 0   0 0 | 4 4   0 0 | 0 0
 1 0 | 0 0   0 0 | 2 0   3 3 | 3 3   4 4 | 4 4   0 3 | 4 0
=========== =========== =========== =========== ===========

On insère un chiffre par casier.
Dans chaque grille par chiffre, on biffe les lignes, les colonnes et les casiers occupés en plaçant le chiffre de la grille dans les emplacements biffés
La grille finale est remplie.
Il reste 6 possibilités par nombre par gille.

--------------------------------------------------------------------------------------------------------------------------------------------------------
1.2 mettre un chiffre dans un autre casier en faisant attention aux lignes et colonnes occupées
--------------------------------------------------------------------------------------------------------------------------------------------------------

grille du 1 grille du 2 grille du 3 grille du 4 grille finale
=========== =========== =========== =========== ===========
 1 1 | 1 1   2 2 | 2 2   0 3 | 0 3   4 0 | 4 0   1 2 | 0 0
 1 1 | 1 1   2 2 | 2 2   0 3 | 0 3   4 0 | 4 0   0 0 | 2 1
----------- ----------- ----------- ----------- -----------
 1 0 | 0 1   0 2 | 2 0   3 3 | 3 3   4 4 | 4 4   4 0 | 0 3
 1 0 | 0 1   0 2 | 2 0   3 3 | 3 3   4 4 | 4 4   0 3 | 4 0
=========== =========== =========== =========== ===========

Dans chaque grille par chiffre, on biffe les lignes, les colonnes et les casiers occupés en plaçant le chiffre de la grille dans les emplacements biffés
La grille finale est remplie.
Il reste 4 possibilités par gille.

--------------------------------------------------------------------------------------------------------------------------------------------------------
1.3 mettre un chiffre dans un autre casier en faisant attention aux lignes et colonnes occupées
--------------------------------------------------------------------------------------------------------------------------------------------------------

grille du 1 grille du 2 grille du 3 grille du 4 grille finale
=========== =========== =========== =========== ===========
 1 1 | 1 1   2 2 | 2 2   3 3 | 0 3   4 4 | 4 4   1 2 | 0 4
 1 1 | 1 1   2 2 | 2 2   3 3 | 3 3   4 0 | 4 4   3 0 | 2 1
----------- ----------- ----------- ----------- -----------
 1 1 | 1 1   0 2 | 2 2   3 3 | 3 3   4 4 | 4 4   4 1 | 0 3
 1 1 | 0 1   2 2 | 2 2   3 3 | 3 3   4 4 | 4 4   0 3 | 4 2
=========== =========== =========== =========== ===========

Dans chaque grille par chiffre, on biffe les lignes, les colonnes et les casiers occupés en plaçant le chiffre de la grille dans les emplacements biffés
La grille finale est remplie.
Il reste 1 possibilités par gille.

--------------------------------------------------------------------------------------------------------------------------------------------------------
1.4 terminer et vérifier
--------------------------------------------------------------------------------------------------------------------------------------------------------

grille du 1 grille du 2 grille du 3 grille du 4 grille finale
=========== =========== =========== =========== ===========
 1 1 | 1 1   2 2 | 2 2   3 3 | 3 3   4 4 | 4 4   1 2 | 3 4
 1 1 | 1 1   2 2 | 2 2   3 3 | 3 3   4 4 | 4 4   3 4 | 2 1
----------- ----------- ----------- ----------- -----------
 1 1 | 1 1   2 2 | 2 2   3 3 | 3 3   4 4 | 4 4   4 1 | 1 3
 1 1 | 1 1   2 2 | 2 2   3 3 | 3 3   4 4 | 4 4   2 3 | 4 2
=========== =========== =========== =========== ===========


Dans chaque grille par chiffre, on biffe les lignes, les colonnes et les casiers occupés en plaçant le chiffre de la grille dans les emplacements biffés
La grille finale est remplie.
Il reste 0 possibilités par gille.

Il est aussi possible de générer par ligne ou par colonnes. 
Le nombre de pas dépend de l'ensemble de départ.
Cette façon de faire peut aussi servir pour la résolution de sudoku.

Approximation du total des possibilités :
Cas pessimiste = 16 * 6 * 4 + 12 * 6 * 4 + 8 * 6 * 4 + 4 * 6 * 4 = 3840 possibilités


Sources :
http://www.geometer.org/mathcircles/sudoku.pdf
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

Pygnol · 18 Aug 2008 07:35:45

Peut-être que ce post peut t'intéresser:
http://www.developpez.net/forums/d54373 … se-sudoku/

Thierry

jean@adimp.ch · 29 Aug 2008 13:48:34

Salut,
J'avance à petits pas. Un premier essai ici : http://www.t-servi.com/cgi-bin/trac.cgi … endants.py

Meilleures salutations.

Edit : essai basé à peu prés sur la méthode décrite ci-dessus.

Dernière modification par jean@adimp.ch (29 Aug 2008 13:50:34)

Swisslinux.org

− Le carrefour GNU/Linux en Suisse −

Recherche

Menu

Forum

Identification

Inscription

Langue

Le Forum

#1 14 Jul 2008 09:44:46

[Algorithme] Sudoku

#2 14 Jul 2008 14:53:11

Re: [Algorithme] Sudoku

#3 14 Jul 2008 16:10:07

Re: [Algorithme] Sudoku

#4 15 Jul 2008 19:26:02

Re: [Algorithme] Sudoku

#5 16 Jul 2008 10:58:18

Re: [Algorithme] Sudoku

#6 19 Jul 2008 00:07:49

Re: [Algorithme] Sudoku

#7 19 Jul 2008 03:23:35

Re: [Algorithme] Sudoku

#8 20 Jul 2008 17:11:06

Re: [Algorithme] Sudoku

#9 20 Jul 2008 22:16:24

Re: [Algorithme] Sudoku

#10 08 Aug 2008 17:24:40

Re: [Algorithme] Sudoku

Code:

#11 11 Aug 2008 12:41:21

Re: [Algorithme] Sudoku

BOFH a écrit:

#12 13 Aug 2008 14:39:03

Re: [Algorithme] Sudoku

#13 13 Aug 2008 15:59:25

Re: [Algorithme] Sudoku

#14 13 Aug 2008 20:33:56

Re: [Algorithme] Sudoku

jean@adimp.ch a écrit:

#15 14 Aug 2008 21:31:27

Re: [Algorithme] Sudoku

Code:

#16 18 Aug 2008 07:35:45

Re: [Algorithme] Sudoku

#17 29 Aug 2008 13:48:34

Re: [Algorithme] Sudoku

Pied de page des forums