Programme pour rsoudre les sudokus:
						Michel Julier, 31/12/2006

Pour le lancer:
  - ouvrir une fentre de console:
    Dans Windows XP, si a n'existe pas dans
    le menu Dmarrer-Programmes, il faut faire ceci:
	Dmarrer - Excuter... - taper "cmd" puis Entre
    Dans Windows 98, c'est "command" au lieu de "cmd"

  - aller dans le rpertoire o se trouve le programme (avec CD)

  - utiliser une des mthodes suivantes:

	1) en ligne de commande:

sudoku xxxxx8x1x x37xxxxxx x5xx7x4x9  xxxxxx2xx xxx6xxxxx 41xxx2xx3  x71xxxxxx xx9x2x6x4 xx6x935xx

	2) en tapant ligne par ligne

sudoku -
xxxxx8x1x 
x37xxxxxx 
x5xx7x4x9  
xxxxxx2xx 
xxx6xxxxx 
41xxx2xx3  
x71xxxxxx 
xx9x2x6x4 
xx6x935xx

	3) en utilisant une grille existante dans un fichier

type expert.txt | sudoku -


Remarques:
  1) le "-" indique au programme que la grille est fournie dans l'entre standard
     c'est--dire soit au clavier, soit depuis un autre programme avec le "pipe": "|"
  2) dans tous les cas, les espaces, tabulations, fins de ligne, et caractres "-|+" 
     servant  dessiner les grilles sont ignors. Les autres, s'ils ne sont pas un
     chiffre de 1  9, sont considrs comme correspondant  une case encore vide
  3) si on veut mettre le rsultat dans un fichier, il suffit de rajouter "> fichier.txt"
      la fin de la commande. Exemple:

type expert.txt | sudoku - > resultat_expert.txt


****************
* Le programme *
****************

C'est un tout petit programme crit en C++, langage bien adapt dans ce cas.
Il fonctionne sous Linux et sous Windows de faon identique.
Pour Windows, il a t compil avec l'environnement Bloodshed Dev-C++ qui
utilise le compilateur Mingw-GCC.
L'excutable doit fonctionner tout seul sur n'importe quelle version
de Windows  partir de Windows 95.

**************
* La mthode *
**************

Je pense que ce programme est relativement intelligent. En tous cas, sur un PC,
le calcul est instantan.
Autre raffinement: le programme dit s'il y a une solution, ou aucune, ou bien
plusieurs (et dans ce cas il en exhibe deux). Il est amusant d'essayer avec une
grille vide:

sudoku xxxxxxxxx xxxxxxxxx xxxxxxxxx  xxxxxxxxx xxxxxxxxx xxxxxxxxx  xxxxxxxxx xxxxxxxxx xxxxxxxxx


La mthode de rsolution est la suivante:

 1) pour chaque case, on mmorise toutes les chiffres autoriss sur cette case:
    initialement, tous les chiffres sont possibles sur chaque case.

 2)  chaque fois qu'on crit un chiffre (qu'il soit donn dans l'nonc ou bien
    qu'on l'ait trouv plus tard), on retire ce chiffre de la liste des possibilits
    pour toutes les autres cases du carr, de la ligne, ou de la colonne

 3) la premire mthode essaye est nomme "triviale": s'il n'y a qu'une seule
    possibilit pour une case, eh bien on crit cette possibilit. C'est--dire
    quand tous les autres chiffres existent dj dans la ligne, la colonne, ou le carr.

 4) ensuite, on utilise la mthode "seule position possible", qui fonctionne de
    faon inverse. Pour chaque ligne, chaque colonne, et chaque carr, il doit
    apparatre chaque chiffre une fois et une seule. Si on constate, pour chacun
    des cas, que toutes les positions sauf l'une sont impossibles, on crit le chiffre
    en question  la position o ce n'est pas impossible.

 5) ensuite, on utilise la mthode "chiffres sur une ligne": dans chaque carr, si
    on n'a pas trouv la position d'un chiffre, mais on a trouv que toutes les
    positions possibilits de ce chiffre dans ce carr sont sur une mme ligne
    ou sur une mme colonne, alors on retire ce chiffre de la liste des possibilits
    pour toutes les cases de la mme ligne ou colonne situes sur les autres carrs.

 6) si on n'a toujours pas trouv la conclusion (c'est--dire soit la solution unique,
    soit une impossibilit), on passe  la mthode rcursive base sur des hypothses:

    - on fait la liste des cases pour lesquelles on peut faire des hypothses
    - on classe ces hypothses par nombre croissant de choix possibles
    - on dbute par celle qui a le moins de choix possibles
        (NB: en fait, cette hypothse mne forcment  la solution du problme,
         mais au dpart j'avais envisag d'autres stratgies pour explorer
         plusieurs hypothses en regardant laquelle aboutit le plus vite,
         mais j'y ai renonc car en fait a n'apportait aucune amlioration)
    - sur une copie de la grille, on crit successivement chaque choix possible,
      et  chaque fois on cherche la solution avec les mthodes non itratives
      prcdemment dcrites:
        - si une solution unique est alors trouve, on note cette solution
        - si une impossibilit est alors trouve, on note que ce choix ne convient pas
        - si la conclusion n'est pas trouve par les mthodes non itratives, on
          la cherche  nouveau par la mthode itrative:
            - si on trouve 2 solutions ou plus, c'est la conclusion
            - si on trouve une solution unique:
                - si c'est la premire que l'on trouve, on l'enregistre
                - si c'est la 2e, on conclut qu'il y a au moins 2 solutions
            - si on trouve une impossibilit, on ne fait rien
            - si on ne trouve pas la conclusion, on mmorise cela (ceci ne doit pas arriver)
    - Si on est tomb au moins une fois sur une absence de conclusion, on revient en
      disant que le problme est trop difficile pour ce programme (ceci ne doit pas arriver)
    - Si on n'a trouv aucune solution, la conclusion est une impossibilit.
    - Sinon (une seule solution trouve), la conclusion est qu'il y a une solution unique.

En se basant sur des exemples de sudokus, tirs de http://sudoku.koalog.com/ , j'ai trouv
  - les sudokus trs faciles, faciles, et moyens, se rsolvent avec les mthodes 1  4
  - le sudoku difficile demande l'aide de la mthode 5
  - le sudoku trs difficile demande la mthode itrative avec 1 hypothse (2 choix possibles)
  - le sudoku expert demande 3 hypothses successives (2 choix possibles  chaque fois)

NB: la fonction de rsolution marche galement pour les autres tailles. On peut indiquer
"-1" (sudoku stupide), "-2" (sudoku enfant), "-4" (sudoku humainement infaisable, avec des 
lettres de A  P), ou mme en thorie "-5" (lettres de A  Y) mais cette dernire option 
est dsactive (pas trs utile, et sur une grille vide a demande beaucoup de mmoire).


Exemples de commandes  coller dans la fentre de console (faire "copier" sur ce texte,
puis "clic droit" dans la consolle pour coller le texte):

  trs facile: 
sudoku 3xxx24xxx 6xxxx8xxx xxxxxx918  xxxxxxxxx 8xx5xxx3x xxxx4xx62  x2xx87xx4 xx4xxx5xx x1xxx32xx

  facile:
sudoku 2xxxx7x6x 37xxxxxxx xxx2xx19x  xxxxxx6xx 1xx84x5xx x3xxx6x8x  412xxxxxx xxxx2x7x9 xx5x1xxxx

  moyen: 
sudoku 2xxx7xx6x 613xxxxx4 xx43xx2xx  xxxxxx8x5 xxx1xx7xx x8xxx3x19  4x17xxxxx xx2xxx5xx xxxx5xxxx

  difficile: 
sudoku 2xxx65xxx x57xxxxxx xx893xx56  xxxxxxxx7 xxx1xxxxx 71xxx4x89  xx68xxxxx xx9x2x4x8 xxxx4x6xx

  tres difficile:  
sudoku 5xxxx84xx x6xxxxxxx xx39xxx8x  xxxxxxxx3 x9x5xx8xx 47xxx1xx2   186xxxxxx xxxx4x5xx xx5x6x1xx

  expert: 
sudoku xxxxx8x1x x37xxxxxx x5xx7x4x9  xxxxxx2xx xxx6xxxxx 41xxx2xx3  x71xxxxxx xx9x2x6x4 xx6x935xx

  grille vierge: 
sudoku xxxxxxxxx xxxxxxxxx xxxxxxxxx  xxxxxxxxx xxxxxxxxx xxxxxxxxx  xxxxxxxxx xxxxxxxxx xxxxxxxxx



Exemple de rsolution d'une grille diabolique (bien plus dur que la catgorie "trs difficile"
des journaux):

> sudoku 5.....4.6 ...3295.. ..1...... .......23 ...7.6... 89....... ......8.. ..8951... 4.6.....7

Entre:
+-------+-------+-------+
| 5 . . | . . . | 4 . 6 |
| . . . | 3 2 9 | 5 . . |
| . . 1 | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . 2 3 |
| . . . | 7 . 6 | . . . |
| 8 9 . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | 8 . . |
| . . 8 | 9 5 1 | . . . |
| 4 . 6 | . . . | . . 7 |
+-------+-------+-------+
Chiffre forcment sur une ligne: retrait de 17 possibilits

Passage  la recherche itrative base sur des hypothses
Nombre d'hypothses possibles  chaque niveau de rcursion:
2222 => chec
   \222 => chec
      \2 => chec
       \2 => chec
        \ => chec
     \ => chec
    \ => chec
  \ => chec
 \22 => chec
   \ => chec
  \ => chec
\22 => chec
  \ => solution
 \ => chec
Solution unique trouve!

Sortie:
+-------+-------+-------+
| 5 2 9 | 8 1 7 | 4 3 6 |
| 7 6 4 | 3 2 9 | 5 1 8 |
| 3 8 1 | 4 6 5 | 2 7 9 |
+-------+-------+-------+
| 6 4 5 | 1 9 8 | 7 2 3 |
| 1 3 2 | 7 4 6 | 9 8 5 |
| 8 9 7 | 5 3 2 | 6 4 1 |
+-------+-------+-------+
| 9 1 3 | 6 7 4 | 8 5 2 |
| 2 7 8 | 9 5 1 | 3 6 4 |
| 4 5 6 | 2 8 3 | 1 9 7 |
+-------+-------+-------+

***************************
* Amliorations possibles *
***************************

Pour certaines grilles trs difficiles, ce programme rsout le problme
en essayant diffrentes hypothses. Or il arrive qu'il existe des mthodes
de rsolution plus lgantes. Par exemple la grille "diabolique" indique
ci-dessus a t classe comme "pas trs difficile, ne ncessite pas
d'hypothses, mais trs inhabituelle" par mon pre. La mthode qu'il
utilise et que mon programme n'utilise pas est celle-ci:
  * 3 nombres dans 3 cases: si on peut trouver 3 cases d'une mme ligne,
colonne, ou carr, dont les possibilits sont constitues des 3 mmes
chiffres, alors sait que ces 3 chiffres sont impossibles sur les 6 autres
cases de la ligne, colonne, ou carr (respectivement).
  Exemple: sur la ligne n5, on constate que les possibilits restantes sont:
    * colonne 2: les chiffres 2, 5, 7
    * colonne 4: les chiffres 2, 7
    * colonne 5: les chiffres 5, 7
  Alors nous savons que sur la ligne n5, les chiffres 2, 5, 7 sont
  ncessairement sur les colonnes 2, 4, 5.
  Dans ce cas, nous savons que les chiffres 2, 5, 7 ne sont pas possibles
  dans le reste de la ligne n5, c'est--dire dans les colonnes 1,3,6,7,8,9.
Cependant, il semble que pour certaines grilles difficiles, mme en utilisant
cette mthode, on doit faire des hypothses pour pouvoir trouver la solution.