/* sudoku.js   Résolution des sudokus

  (C) 2005 Jean-Paul Davalan <jpdv@wanadoo.fr>

   Usage strictement réservé au site http://perso.wanadoo.fr/jean-paul.davalan/

   Ce script ne peut être utilisé sans autorisation par une autre page que
   http://perso.wanadoo.fr/jean-paul.davalan/jeux/solitaires/sudoku/index.html

   Adresser toute demande de renseignement à : 
   Jean-Paul Davalan <jpdv@wanadoo.fr>
 */

function cse2(i, j) { return 3*Math.floor(parseInt(i)/3)+Math.floor(parseInt(j)/3); } // case
function cse(u) { return cse2(lig(u),col(u)); }
function plce2(i,j) { return 3*(parseInt(i)%3)+ parseInt(j)%3; }           // rang dans la case
function plce(u) { return plce2(lig(u),col(u)); }
function lig(u) { return Math.floor(parseInt(u)/9); }   // ligne de 0<= u <81
function col(u) { return parseInt(u)%9; }               //  colonne
function elt(i, j) { return 9*i+1*j; }

function alea(k) { return Math.floor(k*Math.random());}

var bits=new Array(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384);

var Lig = new Array();
for(var i=0; i<81; i++) Lig[i] = lig(i);

var Col = new Array();
for(var i=0; i<81; i++) Col[i] = col(i);

var Cse = new Array();
for(var i=0; i<81; i++) {
   Cse[i] = cse(i);
}
var Cse2 = new Array();
for(var i=0; i<9; i++) {
   Cse2[i] = new Array();
   for(var j=0; j<9; j++)
     Cse2[i][j] = cse2(i,j);
}
var Plce = new Array();
for(var i=0; i<81; i++) Plce[i] = plce2(Lig[i],Col[i]);

var Plce2 = new Array();
for(var i=0; i<9; i++) {
   Plce2[i] = new Array();
   for(var j=0; j<9; j++)
     Plce2[i][j] = plce2(i,j);
}

var Elt = new Array();
for(var i=0; i<9; i++) {
   Elt[i] = new Array();
   for(var j=0; j<9; j++)
     Elt[i][j] = 9*i+j;
}


function permutation(n) {
  var t = new Array();
  for(var i=0;i<n;i++)
    t[i]=i;
  for(var i=n-1; i>0; i--) {
    var a = alea(i+1), b=t[i];
    t[i]=t[a]; t[a]=b;
  }
  return t;
}

function sudoku() {
    this.nc=0;  // nbre de cases déjà remplies
    this.s=null;   // la chaîne de 81 caractères pour initialiser
                // est éventuellement vide ""
    this.tb=new Array(9);  // 9 lignes
    for(i=0;i<9;i++) {
      this.tb[i]=new Array();   // les colonnes
    }
    this.lib=new Array(27);   // 0-8 lignes, 9-17 colonnes, 18-26 cases
    for(var i=0;i<27;i++) {
      this.lib[i]=0;
    }
    this.mini=9;   // nb de valeurs possibles au minimum dans une case
    this.xmini=0;  // x, y position où le moins de possibilités
    this.ymini=0;
    this.perm=new Array();

    function init(s) {
      if(s==null) s="";
      else {
        var t;
        do {
          t=s;
          s = s.replace(/\s+/g,"");
        } while(t!=s);
      }
      this.s=s;
      for(i=0;i<9;i++) {
        for(var j=0;j<9;j++) {
          this.tb[i][j]=0;  // 0 = vide = blanc = pas de valeur
        }
      }
      // 9 lignes + 9 colonnes + 9 blocs
      for(var i=0;i<27;i++) {
        for(var j=0;j<10;j++) this.lib[i] = 0;
      }
      this.nc=0;
      for(var i=0;i<81 && i<s.length;i++) {     
        var c=this.s.charAt(i);
        if(c==null || c=="") break;
        var u=parseInt(c);
        if(u>=1 && u<=9) {
          var a=Lig[i], b = Col[i];
          this.tb[a][b]=u;
          this.nc++;
          var x = bits[u];
          this.lib[a] |=  x;                // dans la ligne
          this.lib[9+b] |= x;              //         colonne
          this.lib[18+Cse[i]] |= x;  //         case (petit carré)
        }
      }
    }
    this.init=init;

    function initlib() {  
      this.nc=0;
      for(var i=0;i<27;i++)this.lib[i] =  0;
      for(var i=0;i<81;i++) {
        var a=Lig[i], b = Col[i], u=parseInt(this.tb[a][b]);
        if(u>=1 && u<=9) {
          this.nc++;
          var x = bits[u];
          this.lib[a] |=  x;                // dans la ligne
          this.lib[9+b] |= x;              //         colonne
          this.lib[18+Cse[i]] |= x;  //         case (petit carré)
        }
      }
    }
    this.initlib=initlib;

    function copy() {
      var sd=new sudoku();
      //sud.init("");
      for(var i=0;i<9;i++)
        for(var j=0;j<9;j++) 
          sd.tb[i][j] = this.tb[i][j];
      for(var i=0;i<27;i++) {
        sd.lib[i] = this.lib[i];
      }
      sd.nc=this.nc;
      return sd;
    }
    this.copy = copy;

    // permutation de 1 2 3... 9
    function permelt() {
       var sd=new sudoku();
       var t=new permutation(9);
       
       for(var i=0;i<9;i++) {
         for(var j=0;j<9;j++) {
           u = parseInt(this.tb[i][j]);
           if(u>0) u = 1+ t[u-1];
           sd.tb[i][j]=u;
         }
       }
       sd.initlib();
       return sd;
    }
    this.permelt=permelt;

    // permutation de 1 2 3
    function permgroupes() {
      var sd=new sudoku();
      var t0=new permutation(3), t1=new permutation(3);
       for(var i=0;i<3;i++) { // groupes de lignes (horizontaux)
         for(var j=0; j<3;j++) {  // dans le groupe
           for(var k=0; k<9; k++) { // sur la ligne
              var u = t0[i];
              sd.tb[3*u+j][k]=this.tb[3*i+j][k];
           }
         }
       }
       var sd2=new sudoku();
       for(var i=0;i<3;i++) { // groupes 
         for(var j=0; j<3;j++) {  // dans le groupe
           for(var k=0; k<9; k++) { // sur la colonne
              var u = t1[i];
              sd2.tb[k][3*u+j]=sd.tb[k][3*i+j];
           }
         }
       }
       delete(sd);
       sd2.initlib();
       return sd2;
    }
    this.permgroupes=permgroupes;

    function permdsgroupe() {
       var sd=new sudoku();
       for(var i=0; i<3; i++) { // groupes de lignes
         var t=new permutation(3);
         for(var j=0; j<3;j++) {  // dans le groupe
           for(var k=0; k<9; k++) { // sur la ligne
             sd.tb[3*i+t[j]][k] = this.tb[3*i+j][k];
           }
         }
         delete(t);
       }
       var sd2=new sudoku();
       for(var i=0; i<3; i++) { // groupes de colonnes
         var t=new permutation(3);
         for(var j=0; j<3;j++) {  // dans le groupe
           for(var k=0; k<9; k++) { // sur la colonne
             sd2.tb[k][3*i+t[j]] = sd.tb[k][3*i+j];
           }
         }
         delete(t);
       }
       delete(sd);
       sd2.initlib();
       return sd2;
    }
    this.permdsgroupe=permdsgroupe;
    
    function symdiag() {
      var sd=new sudoku();
      for(var i=0;i<9;i++)
        for(var j=0;j<9;j++)
          sd.tb[i][j] = this.tb[j][i];   
      sd.initlib();
      return sd;
    }
    this.symdiag=symdiag;

    function insert(a, b, i) {
       a = parseInt(a);
       b = parseInt(b);
       var u = Cse2[a][b];
       var x = bits[i];
       if(this.tb[a][b]!=0 || i<1 || i>9 || ((this.lib[a] | this.lib[9+b] | this.lib[18+u]) & x) ) return false;
       this.tb[a][b]=i;
 
       this.lib[a] |= x;
       this.lib[9+b] |= x;
       this.lib[18+Cse2[a][b]]  |= x;
       this.nc +=1;
       return true;
    }
    this.insert=insert;

   // vérifie dans la table lib si on peut mettre la valeur x dans la case a,b
   function isfree(a, b, x) {
/*
      a = parseInt(a);
      b = parseInt(b);
      x = parseInt(x);
*/
//      var t = bits[x];
      return (  ((this.lib[a] | this.lib[9+b] | this.lib[18+Cse2[a][b]]) & bits[x]) == 0);
   }
   this.isfree=isfree;

   // nb de valeurs possibles dans la case a,b
   function nbpossibles(a,b) {
     var n=0;
     for(var i=1;i<=9;i++) {
       if(this.isfree(a,b,i)) n++;
     }
     return n;
   }
   this.nbpossibles=nbpossibles;

   function minimise() {
     this.mini=10;
     this.xmini=0;
     this.ymini=0;
     for(var i=0; i<9; i++) {
       for(var j=0; j<9; j++) {
         if(this.tb[i][j]==0) {
           var p = this.nbpossibles(i,j);
           if(p<this.mini) {
              this.mini=p;
              this.xmini=i;
              this.ymini=j;
           }
         }
       }
     }
     return this.mini;
  }
  this.minimise=minimise;

  function listepossibles(x, y) {
     var res="";
     if(this.tb[x][y]!=0) return this.tb[x][y];
     for(var i=1;i<=9;i++) {
       if(this.isfree(x,y,i)) {
         res += i+" ";
       }
     }
     return res;
  }
  this.listepossibles=listepossibles;

  function update(f) {
    for(var i=0; i<9;i++) {
      for(var j=0; j<9 ; j++) {
        var u = this.tb[i][j];
        name="a_"+i+"_"+j;
        f.names[name].value=(u>0)? u : "";
      }
    }
  }
  this.update=update;

  function chaine() {
    var res="";
    for(var i=0; i<9;i++) {
      for(var j=0; j<9;j++) {
        var c = this.tb[i][j];
        res += (c==0)? "-" : c;
      }
    }
    return res;
  }
  this.chaine=chaine;
   
  function solve(d, z) {
    var sols = null;
    var n;
    if(nsols >= maxsols) return;
    if(this.nc >= 81) {
      if(sols == null)
        sols = this.chaine();
      else 
        sols += "\n"+this.chaine();
      if(d!=null) difficult += parseInt(Math.log(d)/Math.log(2))+" ";
      nsols +=1;
    } else {
      n = this.minimise();
      if(n==0) {
        return "";
      } 
      else {
         a = this.xmini;
         b = this.ymini;
         var tu = new Array();
         var j=0;
         for(i=1;i<=9;i++) {
           if(this.isfree(a,b,i)==true) {
             tu[j]=i;
             j++
            }
         }
         // ordre différent aléatoire (permutation de 0..n-1)
         for(var i=j-1;z=true && i>=0;i--) {
           var j=Math.floor((i+1)*Math.random());
           var k= tu[j];
           tu[j]=tu[i];
           tu[i]=k
         }
         for(var j=0;j<n;j++) {
           var i = tu[j];
             var su = this.copy();
             su.nc=this.nc
             su.insert(a,b,i);
             var so = su.solve(d*n, z);  
             if(so!=null) {
                if(sols==null) sols = so;
                else sols += so;
             }
         }
      }
    }
    return sols;
  }
  this.solve=solve;
  
  function affiche() {
    for(var i=0; i<9; i++) {
      for(var j=0; j<9; j++) {
        var c = this.tb[i][j];
        c = (0<c && c<=9) ? c : "";
        var name="a_"+i+"_"+j;
        var elt = document.frm[name].value=c;
        elt.value=c;
      }
    }
  }
  this.affiche=affiche;
}
   
function mktable(idt,frm) {
  var color="#0022aa";
  var s = '<style type="text/css">' +
  ' table {border:none;border-collapse: collapse;}'+
  ' table.g{margin:0;spacing:0;padding:0;}'+
  ' table.p{width: 100%;}'+
  ' td.g {border-width:1px;border-style: solid;border-color:'+color+'}'+
  ' td.p {width:20px;height:20px;border-width:0.5px;border-style: solid; border-color:'+color+';text-align:center;vertical-align:middle;}'+
  ' input.t {width:35px;height:35px;text-align:center;vertical-align: middle;font-family: arial, verdana,sans-serif;font-size:28;text-style:bolder;border:none;margin:0;padding:3 2 3 2}' +
  '</style>'
   
  s += '<form name="'+frm+'" action="">' +
  '<center><table class="g">';          // grande table

  for(var i=0; i<3; i++) {     // lignes de la grande table
    s += '<tr>';
    for(var j=0;j<3;j++) {     // colonnes de la grde table
      s += '<td class="g"><table class="p" style="border-collapse: collapse">';           // une petite table
      for(var k=0; k<3; k++) { 
        s += '<tr>'                 // lignes de la petite table
        for(var l=0; l<3; l++) {    // colonnes
           var tlig = i*3+k,  tcol = j*3+l;
           var name = 'a_'+tlig+'_'+tcol;
           var id='b_'+tlig+'_'+tcol;
           s+='<td class="p"><input class="t" id="'+id+'" name="'+name+'" onmouseover="etudier('+tlig+','+tcol+');" onmouseout="vide();" ondblclick="s2s(lire());" onkeypress="s2s(lire());" type="text" value="" /></td>';
        }
        s += '</tr>';
      }
      s += '</table></td>'
    }
    s += '</tr>';
  }

  s += '</table><br /><br />' +
       '<input type="button" onclick="libres();" value="Aide">&nbsp;&nbsp;&nbsp;'+
       '<input class="tt1" type="text" name="el" ondblclick="s2s(\"document.frm.el.value\");" value="">'+
       '<br /><br /><input type="button" onclick="savecurt();" value="Mémorise">&nbsp;&nbsp;&nbsp;'+
       '<input type="button" onclick="suivt(-1);" value="<-">'+
       '<input type="button" onclick="suivt(1);" value="->">'+
       '&nbsp;&nbsp;&nbsp;&nbsp;<input type="button" onclick="resoud();" value="Solution">'+
       '<input type="button" onclick="clrtab();" value="Clr">'+
       '<input type="button" onclick="clrall();" value="CClr">'+
//       '<input type="button" onclick="grid();" value="G">'+
       '<br /><br /><input type="button" onclick="_permelt();" value="A">'+
       '<input type="button" onclick="_permdsgroupe();" value="B">'+
       '<input type="button" onclick="_permgroupes();" value="C">'+
       '<input type="button" onclick="_symdiag();" value="D">'+
       '<input type="button" onclick="_permglobal();" value="E">'+
       '</center></form>';
 // document.getElementById(idt).innerHTML=s;
  document.write(s);
}

function clrtab() {
   for(var i=0; i<9; i++) {
     for (var j=0 ; j<9; j++) {
        document.frm["a_"+i+"_"+j].value="";
        document.frm["a_"+i+"_"+j].readOnly=false;
     }
   }
}

function lire() {
   var s="";
   for(var i=0;i<9;i++) {
     for(var j=0; j<9;j++) {
       name="a_"+i+"_"+j;
       var d, c=document.frm[name].value;
       do { 
         d=c; 
         c=c.replace(/[^1-9]/g,"");
       } while(d!=c);
       document.frm[name].value=c;
       var u;
       if(c!=null && c!="") u = parseInt(c);
       else u="-";
       s += u;
     }
  }
  return s;
}

function vide() {
  document.frm.el.value="";
}

function etudier(a,b) {
  if(sud != null)
    document.frm.el.value = sud.listepossibles(a,b);
  else
    document.frm.el.value = "";
}

function resoud() {
   maxsols=1;
   nsols=0;
   difficult="";
   var sols=null;
   var s=lire();
   s2s(s);
   sols = sud.solve(1, true);
   //alert(difficult);
   difficult = difficult.split(/\s+/g)[0];
   if(difficult<1) difficult=1;
   document.frm.el.value="Niveau de difficulté : "+Math.floor((1+Math.log(difficult)/Math.log(2)));
   if(sols != null && sols!="") {
     s2s(sols);
   }
}

var sud=null;
var nsols=0;
var maxsols=1;
var difficult="";

var Exo = new Array(
"62--75----9----5------9--1---96--184---------218--79---5--3------4----2----84--56",
"4----5--1-25-4-78-69----3--3----8----4-1-26-77-19------7--9-1--9862---5---3-64--8",
"1--4--7-94--7------8-----6-21------63----5-7---817-3----59-2-3-87--3-5----2-8----",
"---4---8----3--95-5--1-6----8---9---69---1--5---6-34---5---7------8---3--76----4-",      // 3
"",
"",      // 5
"",
"",
"",
"",
"",      // 10
"---569-82---------2-3-7-5--4-1-536-----9---4-------7---6-7---343----4-----42-58--",
"",
"",
"",
"",
"",
"",
"",
"",
"",       // 20
"17-------3-----246-65---------2--938---8-1-------76------42----9-3-------2---8591",
"174682359398517246265943817617254938532891764849376125751429683983165472426738591",
"",
"",
"",      //15
"",
"",
"",
"",
"",      // 20
"",
"",
""
);

function s2s(s) {
  if(sud!= null) {
    delete(sud);
  }
  sud = new sudoku();
  sud.init(s);
  lastch=s;
  sud.affiche();
}

function bloque() {
  var r;
  for(var i=0; i<9; i++) {
    for(var j=0; j<9; j++) {
      if(sud.tb[i][j]==0) r=false;
      else r= true;
      document.frm["a_"+i+"_"+j].readOnly=r;
    }
  }
}

function debloque() {
  var r;
  for(var i=0; i<9; i++) {
    for(var j=0; j<9; j++) {
      document.frm["a_"+i+"_"+j].readOnly=false;
    }
  }
}
function nouveau(x) {
  clrall();
  tohist(Exo[x]);
  s2s(Exo[x]);
  bloque();
}

function libres() {
  var u, s=document.frm.el.value;
  var s1=lire();
   if(sud != null) delete(sud);
   sud = new sudoku();
   sud.init(s1);
   sud.affiche();
   tohist(sud.chaine());
   sud.minimise();
   var lp = sud.listepossibles(sud.xmini,sud.ymini);
   document.frm.el.value="("+(1+sud.xmini)+", "+(1+sud.ymini)+") : "+lp;
   if(sud.mini==1) {
      document.frm["a_"+sud.xmini+"_"+sud.ymini].value=lp;
      sud.insert(sud.xmini,sud.ymini,lp);
   }
}

var histtab=new Array(), histref=new Array(), current=0, last=0;

function tohist(s) {
  if(histref[s]==null) {
    histref[s]=last;
    histtab[last]=s;
    current=last;
    last +=1;
  } else {
    current = histref[s];
  }
}
   
function savecurt() {
  s = sud.chaine();
  tohist(s);
}

function suivt(x) {
  var n = current+x;
  if(n >= last) n = last-1;
  if(n<0) n=0; 
  current=n;
  var s = histtab[n];
  s2s(s);
}

function clrhist() {
  delete(histtab);
  delete(histref);
  histtab=new Array();
  histref=new Array();
  current=0;
  last=0;
}

function clrall() {
   clrtab();
   clrhist();
   delete(sud);
   sud=null;
}

function trans() {
  var u, v;
  v=document.frm.el.value;
  do {
    u=v;
    v = v.replace(/[\.\*]/g,"0");
  } while(u!=v);
  do {
    u=v;
    v = v.replace(/[^0-9]/g,"");
  } while(u!=v);
  s2s(v);
  document.frm.el.value="";
}

var pretty=false;

var zcode="0";

function prettyprint() {
 if(pretty==true) {
    document.getElementById("pretty").innerHTML="";
    pretty=false;
  } else {
  if(sud==null) return
  pretty=true;
  var li = "+-------+-------+-------+";
  var s = "<center><code>";
  for(var i=0; i<9; i++) { // lignes
    if(i%3==0) s+= li+"<br />";
    for(j=0;j<9;j++) { // colonnes
      if(j%3==0) s += "| "; // séparation début
      var u = sud.tb[i][j];
      u = (u==0) ? zcode: u;
      s += u+" ";
    }
    s += "|<br />"; // fin de ligne
  }
  s += li+"</code></center>";
  document.getElementById("pretty").innerHTML=s;
  }
}
 
var brut=false;
function formatbrut() {
 if(brut==true) {
    document.getElementById("brut").innerHTML="";
    brut=false;
  } else {
  if(sud==null) return
  brut=true;
  var s = "<center><br /><code>";
  for(var i=0; i<9; i++) { // lignes
    for(j=0;j<9;j++) { // colonnes
      var u = sud.tb[i][j];
      u = (u==0) ? "-": u;
      s += u+"";
    }
  }
  s += "</code><br /></center>";
  document.getElementById("brut").innerHTML=s;
  }
}

var latex=false;

function formatLatex() {
 if(latex==true) {
    document.getElementById("tex").innerHTML="";
    latex=false;
  } else {
 if(sud==null) return
  latex=true;
  var s = '<pre style="{background:#ffffff;}">';
  s += '\\documentclass[11pt,a4]{article}\n'+
       '\\usepackage{epic,eepic}\n'+
//       '\\usepackage{aeguill} % au lieu de [T1]{fontenc}\n'+
//       '% expliquer pourquoi ps2pdf donne un meilleur pdf\n'+
//       '%dvips -Pcmz essai.dvi -o\n'+
       '\\usepackage{times}\n'+
//       '\\usepackage[latin1]{inputenc}\n'+
       '\\usepackage[dvips]{graphicx}\n'+
//       '\%\\usepackage[pdftex]{graphicx}\n'+
       '\\begin{document}\n';

  s += '\\setlength{\\unitlength}{1mm}\n'+
       '\\begin{picture}(63,63)(-1,-1)\n'+
       '\\thicklines\n'+
       '\\put(0,0){\\grid(63,63)(21,21)}\n'+
       '\\put(0.1,0.1){\\grid(63,63)(21,21)}\n'+
       '\\thinlines\n'+
       '\\put(0,0){\\grid(63,63)(7,7)}\n';
  for(var i=0; i<9; i++) { // lignes
    var v = 8-i, h=7*v+2.7;
    var k=false;
    for(j=0;j<9;j++) { // colonnes
      var w = 2.7+j*7;
      var u = sud.tb[i][j];
      if(0<u && u<=9){ 
        k=true; 
        s += '\\put('+w+','+h+'){'+u+'}';
      }
    }
    if(k) s+='\n';
  }
  s += '\\end{picture}\n';
  s += '\\end{document}';
  s += "</pre><br /></center>";
  document.getElementById("tex").innerHTML=s;
  }
}

function _permelt() {
  if(sud==null) return;
  var sd = sud.permelt();
  delete(sud);
  sud = sd;
  sud.affiche();
}
function _permgroupes() {
  if(sud==null) return;
  var sd = sud.permgroupes();
  delete(sud);
  sud = sd;
  sud.affiche();
}

function _permdsgroupe() {
  if(sud==null) return;
  var sd = sud.permdsgroupe();
  delete(sud);
  sud = sd;
  sud.affiche();
}

function _symdiag() {
  if(sud==null) return;
  var sd = sud.symdiag();
  delete(sud);
  sud = sd;
  sud.affiche();
}


function _permglobal() {
  if(sud==null) return;
  var sd1 = sud.permelt();
  delete(sud);
  var sd2 = sd1.permgroupes();
  delete(sd1);
  var sd3 = sd2.permdsgroupe();
  delete(sd2);
  if(Math.random()<0.5) {
    sud = sd3.symdiag();
    delete(sd3);
  } else {
    sud=sd3;
  }
  sud.affiche();
}

var sgrid = "";
var ssaved = "";

function grid(t) {
  var sd = new sudoku();
  var places=81;
  var s2;
  var s;
  if(t==true || ssaved==null || ssaved.length!=81) {
    maxsols=1;
    nsols=0;
    sd.init("");
    s = sd.solve(1, true);
    ssaved = s;
  } else {
    s= ssaved;
  }
  var s1;
  var u = 1;
  maxsols = 3;
  nsols=0;
  var t = new permutation(81);
  for(var i = 0; i< 81 && places > 17; i++) {
    var n = parseInt(t[i]);

    s1 = s.slice(0,n)+"-"+s.slice(n+1);
    sd.init(s1);
    nsols=0;
    var a = sd.solve(1, false);
    
    if(nsols==1) {
      u = parseInt(a.split(/\,/g)[1]);
      s = s1;
      places--;
    } 
    sgrid = s+" , "+u;
    document.frm.el.value=places+" "+(80-i);
    s2="<br /><center><code>" + s + "</code><br /></center>";
    document.getElementById("gene").innerHTML=s2;
  }
  
  if(sud!=null) delete(sud);
  sud=new sudoku();
  sud.init(s);
  s2="<br /><center><code>" + s + "</code><br /></center>";
  document.getElementById("gene").innerHTML = s2;
  sud.affiche();
}

function grid2(t) {
  var sd = new sudoku();
  var places=81, nb=81, d;
  var s2;
  var s;
  if(t==true || ssaved==null || ssaved.length!=81) {
    maxsols=1;
    nsols=0;
    sd.init("");
    s = sd.solve(1, true);
    ssaved = s;
  } else {
    s= ssaved;
  }
  var s1;
  maxsols = 3;
  nsols=0;
  var t = new permutation(41);
  for(var i = 0; i< 41; i++) {
    var n = parseInt(t[i]);
    s1 = s.slice(0,n)+"-"+s.slice(n+1);
    d = 1;
    if(n!=40) { 
      var s1b=s1;
      s1 = s1b.slice(0,80-n)+"-"+s1b.slice(81-n);
      d++;
    }
    sd.init(s1);
    nsols=0;
    var a = sd.solve(1, false);
    nb -=d;
    if(nsols==1) {
      u = parseInt(a.split(/\,/g)[1]);
      s = s1;
      places -=d;
    }
    sgrid = s;
    document.frm.el.value=places+" "+nb;
    s2="<br /><center><code>" + s + "</code><br /></center>";
    document.getElementById("gene").innerHTML=s2;
  }
  if(sud!=null) delete(sud);
  sud=new sudoku();
  sud.init(s);
  s2="<br /><center><code>" + s + "</code><br /></center>";
  document.getElementById("gene").innerHTML = s2;
  sud.affiche();
}

function rot(n) {
  var x=Lig[n], y=Col[n];
  return elt(y,8-x);
}
function symc(n) {
  var x=Lig[n], y=Col[n];
  return elt(8-x,8-y);
}
var trot=new Array(0,1,2,3,4,5,6,7,10,11,12,13,14,15,20,21,22,23,30,31,40);

function grid4(t) {
  var sd = new sudoku();
  var places=81, nb=81, d, s2, s;
  if(t==true || ssaved==null || ssaved.length!=81) {
    maxsols=1;
    nsols=0;
    sd.init("");
    s = sd.solve(1, true);
    ssaved = s;
  } else { s= ssaved; }
  sgrid=s;
  var s1;
  maxsols = 3;
  nsols=0;
  var t = new permutation(21);
  for(var i = 0; i< 21; i++) {
    var n = trot[t[i]], m=rot(n);
    s1 = s.slice(0,n)+"-"+s.slice(n+1);
    d = 1;
    if(n!=40) { 
      var s1b=s1, s1c, s1d;
      s1c = s1b.slice(0,symc(n))+"-"+s1b.slice(1+symc(n));
      s1d = s1c.slice(0,m)+"-"+s1c.slice(m+1);
      s1 = s1d.slice(0,symc(m))+"-"+s1d.slice(symc(m)+1);
      d +=3;
    }
    sd.init(s1);
    nsols=0;
    var a = sd.solve(1, false);
    nb -= d;
    if(nsols==1) {
      s = s1;
      places -=d;
    }
    sgrid = s;
    document.frm.el.value=places+" "+nb;
    s2="<br /><center><code>" + s + "</code><br /></center>";
    document.getElementById("gene").innerHTML=s2;
  }
  if(sud!=null) delete(sud);
  sud=new sudoku();
  sud.init(sgrid);
  s2="<br /><center><code>" + s + "</code><br /></center>";
  document.getElementById("gene").innerHTML = s2;
  sud.affiche();
}
function symaxe(n, axe) {
   var x=Lig[n], y= Col[n];
   if(axe=="horizontal") {
      x=8-x;
   } else if(axe=="vertical") {
     y=8-y;
   }
   return 9*x+y;
}
var tsym2=new Array(40,4,13,22,31,36,37,38,39,0,1,2,3,9,10,11,12,18,19,20,21,27,28,29,30);
function gridsym2(t) {
  var sd = new sudoku();
  var places=81, nb=81, s2, s;
  if(t==true || ssaved==null || ssaved.length!=81) {
    maxsols=1;
    nsols=0;
    sd.init("");
    s = sd.solve(1, true);
    ssaved = s;
  } else { s= ssaved; }
  sgrid=s;
  var s1, u = 1, d= 0;
  maxsols = 3;
  nsols=0;
  var t = new permutation(25);
  for(var i = 0; i< 25; i++) {
    var n = tsym2[t[i]], m0=symaxe(n,"horizontal"), m1=symaxe(n,"vertical"), m2=symaxe(m0,"vertical");
    s1 = s.slice(0,n)+"-"+s.slice(n+1);
    d = 1;
    if(n!=40) {
      var s1b=s1, s1c, s1d;
      if(m0 != n) {
         s1b=s1; s1 = s1b.slice(0,m0)+"-"+s1b.slice(1+m0); d++;
      }
      if(m1!=n) {
         s1b=s1; s1 = s1b.slice(0,m1)+"-"+s1b.slice(1+m1); d++
      }
      if(m0 != n && m1!=n) {
         s1b=s1; s1 = s1b.slice(0,m2)+"-"+s1b.slice(1+m2); d++
      }
    }
    sd.init(s1);
    nsols=0;
    var a = sd.solve(1, false);
    if(nsols==1) {
      s = s1; places -=d;
    }
    nb -=d;
    sgrid = s;
    document.frm.el.value=places+" "+nb;
    s2="<br /><center><code>" + s + "</code><br /></center>";
    document.getElementById("gene").innerHTML=s2;
  }
  if(sud!=null) delete(sud);
  sud=new sudoku();
  sud.init(sgrid);
  s2="<br /><center><code>" + s + "</code><br /></center>";
  document.getElementById("gene").innerHTML = s2;
  sud.affiche();
}
function symdiag(n,diag) {
   var u,v, x = Lig[n], y= Col[n];
   if(diag==1) {
      u = y; 
      v = x;
   } else if(diag==2) {
      u = 8-y;
      v = 8-x;
   }
   return 9*u+v;
}
var tdiag= new Array(0,1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,20,21,22,23,24,30,31,32,40);
function griddiag(t) {
  var sd = new sudoku();
  var places=81, nb=81, s2, s;
  if(t==true || ssaved==null || ssaved.length!=81) {
    maxsols=1;
    nsols=0;
    sd.init("");
    s = sd.solve(1, true);
    ssaved = s;
  } else { s= ssaved; }
  sgrid=s;
  var s1, u = 1, d= 0;
  maxsols = 3;
  nsols=0;
  var t = new permutation(25);
  for(var i = 0; i< 25; i++) {
    var n = tdiag[t[i]], m0=symdiag(n,1), m1=symdiag(n,2), m2=symc(n);    
    //if(i<5) alert(n+" "+m0+" "+m1+" "+m2);
    s1 = s.slice(0,n)+"-"+s.slice(n+1);
    d = 1;
    if(n!=40) {
      var s1b;
      if(m0 != n) {
         s1b=s1; s1 = s1b.slice(0,m0)+"-"+s1b.slice(1+m0); d++;
      }
      if(m1!=n) {
         s1b=s1; s1 = s1b.slice(0,m1)+"-"+s1b.slice(1+m1); d++
      }
      if(m2 != m0 && m2!=m1) {
         s1b=s1; s1 = s1b.slice(0,m2)+"-"+s1b.slice(1+m2); d++
      }
    }
    sd.init(s1);
    nsols=0;
    var a = sd.solve(1, false);
    if(nsols==1) {
      s = s1; places -=d;
    }
    nb -=d;
    sgrid = s;
    document.frm.el.value=places+" "+nb;
    s2="<br /><center><code>" + s + "</code><br /></center>";
    document.getElementById("gene").innerHTML=s2;
  }
  if(sud!=null) delete(sud);
  sud=new sudoku();
  sud.init(sgrid);
  s2="<br /><center><code>" + s + "</code><br /></center>";
  document.getElementById("gene").innerHTML = s2;
  sud.affiche();
}

function  resoudgrid() {
   s2s(sgrid);
   resoud();
   var s = "";
   for(var i=0; i<9; i++) { // lignes
     for(j=0;j<9;j++) { // colonnes
       var u = sud.tb[i][j];
       u = (u==0) ? "-": u;
       s += u+"";
     }
   }

   s1 = "<br /><center><code>" + sgrid.split(/\,/g)[0] + "</code><br />" +
        "<code>" + s + "</code><br />"
   document.getElementById("gene").innerHTML = s1;
}