<?php
/*************************/
/*  Resolveur de Sudoku  */
/*      By Clems, 2006   */
/*************************/
$start = explode(' ', microtime());
 
/*function vide (int)
Sert pour savoir si le sudoku est rempli ou non
Fonction de callback par array_filter*/
function vide($valeur) 
{
   return ($valeur == 0); //renvoie TRUE si $valeur vaut 0, FALSE sinon
}
 
/*function affichage(array)
Sortie Html pour affiche le sudoku de maniere comprehensible*/
function affichage($sudoku)
{
   echo '<table style="border: 1px solid black; border-colapse: colaspe">';//initialisation du tableau
   $sudoku = decoupe($sudoku);//on rend le sudoku plus organise, pour avoir les coordonnees  x|y  des cases
   for($i=1; $i<10; $i++)
   {
      echo '<tr>'; //ligne
      for($j=1; $j<10; $j++)
      {
         echo '<td style="'; //cellule
         if($j%3 == 0 && $j != 9) echo 'border-right: 1px solid black;'; //si c'est la droite d'un carre, on trace la bordure
         if($i%3 == 0 && $i != 9) echo 'border-bottom: 1px solid black;'; //si c'est le bas d'un carre, on trace la bordure
         echo '"><input size="1" readonly="readonly" maxlength="1" value="';
         if ($sudoku['ligne'.$i][$j] != 0) echo $sudoku['ligne'.$i][$j]; //si la case n'est pas vide, on l'affiche
         echo '"/></td>';
      }
      echo '</tr>';//fin ligne
   }
   echo '</table><br />'; //fin de l'affichage
}
 
/*function decoupe(array)
Decoupe le sudoku de maniere a connaitre le contenu de chaques lignes, colones, et carre, pour connaitre plus tard les valeurs admissibles pour les cases vides*/
function decoupe($sudoku)
{   
   $decoupe = array();//initialisation de l'array
   for($x=1; $x<10; $x++) //pour chaque ligne
   {
      ${'ligne'.$x} = array(); //initialisation de la ligne
      for($y=1; $y<10; $y++) //chaque cellule de la ligne en cours
      {
         ${'ligne'.$x}[$y] = $sudoku[$x.'|'.$y]; //on remplis l'array "ligne_numero X" avec la valeur qui va bien
      }
      $decoupe['ligne'.$x] = ${'ligne'.$x};//et on mets la ligne dans l'array qui contient tout => $decoupe
   }
   for($y=1; $y<10; $y++) // Bon, la, je refais pas tout les commentaires, c'est exactement pareil, mais avec les colones :-D
   {
      ${'colone'.$y} = array();
      for($x=1; $x<10; $x++)
      {
         ${'colone'.$y}[$x] = $sudoku[$x.'|'.$y];
      }
      $decoupe['colone'.$y] = ${'colone'.$y};
   }
   $i = 1; //initialisation du compteur pour le numero des carres
   for($centre_x=2; $centre_x<=8; $centre_x+=3)//pour chaque centre de carre
   {
      for($centre_y=2; $centre_y<=8; $centre_y+=3)//idem : pour chaque centre de carre
      {
         ${'carre'.$i} = array();//initialisation du carre_munero_I
         $j = 1; //initialisation du compteur pour les cases des carres
         for($x=$centre_x-1; $x<=$centre_x+1; $x++)// la...
         {
            for($y=$centre_y-1; $y<=$centre_y+1; $y++)//... et la, on fait le tour du centre du carre, donc on parcour tout le carre :-)
            {
               ${'carre'.$i}[$j] = $sudoku[$x.'|'.$y]; //et on mets la valeur de la case correspondante dans l'array  carre_munero_I...
               $j++; //case suivante
            }
         }
         $decoupe['carre'.$i] = ${'carre'.$i}; //... qu'on met ensuite dans l'array qui contient tout => $decoupe
         $i++; //carre suivant
      }
   }
   return $decoupe; //et on revoie le tout,  bien ficele :-)
}
 
/*function possible(string CASE, array SUDOKU)
Renvoie les valeurs possibles pour la case CASE, en se basant sur le sudoku SUDOKU*/
function possible($case, $sudoku)
{   
   $coord_case = explode('|', $case); //decoupe des coordonnees
   $x_case = $coord_case[0]; //l'abscisse de la case
   $y_case = $coord_case[1]; //l'ordonnee de la case
   
   $decoupe = decoupe($sudoku); //on decoupe le sudoku
   $possible = array(1, 2, 3, 4, 5, 6, 7, 8, 9); //toute les valeurs possible pour une case
   $possible = array_diff($possible, $decoupe['ligne'.$x_case]); //on enleve a ces valeurs toutes celles de la ligne qui contient la case
   $possible = array_diff($possible, $decoupe['colone'.$y_case]); //on enleve a ces valeurs toutes celles de la colone qui contient la case
   
   if($y_case <= 3 && $x_case <=3) $possible = array_diff($possible, $decoupe['carre1']); //ca...
   elseif($y_case <= 6 && $x_case <= 3) $possible = array_diff($possible, $decoupe['carre2']); //... et ca...
   elseif($y_case <= 9 && $x_case <= 3) $possible = array_diff($possible, $decoupe['carre3']); //... et ca...
   elseif($y_case <= 3 && $x_case <= 6) $possible = array_diff($possible, $decoupe['carre4']); //... et ca...
   elseif($y_case <= 6 && $x_case <= 6) $possible = array_diff($possible, $decoupe['carre5']); //... et ca...
   elseif($y_case <= 9 && $x_case <= 6) $possible = array_diff($possible, $decoupe['carre6']); //... et ca...
   elseif($y_case <= 3 && $x_case <= 9) $possible = array_diff($possible, $decoupe['carre7']); //... et ca...
   elseif($y_case <= 6 && $x_case <= 9) $possible = array_diff($possible, $decoupe['carre8']); //... et ca...
   elseif($y_case <= 9 && $x_case <= 9) $possible = array_diff($possible, $decoupe['carre9']); //... et ca, ca sert a determiner dans quel carre se trouve la case, et a enlever au valeurs possibles toutes celles deja mise dans le carre
   
   if(!empty($possible)) //si il y a une ou des valeurs possibles
   {
      return array_values($possible); //on les renvoie
   }
   else
   {
      return FALSE; //sinon, FALSE, pour dire que la case est impossible a remplir :'(
   }
}
 
/*function init()
Initialise le sudoku en fonction des valeurs envoyees via le formulaire*/
function init()
{
   $a_remplir = array(); //on initialise le tableaux qui va contenir toutes les cases devant etre remplies (celles laissees vides par l'utilisateur, quoi :-p)
   $sudoku = array(); //et on initialise l'array sudoku, qui contiendra les valeurs de chaques cases.
   for($x=1; $x<10; $x++) //ca...
   {
      for($y=1; $y<10; $y++)// ... et ca, c'est pour parcourir toutes les cases
      {
         $sudoku[$x.'|'.$y] = (intval($_POST[$x.'|'.$y]) < 10 && intval($_POST[$x.'|'.$y] > 0)) ? intval($_POST[$x.'|'.$y]) : 0; //si la valeur envoyer par l'utilisateur et bien compris entre 1 et 9, on la mets dans l'array SUDOKU, sinon, on mets 0 a la place, comme case a remplir
         if ($sudoku[$x.'|'.$y] == 0) $a_remplir[] = array($x.'|'.$y, '', 0); //et si la case du soduku est vide, on l'ajoute a l'array A_REMPLIR,  qui va contenir toutes les cases devant etre remplies
      }
   }
   return array($sudoku, $a_remplir); //et on renvoie l'ensemble
}
 
function verif_grille($sudoku)
{
   $decoupe = decoupe($sudoku);
   $erreur = '';
   for($i = 1; $i<10; $i++)
   {
      if(array_diff($decoupe['ligne'.$i], array_filter($decoupe['ligne'.$i], "vide")) != array_unique(array_diff($decoupe['ligne'.$i], array_filter($decoupe['ligne'.$i], "vide"))))
      {
         $erreur .= 'La ligne '.$i.' comporte une erreur : 2 chiffres ou plus sont identiques.<br />';
      }
      if(array_diff($decoupe['colone'.$i], array_filter($decoupe['colone'.$i], "vide")) != array_unique(array_diff($decoupe['colone'.$i], array_filter($decoupe['colone'.$i], "vide"))))
      {
         $erreur .= 'La colone '.$i.' comporte une erreur : 2 chiffres ou plus sont identiques.<br />';
      }
      if(array_diff($decoupe['carre'.$i], array_filter($decoupe['carre'.$i], "vide")) != array_unique(array_diff($decoupe['carre'.$i], array_filter($decoupe['carre'.$i], "vide"))))
      {
         $erreur .= 'Le carre '.$i.' comporte une erreur : 2 chiffres ou plus sont identiques.<br />';
      }
   }
   return $erreur;
}
 
/*function retour(int NUMERO_CASE_ORIGIN)
Si la case a remplir numero NUMERO_CASE_ORIGIN  + 1 est impossible a remplir, on revient en arriere, en modifiant la case precedente numero NUMERO_CASE_ORIGIN, de maniere a avoir des valeurs possibles*/
function retour($numero_case)
{
   global $a_remplir, $sudoku, $nb_case_remplie, $erreur_commise; //on recupere toutes les variables dont on a besoin
   $erreur_commise += 1;
   $case_a_modif = $a_remplir[$numero_case][0]; //on determine les coordonees de la case a remplir, grace a son numero, et a l'array A_REMPLIR
   $valeur_possible = $a_remplir[$numero_case][1]; //on determine les valeurs possibles de la case a remplir, grace a son numero, et a l'array A_REMPLIR
   $valeur_test = $a_remplir[$numero_case][2]; //on determine quelles valeurs possibles de la case a remplir ont deja ete testees, grace a son numero, et a l'array A_REMPLIR
   if (!empty($valeur_possible[$valeur_test])) //Si il existe encore une valeur possible non-teste
   {
      $sudoku[$case_a_modif] = $valeur_possible[$valeur_test]; //on remplace l'ancienne valeur par celle-ci
      $a_remplir[$numero_case][2] += 1; //et on signal que l'on vient de tester une valeur de plus
      $possible = possible($a_remplir[$numero_case+1][0], $sudoku); //on redefinit les nouvelles valeurs possible pour la case suivante (celle qui bloquait
      $a_remplir[$numero_case+1][1] = $possible; //et on les insere dans l'array A_REMPLIR qui les retients
   }
   else //sinon, plus de valeur possible, cette case n'est donc pas modifiable, il faut revenir a celle d'avant encore
   {
      $sudoku[$case_a_modif] = 0; //on remet la case a 0 ( = a remplir)
      $a_remplir[$numero_case][2] = 0; //on remet son compteur de case teste a 0
      $nb_case_remplie--; //et on signal que l'on est revenu une case en arriere
      $numero_case = ($numero_case > 1) ? $numero_case-1 : 0; //on verifie qu'on donne pas un numero de case negatif(il n'y a pas de numero de case negatif :-p), sinon, on le remet a 0
      retour($numero_case);//ET REBELOTTE, on recommence :-D
   }
}
 
//une grille par defaut
$grille_defaut = array('1|1' => '',
                  '1|2' => '',
                  '1|3' => 5,
                  '1|4' => '',
                  '1|5' => '',
                  '1|6' => 7,
                  '1|7' => '',
                  '1|8' => '',
                  '1|9' => 1,
                  '2|1' => '',
                  '2|2' => '',
                  '2|3' => '',
                  '2|4' => '',
                  '2|5' => '',
                  '2|6' => '',
                  '2|7' => 4,
                  '2|8' => 6,
                  '2|9' => 3,
                  '3|1' => 8,
                  '3|2' => 1,
                  '3|3' => 9,
                  '3|4' => '',
                  '3|5' => '',
                  '3|6' => '',
                  '3|7' => '',
                  '3|8' => '',
                  '3|9' => '',
                  '4|1' => '',
                  '4|2' => '',
                  '4|3' => '',
                  '4|4' => 3,
                  '4|5' => 1,
                  '4|6' => 5,
                  '4|7' => '',
                  '4|8' => '',
                  '4|9' => '',
                  '5|1' => 2,
                  '5|2' => '',
                  '5|3' => 3,
                  '5|4' => '',
                  '5|5' => '',
                  '5|6' => '',
                  '5|7' => 8,
                  '5|8' => '',
                  '5|9' => 7,
                  '6|1' => '',
                  '6|2' => '',
                  '6|3' => '',
                  '6|4' => 7,
                  '6|5' => 2,
                  '6|6' => 8,
                  '6|7' => '',
                  '6|8' => '',
                  '6|9' => '',
                  '7|1' => '',
                  '7|2' => '',
                  '7|3' => '',
                  '7|4' => '',
                  '7|5' => '',
                  '7|6' => '',
                  '7|7' => 5,
                  '7|8' => 9,
                  '7|9' => 6,
                  '8|1' => 6,
                  '8|2' => 2,
                  '8|3' => 8,
                  '8|4' => '',
                  '8|5' => '',
                  '8|6' => '',
                  '8|7' => '',
                  '8|8' => '',
                  '8|9' => '',
                  '9|1' => 1,
                  '9|2' => '',
                  '9|3' => '',
                  '9|4' => 4,
                  '9|5' => '',
                  '9|6' => '',
                  '9|7' => 3,
                  '9|8' => '',
                  '9|9' => '');
                  
if(!empty($_POST)) //si le formulaire est soumis
{
   $init = init(); //on initialise le tout
   $sudoku = $init[0]; //on definit l'array SUDOKU
   $a_remplir = $init[1]; //on definit l'array A_REMPLIR
   $valide = verif_grille($sudoku);
   if($valide == '')
   {   
      $sudoku_depart = $sudoku; //ca, c'est juste pour garder en memoire la grille de depart, et l'afficher a la fin
      
      $is_vide = array_filter($sudoku, "vide"); //on verifie que l'utilisateur a pas soumis une grille deja pleine :-p (on sait jamais :-p)
      $nb_case_remplie = 0; //et on signale qu'on n'a pas encore remplis de case
      
      $erreur_commise = 0;
      $coup = 0;
      $start = explode(' ', microtime()); //temps de depart
 
      while(!empty($is_vide)) //tant que le sudoku n'est pas plein, on execute la routine de remplissage suivant :
      {
         $coup++;
         $case_a_remplir = $a_remplir[$nb_case_remplie][0]; //definition des coordonnees de la case a remplir grace a son numero, et l'array A_REMPLIR
         $possible = possible($case_a_remplir, $sudoku); //on determine les valeurs possibles de la case a remplir, grace a son numero, et a l'array A_REMPLIR
         if(!empty ($possible)) //si il y a au moins une valeur possible
         {
            $a_remplir[$nb_case_remplie][1] = $possible; //on remplis les caracteristique de la case, contenues dans l'array A_REMPLIR
            $sudoku[$case_a_remplir] = $possible[0]; //et on mets la premiere valeur possible dans la case que l'on est en train de remplir
            $a_remplir[$nb_case_remplie][2] += 1; //on signal que l'on vient de tester une valeur de plus
            next($a_remplir); //et on passe a la case suivante, toujours contenu dans l'array  A_REMPLIR
            $case_a_remplir = key($a_remplir);   //et on definit la nouvelle case a remplir
            $nb_case_remplie++; //sans oublie de signaler que l'on vient de remplir une case de plus ;-)
         }
         else //sinon, si aucune valeur n'est possible, 
         {
            retour($nb_case_remplie-1); //on appelle la function RETOUR
         }
         //affichage($sudoku);
         $is_vide = array_filter($sudoku, "vide"); //on verifie que le sudoku n'est pas vide
      }
      //fin de la routine de remplissage
      $stop = explode(' ', microtime());
      $tps[0] = $stop[0]+$stop[1];
      $tps[1] = $start[0]+$start[1];
      $rendertime=number_format((($tps[0])-($tps[1])), '4');
      
      echo 'Sudoku de depart :'; //on passe a l'affichage :-D
      affichage($sudoku_depart); //affiche de la grille de depart
      $coup_total = $coup + $erreur_commise;
      echo 'Solution trouvee en : '.$rendertime.' secondes ('.$coup_total.' coups, dont '.$erreur_commise.' erreurs) :';
      affichage($sudoku); //et de la solution trouvee :-D
      echo '<a href="sudoku.php">Retour</a>'; //lien de retour
   }
   else
   {
      echo '<strong>Grille invalide !</strong><br />'.$valide;
   }
}
else //sinon, le formulaire
{
   echo 'Entrez une grille <strong>valide</strong> du sudoku ci-dessous : ';
   if (!empty($_GET['def'])) echo'(<a href="sudoku.php">Grille vierge</a>)'; //si l'utilisateur a demander la grille par defaut
   else echo'(<a href="sudoku.php?def=ok">Grille par defaut</a>)'; //sinon
   echo '<br /><br/ ><!--by Clems--!><form action="sudoku.php" method="post">
         <table style="border: 1px solid black; border-colapse: colaspe">';
   
   for($x=1; $x<10; $x++)
   {
      echo '<tr>';
      for($y=1; $y<10; $y++)
      {
         echo '<td style="'; //cellule
         if($x%3 == 0 && $x != 9) echo 'border-bottom: 1px solid black;'; //si c'est la droite d'un carre, on trace la bordure
         if($y%3 == 0 && $y != 9) echo 'border-right: 1px solid black;'; //si c'est le bas d'un carre, on trace la bordure
         $value = (!empty($_GET['def'])) ? $grille_defaut[$x.'|'.$y] : ''; //comment pre-remplir le formulaire
         echo '"><input name="'.$x.'|'.$y.'" size="1" maxlength="1" value="'.$value.'"/></td>'; //affichage de la valeur de la grille par defaut
      }
      echo '</tr>';
   }
   echo '</table><br />
      <input type="submit" value="go!" />
      </form>';
}
?>