/* rb2.js rb2b.js
  génère des arcs-en-ciel et aide à les résoudre
  Copyright (C) 2006 Jean-Paul Davalan
*/
var alpha="abcdefghijklmnopqrstuvwxyz1234567890".split(/\B/g);
var alpha2="123456789abcdefghijklmnopqrstuvwxyz".split(/\B/g);
var Alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(/\B/g);
function graph() {
this.n=0; // nombre de sommets  0 1 2 3 ... n-1
this.matrice=new Array(); // avec colorations
this.mat2=new Array();
this.history=new Array();  // this.history[i][j] date à laquelle this.mat2[i][j] devient null
this.date=0;               // date actuelle
this.res=new Array(); // couleurs uniques dans mat2 (à partir des cases cliquées)
this.dateres=new Array(); // date à laquelle this.res[i] passe de false à true
this.compte=new Array(); // compte des couleurs dans mat2
this.ham=new Array();
this.col=new Array();
this.lig = new Array();
this.k=0;
this.p=0;
this.sp=false;
function init(n, p) {
this.n=n;
this.k=n;
this.p = p;
var cl=iperm(this.n), pos=iperm(this.n);
pos[this.n]=pos[0];
for(var i=0; i<this.n; i++) {
this.res[i]=false;          // non
this.dateres[i]=-1;     // date de résolution
this.compte[i]=0;
}
for(var i=0; i<this.n; i++) {
this.matrice[i] = new Array();
this.mat2[i] = new Array();
this.history[i] = new Array();
this.ham[i] = new Array();
this.col[i] = new Array();
this.lig[i] = new Array();
}
for(var i=0; i<this.n; i++) {
for(var j=0; j<this.n; j++) {
this.history[i][j]=0;
}
}
for(i=0; i<this.n; i++) {
this.matrice[pos[i]][pos[i+1]]=cl[i]
this.matrice[pos[i+1]][pos[i]]=cl[i]
this.ham[pos[i]][pos[i+1]]=cl[i]
this.lig[pos[i]][cl[i]]=1
this.col[pos[i]][cl[i]]=1
this.lig[pos[i+1]][cl[i]]=1
this.col[pos[i+1]][cl[i]]=1
}
var tab = iperm(this.n*this.n)
for(i=0; i<this.n*this.n; i++) {
var u = tab[i]
var x = xcoord(this.n, u);
var y = ycoord(this.n, u);
if(x==y || this.matrice[x][y]!=null|| this.matrice[y][x]!=null || hasard(this.p)==false) continue;
var c = iperm(this.n);
for(var j=0; j<this.n; j++) {
if(this.lig[x][c[j]]== null && this.col[y][c[j]]==null) {
this.matrice[x][y]=c[j]
this.matrice[y][x]=c[j]
this.lig[x][c[j]]=1
this.col[y][c[j]]=1;
this.col[x][c[j]]=1
this.lig[y][c[j]]=1;
break;
}
}
delete(c)
}
for(var i=0; i<this.n; i++) {
for(var j=0; j<this.n; j++) {
this.mat2[i][j] = this.matrice[i][j]
}
}
}
this.init = init;
function affiche() {
var s = ""
for(var i=0; i< this.n; i++) {
for(var j=0; j< this.n; j++) {
if(this.matrice[i][j]==null) s += " - "
else s += " "+alpha[this.matrice[i][j]]+" "
}
s += "\n"
}
return s
}
this.affiche = affiche
function tolatex(z, nu) {
var dim=22, cote = this.n*dim, dim2=8, dim4=4;
//var matrix = (z==0)? this.matrice : this.ham
var matrix = this.matrice
var grid =
"\\begin\{picture\}("+ (cote+dim+dim2) + ","+ (cote +dim+dim2)+")(-1,-1)\n" +
"\\Quadri\n"+
"\{\\Large \n"
for(var i=0; i<this.n; i++) {
var u = Alpha[i];
var a = (dim2+dim+dim*i)
grid += "\\put(" + a + "," + (cote+dim2) + ")\{"+ u +"\}"
}
for(var i=0; i<this.n; i++) {
var i2=this.n-i-1
var v = Alpha[i2];
grid += "\\put("+ 0 +","+ (dim*i+dim2) +"){"+ v +"}"
for(var j=0; j<this.n; j++) {
var w;
if(matrix[i2][j] != null) {
if(nu) w = alpha2[matrix[i2][j]]
else w = alpha[matrix[i2][j]]
grid += "\\put("+ (dim+dim2+dim*j) +","+ (dim2+dim*i) +"){"+ w +"}"
if(z==1 && this.ham[i2][j] != null) grid += "\\put("+(dim+dim2+dim4-1+dim*j) +","+ (dim2+dim4-1+dim*i) +"){\\circle{"+(dim-3)+"}}"
}
}
}
grid += "\}\n"
grid += "\\end{picture}\n";
return grid;
}
this.tolatex=tolatex;
function totexte() {
var niv = [0.05,0.20,0.40,0.65,1];
for(var niveau=0; niveau<5; niveau++) {
if(niv[niveau]==this.p) break;
}
var s="#\n"
s += "dim    : "+ this.n +"\n"       // dimension
s += "proba  : "+this.p +" "+(niveau+1)+"\n"       // proba de remplissage
s += "grille : "
for(var i=0; i<this.n;i++) {
for(var j=0; j<this.n; j++) {
s +=(this.matrice[i][j]!=null)? alpha[this.matrice[i][j]] : "-"
}
}
s += "\n"
s += "cycle  : "
for(var i=0; i<this.n;i++) {
for(var j=0; j<this.n; j++) {
s +=(this.ham[i][j]!=null)? alpha[this.ham[i][j]] : "-"
}
}
s += "\n"
return s;
}
this.totexte=totexte;
function fromtexte(s) {
var tab = s.split(/\n+/g);
//alert(tab)
var n, p, mat, h;
for(i=0; i<tab.length; i++) {
tab[i].replace(/\s+$/,"");
tab[i].replace(/^\s+/,"");
var t = tab[i].split(/\s*\:\s*/g);
if(t[0]!=null) {
t[0].replace(/\s+$/,"");
t[0].replace(/^\s+/,"");
}
if(t[1]!=null) {
t[1].replace(/\s+$/,"");
t[1].replace(/^\s+/,"");
}
if(t[0]=="dim") {
n=parseInt(t[1])
} else if(t[0]=="proba") {
if(t[1]!= null) {
var ut = t[1].split(/\s+/g)
p=parseFloat(ut[0]);
} else {
p=0.2
}
} else if(t[0]=="grille") {
//alert(t)
mat = t[1]
//alert(mat)
} else if(t[0]=="cycle") {
h = t[1]
//alert(h)
}
}
this.n=n;
this.k=n;
this.p = p;
for(var i=0; i<this.n; i++) {
this.res[i]=false;          // non
this.dateres[i]=-1;     // date de résolution
this.compte[i]=0;
}
for(var i=0; i<this.n; i++) {
this.matrice[i] = new Array();
this.mat2[i] = new Array();
this.history[i] = new Array();
this.ham[i] = new Array();
this.col[i] = new Array();
this.lig[i] = new Array();
}
for(var i=0; i<this.n; i++) {
for(var j=0; j<this.n; j++) {
this.history[i][j]=0;
}
}
for(var i=0; i<mat.length; i++) {
var c = mat.charAt(i);
if(c=="-") this.matrice[Math.floor(i/n)][i%n]=null
else {
if(this.matrice[Math.floor(i/this.n)] == null) this.matrice[Math.floor(i/this.n)]=[]
this.matrice[Math.floor(i/this.n)][i%this.n] = mat.charCodeAt(i)-"a".charCodeAt(0)
}
if(i<h.length) {
var d = h.charAt(i);
if(this.ham[Math.floor(i/n)]==null) this.ham[Math.floor(i/n)] = []
if(d=="-") this.ham[Math.floor(i/n)][i%n]=null
else
this.ham[Math.floor(i/n)][i%n] = h.charCodeAt(i)-"a".charCodeAt(0)
}
}
for(var i=0; i<n; i++) {
for(var j=0; j<n; j++) {
this.mat2[i][j]=this.matrice[i][j];
}
}
//reinit()
}
this.fromtexte=fromtexte;
function togrid() {
var niv = [0.05,0.20,0.40,0.65,1];
for(var niveau=0; niveau<5; niveau++) {
if(niv[niveau]==this.p) break;
}
var s="#\n"
s += "dim    : "+ this.n +"\n"       // dimension
s += "niveau : "+(niveau+1)+ "   (proba "+this.p +")\n"       // proba de remplissage
var s0 = "", s1="-"
for(var i=0; i<this.n; i++) {
s0 += Alpha[i]+" "
s1 += "--"
}
s +="           "+s0+ "                    "+s0+"\n"
s +="         ." +s1+ "                  ." +s1+"\n"
for(var i=0; i<this.n;i++) {
s +="       "+Alpha[i]+" | "
for(var j=0; j<this.n; j++) {
s +=(this.matrice[i][j]!=null)? alpha[this.matrice[i][j]] : "."
s += " "
}
s +="                "+Alpha[i]+" | "
for(var j=0; j<this.n; j++) {
s +=(this.ham[i][j]!=null)? alpha[this.ham[i][j]] : "."
s += " "
}
s += "\n"
}
s += "\n"
return s;
}
this.togrid=togrid;
function totable() {
var s = "<table border=0><tr><td></td>"
for(var i=0; i< this.n; i++) {
s += "<td align=center valign=middle>"+Alpha[i]+"</td>"
}
s += "</tr>"
for(var i=0; i< this.n; i++) {
s += "<tr><td align=center valign=middle>"+Alpha[i]+"&nbsp;</td>"
for(var j=0; j< this.n; j++) {
s+="<td valign=center align=center>"+
"<div class=\"box\" id=\"t"+i+"_"+j+"\" "+
"onclick=\"calc("+i+","+j+");\">"
if(this.matrice[i][j]==null) s += " "
else s += alpha[this.matrice[i][j]]
s += "</div></td>"
}
s += "</tr>"
}
s += "</table><br />"
//alert(s)
document.getElementById("Gr").innerHTML=s;
for(var i=0; i< this.n; i++) {
for(var j=0; j< this.n; j++) {
var u = "t"+i+"_"+j
if(this.matrice[i][j]==null) {
document.getElementById(u).style.cursor="text";
} else {
document.getElementById(u).style.cursor="pointer";
}
}
}
}
this.totable = totable;
}
function hasard(p) { return (Math.random()<p);}
function alea(i) { return Math.floor((i+1)*Math.random());}
function xcoord(n, a) { return Math.floor(a/n);}
function ycoord(n, a) { return a%n; }
function ident(t, n) { for(i=0; i<n; i++) t[i] = i; }
function permute(t, n) {
for(i=n-1; i>0; i--) {
u = alea(i);
if(u != i) {
c = t[i]; t[i]=t[u]; t[u]=c;
}
}
}
function iperm(n) {
var t = new Array();
ident(t, n);
permute(t, n)
return t;
}
var g = new graph();
function cherche(k) {
document.getElementById("Commt").innerHTML="<br /><br /><br /><br />"
var niveau=0;
for(i=0; i<5; i++) {
if(document.fr.rd[i].checked) niveau=i
}
if(g != null) {
delete(g);
g = new graph();
}
var n = k+parseInt(document.fr.n.value);
if(n<3) n=3
else if(n>26) n=26;
document.fr.n.value = n
var tniv=[0.05,0.20,0.40,0.65,1];
g.init(n, tniv[niveau]);
g.totable();
}
function click(i, j) {
if(g.mat2[i][j]!=null) {
//      if(g.res[g.mat2[i][j]]==false) {
g.res[g.mat2[i][j]]=true;
g.dateres[g.mat2[i][j]]=g.date;
//      }
} else {
return;
}
// efface la colonne sauf en i,j
for(var r=0; r<g.n; r++) {
if(r!=j) {
if(g.mat2[i][r]!=null) {
var u = "t"+i+'_'+r
document.getElementById(u).innerHTML=''
document.getElementById(u).style.cursor='text'
g.mat2[i][r]=null
g.history[i][r]=g.date
}
}
}
// efface la ligne sauf en i,j
for(var r=0; r<g.n; r++) {
if(r!=i) {
if(g.mat2[r][j]!=null) {
var u = "t"+r+'_'+j
document.getElementById(u).innerHTML=''
document.getElementById(u).style.cursor='text'
g.mat2[r][j]=null
g.history[r][j]=g.date
}
}
}
// efface la couleur g.matrice[i][j], partout sauf en i,j
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
if((r!=i || s!=j)&& g.mat2[r][s] != null && g.matrice[r][s]==g.matrice[i][j]) {
var u = "t"+r+'_'+s
document.getElementById(u).innerHTML=''
document.getElementById(u).style.cursor='text'
g.mat2[r][s]=null
g.history[r][s]=g.date
}
}
}
}
function unique() {
// compte[i] = nb cases de la couleur i
//var compte = new Array();
for(var i=0; i<g.n; i++) {
g.compte[i]==0;
}
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
if(g.matrice[r][s]!=null)
g.compte[g.matrice[r][s]]++
}
}
// si nb cases couleur i == 1 et non traité au préalable
// effacer ligne et colonne sauf case r,s
for(var i=0; i<g.n; i++) {
if(g.compte[i]==1 && g.res[i]==false) {
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
if(g.mat2[r][s]==i) {
click(r, s)
return true;
}
}
}
}
}
return false
}
// cherche ligne ou colonne avec 1 seul élément
function collig() {
// tableaux de comptage
var ligs = [], cols=[];
for(var r=0; r<g.n; r++) {
ligs[r]=0;
cols[r]=0;
}
// compte des élémts dans la ligne (dans la colonne)
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
if(g.mat2[r][s]!=null) {
ligs[r]++
cols[s]++;
}
}
}
for(var r=0; r<g.n; r++) {
if(ligs[r]==1) {    // un seul dans la ligne
for(var s=0; s<g.n; s++) { // le trouver
if(g.mat2[r][s]!= null) {
//var a = g.mat2[r][s];
if(g.res[g.mat2[r][s]]==false) { // ne pas refaire les mêmes indéfiniment
click(r, s)
return true;
}
}
}
}
}
for(var r=0; r<g.n; r++) {
if(cols[r]==1) {
for(var s=0; s<g.n; s++) {
if(g.mat2[s][r]!= null) {
//var a = g.mat2[s][r];
if(g.res[g.mat2[s][r]]==false) {
click(s, r)
return true;
}
}
}
}
}
return false;
}
function calc(i, j) {
document.getElementById("Commt").innerHTML="<br /><br /><br /><br />"
//alert(i+", "+j)
if(g.mat2[i][j]==null) return
g.date++
click(i, j);
if(document.fr.sp.checked) {
while(collig() || unique()) ;
}
var str="<br /><br /><br />";
var tf = testefin();
if(tf) {
str = "La recherche est terminée<br />";
if(testecomplet()) {
str += "Toutes les couleurs apparaissent<br />";
if(testecycle()) {
str += "La réponse correspond à un seul cycle,<br />"+
"il s'agit donc bien d'un cycle hamiltonien multicoloré";
} else {
str += "Ce n'est pas un cycle hamiltonien<br />";
}
}  else {
str += "Certaines couleurs manquent<br />"+
"Ce n'est pas un cycle hamiltonien multicoloré<br />";
}
}
str +="<br />"
document.getElementById("Commt").innerHTML=str
}
function back() {
document.getElementById("Commt").innerHTML="<br /><br /><br /><br />"
if(g.date==0) return
for(var i=0; i<g.n; i++) {
for(var j=0; j<g.n; j++) {
if(g.history[i][j]==g.date && g.matrice[i][j]!=null && g.mat2[i][j]==null) {
g.history[i][j]=0;
g.mat2[i][j]=g.matrice[i][j]
var u = "t"+i+"_"+j
document.getElementById(u).style.cursor="pointer";
var y = alpha[g.matrice[i][j]]
document.getElementById(u).innerHTML=y
}
}
}
for(var i=0; i<g.n; i++) {
if(g.dateres[i]==g.date)
g.dateres[i]=-1;
g.res[i]=false;
}
g.date--
}
function reinit() {
document.getElementById("Commt").innerHTML="<br /><br /><br /><br />"
g.date=0;
for(var i=0; i<g.n; i++) {
for(var j=0; j<g.n; j++) {
g.history[i][j]=0
}
}
for(var i=0; i<g.n; i++) {
g.res[i]=false;
}
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
var u = "t"+r+'_'+s
var y;
g.mat2[r][s]=g.matrice[r][s]
if(g.matrice[r][s]!=null) {
y = alpha[g.matrice[r][s]]
document.getElementById(u).innerHTML=y
document.getElementById(u).style.cursor='pointer'
} else {
document.getElementById(u).innerHTML=''
document.getElementById(u).style.cursor='text'
}
}
}
}
function resolu() {
document.getElementById("Commt").innerHTML="<br /><br /><br /><br />"
for(var r=0; r<g.n; r++) {
for(var s=0; s<g.n; s++) {
var u = "t"+r+'_'+s
var x = g.ham[r][s]
if(x==null) {
y=""
document.getElementById(u).style.cursor='text'
} else {
y = alpha[x]
document.getElementById(u).style.cursor='pointer'
}
document.getElementById(u).innerHTML=y
}
}
}
function testefin() {
for(i=0; i<g.n;i++) {
u=0; v=0;
for(j=0; j<g.n; j++) {
u+=(g.mat2[i][j]!=null)?1:0;
v +=(g.mat2[j][i]!=null)?1:0;
}
if(u>1 || v>1) return false
}
return true
}
function testecomplet() {
for(i=0; i<g.n;i++) {
u=0; v=0;
for(j=0; j<g.n; j++) {
u +=(g.mat2[i][j]!=null)?1:0;
v +=(g.mat2[j][i]!=null)?1:0;
}
if(u==0 || v==0) return false
}
return true
}
function testecycle() {
var tab=[], tab2=[];
for(var i=0; i<g.n; i++){
for(var j=0; j<g.n; j++) {
if (g.mat2[i][j]!=null) {
tab[i]=j;
}
}
}
var a = tab[0];
for(i=0; i< g.n; i++) {
b = tab[a];
if(tab2[b] != null) return false
tab2[b]=1
a=b;
}
return true;
}
var modejeux = false
function jeux(m, k) {
modejeux = !modejeux
if(!modejeux) {
document.getElementById("Text").innerHTML ="";
return;
}
var s="";
document.getElementById("Text").innerHTML ="";
var niveau=0;
for(i=0; i<5; i++) {
if(document.fr.rd[i].checked) niveau=i
}
var tniv=[0.05,0.20,0.40,0.65,1];
var n = parseInt(document.fr.n.value);
if(n<3) n=3
else if(n>26) n=26;
document.fr.n.value = n
var tniv=[0.05,0.20,0.40,0.65,1];
for(var i=0; i<parseInt(k); i++) {
var gr=new graph();
n = parseInt(document.fr.n.value)
p =
gr.init(n, tniv[niveau]);
if(m==0) {
s += gr.totexte();
} else if(m==1) {
s += gr.togrid();
} else {
s += gr.tolatex();
}
document.getElementById("Text").innerHTML = "<pre>"+s+"</pre>"
delete(gr)
}
}
function essai() {
var s=document.fr2.ar.value;
if(g!= null) delete g;
g =new graph();
if(g!=null) {
g.fromtexte(s);
reinit();
}
}
function jeuxenligne(k, n, d) {
var s="";
var niveau=0;
var tniv=[0.05,0.20,0.40,0.65,1];
if(n<3) n=3
else if(n>26) n=26;
for(var i=0; i<parseInt(k); i++) {
var gr=new graph();
gr.init(n, tniv[d]);
s += gr.togrid();
delete(gr)
}
print(s)
}
function texteEnLigne() {
if(document.getElementById("lig").style.display=="none")
document.getElementById("lig").style.display="block";
else
document.getElementById("lig").style.display="none";
}
function jeuxenlatex(k, n, numb) {
var madate = ""
var nu = true
var debut=
"\\documentclass[11pt]{article}\n" +
"\\usepackage{epic,eepic}\n" +
"\\usepackage{times}\n" +
"\\usepackage{amssymb,amsfonts,amsxtra,eucal}\n" +
"\\usepackage[latin1]{inputenc}\n" +
"\\usepackage[francais]{babel}\n" +
"\\usepackage[dvips]{graphicx}\n" +
"\\voffset -0.2in\n" +
"\\hoffset -1in\n" +
"\\oddsidemargin=1.5cm\n" +
"\\evensidemargin=1cm\n" +
"\\topmargin=0.0cm\n" +
"\\textwidth=18.5cm\n" +
"\\textheight=26.5cm\n" +
"\\footskip=0.0cm\n" +
"\\pagestyle{myheadings}\n" +
"\\markboth{http://perso.orange.fr/jean-paul.davalan/jeux/logic/aec/index.html}"+
"{Arc-en-ciel "+numb+"}\n" +
"\\begin{document}\n" +
"\\parindent0pt\n"
var niveau=0;
var tniv=[0.05,0.20,0.40,0.65,1];
if(n<3) n=3
else if(n>26) n=26;
var dim=22, dim2 = 8, cote = n*dim;
var quad = "\\def\\Quadri\{%\\thicklines\n" +
"%\\put("+ dim +",0)\{\\grid(" + cote +","+ cote +")("+ cote  +","+ cote  +")\}\n" +
"\\thinlines\n" +
"\\put("+dim+",0)\{\\grid(" + cote +","+ cote +")("+ dim  +","+ dim  +")\}\}\n"
var s = debut + quad
var s1="";
var iniv=[1,2,2,3,4,5]
var pniv=[0.05,0.20,0.30,0.40,0.65,1];
for(var i=0; i<parseInt(k); i++) {
var gr=new graph();
if(arguments[4]!=null)
gr.init(n, parseFloat(arguments[4]));
else
gr.init(n, pniv[i]);
s += gr.tolatex(0, true);
if(i%2==1) s += "\\vskip5mm\n";
else s +="\\hspace{20mm}\n"
s1 += gr.tolatex(1, nu);
if(i%2==1) s1 += "\\vskip5mm\n";
else s1 +="\\hspace{20mm}\n"
delete(gr)
}
s += "{\\footnotesize "+
"1) Entourez une fois et une seule chacune des huit lettres a, b, c, d, e, f, g, h.\\\\ "+
"2) Une lettre de chaque ligne et aussi de chaque colonne doit être entourée. \\\\"+
"3) On doit pouvoir en déduire un cycle sur l'ensemble des huit sommets A, B, C, D, E, F, G, H.}"
s += "\\clearpage\n"+s1
s += "\\end\{document\}\n";
//print(s)
return s;
}
// print(jeuxenlatex(6, 8, 1))
//system("cat x2.js|js > essai.tex;pdflatex essai.tex");
function imp() {
var s="<pre>"+(jeuxenlatex(6,8,-10))+"</pre>"
document.getElementById("Text").innerHTML=s;
}