/* 3cols.js 3colsB.js
	Jeu 3 Couleurs (jeu de transpositions de pions)
  Copyright (C) 2006 Jean-Paul Davalan
*/
function bij(t, n) {
for(var i=0; i<n; i++)  {
t[i]=i;
}
for(var i=n-1; i>0; i--) {     
var j= Math.floor((i+1)*Math.random()); 
if(i != j) {
var c= t[j]; t[j] = t[i]; t[i] = c;  
}
}
}
var K, k=0, d, m0, a, b, x1;
var tab = [];	
var cols=[0,1,2,0,1,2,0,1,2];	
var absc=[0,1,2,3,4,5,6,7,8];	
var rg=[0,1,2,3,4,5,6,7,8];	
function chge(n) {
if(idt != null)
return;
var m=tab[n];	
var u = absc[m];
if(demoencours==true) {
document.getElementById("fl").style.zIndex=4;
document.getElementById("fl").style.left=(50*absc[n]+30)+"px";
document.getElementById("fl").style.display="block"
document.images["fle"].src="fle.png"
}
absc[m]=absc[n];
absc[n]=u;	
rg[absc[m]]=m; rg[absc[n]]=n;        
var test = false;
for(var i=0; test == false && i<7; i++) {
if(cols[rg[i]]==cols[rg[i+1]] && cols[rg[i]]==cols[rg[i+2]] ) {
test = true
}
}
for(var i=0; i<9; i++) {
document.getElementById("s"+i).style.zIndex = 1;
}
document.getElementById("s"+m).style.zIndex=2;
document.getElementById("s"+n).style.zIndex=3;
a =parseInt(document.getElementById("s"+n).style.left.replace(/px/g,""))
b =parseInt(document.getElementById("s"+m).style.left.replace(/px/g,""))
var u = a-b
k = Math.abs(u/5);
K=k-1;
d =(u<0)?-1 : 1
d = 5*d
m0=m;
n0=n;
bouge();
if(test) {
if(!demoencours)
document.getElementById("commt").innerHTML="Bravo. <span style='cursor:pointer;color:blue;' onclick='unique(1);'>Une autre partie ?</span>";
else
document.getElementById("commt").innerHTML="<br />Solution"
}
}
var idt;
function bouge() {
if(k<=0) {
clearTimeout(idt)
idt=null
return;
}
var z;
a -=d
b +=d
z = (k<=K/2)? k-1 : K-k;
document.getElementById("s"+n0).style.left =a+"px"
document.getElementById("s"+n0).style.top =(30-z)+"px"
document.getElementById("s"+m0).style.left =b+"px"
document.getElementById("s"+m0).style.top =(30+z)+"px"
k--
if(idt) clearTimeout(idt)
idt = setTimeout("bouge()",30)
}
var decale = 10
function initplaces() {
for(var i=0; i<9; i++) {
document.getElementById("f"+i).innerHTML=(tab[i]+1)
document.getElementById("s"+i).style.left =(decale+50*i)+"px"
absc[i]=i;
rg[i]=i;
}
document.getElementById("commt").innerHTML="";
}
var slv = null;
function nodemo() {
kdemo=0
if(idt!=null) clearTimeout(idt);
if(iddemo!=null) clearTimeout(iddemo);
}
function nouveau() {
nodemo();
bij(tab,9);
if(slv != null) delete(slv)
slv = new solveur(tab, 9);
infos();
initplaces()
}
function usager() {
nodemo();
var u = document.frm2.p.value, v;
do {
v=u
u = u.replace(/[\s\n]+/g," ");
u = u.replace(/[\;]+$/,"");
u = u.replace(/[\s]+$/,"");
u = u.replace(/\s*\;\s*/,";");
}while(u!=v);
var txt = u.split(/\;+/g);
for(i=0; i<2 && i<txt.length; i++) {
txt[i] = txt[i].replace(/^\s+/,"");
txt[i] = txt[i].replace(/\s+$/,"");
txt[i] = txt[i].replace(/\s+/g," ");
}
for(var i=2; i<txt.length; i++) delete(txt[i])
if(txt.length>1 && txt[1]=="") delete(txt[1])
if(txt.length==1)
document.frm2.p.value = txt[0]
else
document.frm2.p.value = txt[0]+";"+txt[1]
var tb = txt[0].split(/\s/g);
var tc = [];
for(var i=0; i<9 && i<tb.length; i++) {
tb[i] = parseInt(tb[i])-1
}
for(var i=0; i<tb.length; i++) {
tc[tb[i]]=0;
}
for(var i=0; i<tb.length; i++) {
tc[tb[i]]++;
}
var test = true
for(var i=0; test && i<9; i++) {
if(tc[i]==null || tc[i]!=1)  {
test = false
}
}
if(test==false) {
document.frm2.p.value="Incorrect";
return;
} else {
initplaces()
for(var i=0; i<9; i++) {
tab[i] = tb[i];
}
if(slv != null) delete(slv);
slv = new solveur(tab, 9);
infos();
}
initplaces()
if(txt.length>1) {
demoencours=true;
if(demotab!=null) delete(demotab);
demotab = txt[1].split(/\s/g);
kdemo = demotab.length-1;
iddemo=setTimeout("nextdemo2()",2500);
}
}
function unique(t) {
nodemo();
for(var i=0; i<9; i++) {
absc[i]=i;
rg[i]=i;
}
do {
bij(tab,9);
if(slv != null) delete(slv)
slv = new solveur(tab, 9);
}while(slv.nsols != t);
infos();
initplaces()
}
function f2c() {
nodemo();
for(var i=0; i<9; i++) {
absc[i]=i;
rg[i]=i;
}
var test
do {
test = true
bij(tab,9);
if(slv != null) delete(slv)
slv = new solveur(tab, 9);
if(slv.nsols<2) test = false
for(var i=0; test && i<slv.nsols-1; i++) {
var c1 = slv.solus[i]
for(var j=i+1; test && j<slv.nsols; j++) {
var c2=slv.solus[j]
var d1 = Math.abs(c1.x-c2.x);
if((d1<3)||c1.col == c2.col) test = false
}
}
} while(test==false);
infos();
initplaces()
}
function f3c() {
nodemo();
for(var i=0; i<9; i++) {
absc[i]=i;
rg[i]=i;
}
var test
do {
test = true
bij(tab,9);
if(slv != null) delete(slv)
slv = new solveur(tab, 9);
if(slv.nsols<3) test = false
for(var i=0; test && i<slv.nsols-2; i++) {
var c1 = slv.solus[i]
for(var j=i+1; test && j<slv.nsols-1; j++) {
var c2=slv.solus[j]
var d1 = Math.abs(c1.x-c2.x);
if((d1!=3 && d1!= 6)||c1.col == c2.col) test = false
for(var k=j+1; test && k<slv.nsols; k++) {
var c3=slv.solus[k]
var d2 = Math.abs(c1.x-c3.x);
var d3 = Math.abs(c2.x-c3.x);
if((d2!=3 && d2!= 6)||(d3!=3 && d3!= 6)||c1.col == c3.col|| c2.col == c3.col) test = false
}}}
} while(test==false);
infos();
initplaces()
}
function stats(k) {
document.getElementById("sols").innerHTML="";
var sum=0, sum2=0, cycl=0, cycl2=0, xy=0, uniq=0, aucune=0;
for(var i=0; i<k; i++) {
bij(tab,9);
if(slv != null) delete(slv)
slv = new solveur(tab, 9);
uniq += (slv.nsols==1)? 1 : 0;
aucune += (slv.nsols==0)? 1 : 0;
sum += slv.nsols;
sum2 += slv.nsols*slv.nsols;
cycl += slv.ncycles
cycl2 += slv.ncycles*slv.ncycles;
xy += slv.nsols*slv.ncycles
}
var msols = sum/k, sigmasols = Math.sqrt(sum2/k-msols*msols),
mcycl=cycl/k, sigmacycl=Math.sqrt(cycl2/k-mcycl*mcycl),
covxy = xy/k-msols*mcycl,
sigmaxy = Math.sqrt(covxy),
correl =covxy/(sigmasols*sigmacycl);
document.getElementById("stts").innerHTML=
"<pre>"+
"Nombre moyen de solutions : "+msols+"  (écart-type : "+sigmasols+")\n"+
"Nombre moyen de cycles    : "+mcycl+"  (écart-type : "+sigmacycl+")\n"+
"Covariance : "+covxy+"\n"+
"Coef Corrél. lin. : "+correl+"\n"+
"Fréquence des jeux sans solutions : "+(aucune/k)+"\n"+
"Fréquence des solutions uniques : "+(uniq/k)+"\n"+
"</pre>";
}
function infos() {
if(document.frm.ck[0].checked) {
document.getElementById("sols").innerHTML="";
} else if (document.frm.ck[1].checked) {
afficheSolutions()
} else if(document.frm.ck[2].checked) {
afficheSolutions2()
}
}
function afficheSolutions() {
document.getElementById("sols").innerHTML="";
if(slv != null) {
var str = (slv.comment!="")?"<pre>"+slv.comment+"</pre>" : "Pas de solution";
document.getElementById("sols").innerHTML=str
}
}
function afficheSolutions2() {
var str = "<pre>Permutation :\n", s0="[ ", s1="[ "
for(var i=0; i<9; i++) {
s0 += (i+1)+" "
s1 += (tab[i]+1)+" "
}
s0 += " ] <-- en cliquant le pion\n"; s1 += " ] <-- il s'échange avec celui-ci\n"; str += s0+s1;
if(slv.ncycles==1)  str +="un seul cycle :\n"
else str += slv.ncycles+" cycles :\n";
str += slv.infos+"\n"
if(slv != null) {
str += (slv.comment!="")? slv.comment : "Pas de solution";
}
str += "</pre>"
document.getElementById("sols").innerHTML=str
}
function permtos() {
var s = "<code>"
for(var i=0; i<9; i++) {
s += (parseInt(tab[i])+1) + ((i<8)?" ":"</code>");
}
document.getElementById("p3").innerHTML=s;
}
function reinit() {
initplaces()
}
function cycle(m, t, n, a) {
this.n=n;
this.cy = new Array();
this.orig = a;
this.l = 0;
this.colors = new Array(0,0,0);  
this.txt="";
this.txt2="";
for(var i=0; i<n; i++)
this.cy[i]=false
var b=a;
do {
this.txt += (this.txt=="")? "(" : " ";
this.txt += (b+1);
this.l++;
this.cy[b]=true;
m[b] = false
this.colors[b%3]++;   
b = t[b];
} while(b != a);
this.txt += ")";
var cl = ["R","V","B"]
for(var i=0; i<3; i++) {
if(this.colors[i]!=0) {
for(var j=0; j< this.colors[i]; j++) {
this.txt2 += cl[i]
}
this.txt2 += " ";
}
}
this.txt2
}
function minimum(x, y) {
return (x<y)?x : y;
}
function uneSolu(c,x) {
this.col=c; 
this.x=x;   
this.icycles=new Array(3); 
this.quels =new Array();  
}
function solveur(t, n) {
this.cycles = new Array();
this.ncycles = 0;
this.comment="";
this.infos ="";
this.nsols=0;
this.solus=new Array();
function lesCycles(t, n) {
this.infos = "";
var m = new Array(n)
for(var i=0; i<n; i++)
m[i] = true;
var maxl=0;
for(var i=0; i<n; i++) {
if(m[i]==true) {
var c = new cycle(m, t, n, i)
this.cycles[this.cycles.length]=c;
this.ncycles++;
if(c.txt.length>maxl) maxl = c.txt.length;
}
}
for(var i=0; i<this.cycles.length; i++) {
var c = this.cycles[i]
var u = c.txt;
while(u.length<maxl+2) u += " "
this.infos += u +c.txt2+"\n"
}
}
this.lesCycles=lesCycles;
this.lesCycles(t, n);
for(var i=0; i<7; i++) {
var induite = new Array(this.ncycles);
var compte = new Array();
for(var j=0; j<this.ncycles; j++) {
var u =new Array();
var z=0
compte[j]=0
for(var k=0; k< n; k++) {
u[k] = (k>=i && k<=i+2 && this.cycles[j].cy[k]==true)
if(u[k]) {
z++
compte[j]++
}
}
if(z>0) induite[j] = u;
}
for(var r=0; r<3; r++) {
var ns = 0
for(var j=0; j<this.ncycles; j++) {
ns += minimum(compte[j], this.cycles[j].colors[r])
}
if(ns == 3 ) {
this.comment += "solution "+couleurs[r]+ " en "+(i+1)+" "+(i+2)+" "+(i+3)+"\n";
this.solus[this.nsols] = new uneSolu(r,i);
for(var j=0; j<this.ncycles;j++) {
for(var k=0; k<3; k++) {
if(this.cycles[j].cy[i+k]==true) {
this.solus[this.nsols].icycles[k]=j
var test=true
for(var kk=0; test && kk<this.solus[this.nsols].quels.length;kk++) {
if(this.solus[this.nsols].quels[kk]==j) test = false
}
if(test) {
var ll=this.solus[this.nsols].quels
this.solus[this.nsols].quels[ll]=j;
}
}
}
}
this.nsols++;
}
}
}
}
var couleurs = ["Rouge","Verte","Bleue"];
function solve(k) {
if(k>= slv.nsols) return;
this.clics=new Array();
var t = new Array(0,1,2,3,4,5,6,7,8);
var col = slv.solus[k].col, x=slv.solus[k].x;
for(var i=0; i<slv.solus[k].quels.length  ;i++) {
var cy = slv.solus[k].quels[i];
var test=false;
var j;
for(j=0; !test && j<3; j++) {
if(slv.solus[k].icycles[j]==cy) test = true
}
while(	(slv.solus[k].icycles[0]==cy&&t[x]%3!=col) ||
(slv.solus[k].icycles[1]==cy&&t[x+1]%3!=col) ||
(slv.solus[k].icycles[2]==cy&&t[x+2]%3!=col) ) {
this.clics[this.clics.length] = t[x+j]
var u = t[x+j], v= tab[x+j]
for(r=0; r<9; r++) {
if(t[r]==v) {
t[r]=u
t[x+j]=v
break;
}
}
}
}
}
var kdemo, iddemo;
var demotab = null
function demo() {
unique(1);
kdemo = 5+Math.floor(10*Math.random())
nextdemo();
}
function nextdemo() {
if(iddemo!=null) clearTimeout(iddemo);
var u = Math.floor(9*Math.random());
chge(u);
kdemo--;
if(kdemo<0) return
iddemo=setTimeout("nextdemo();",1500);
}
var demotable = new Array(
"9 5 3 4 6 1 7 2 8;1 2 5",
"2 1 7 6 3 4 5 8 9;2 3",
"7 3 5 2 4 9 8 1 6;1 7 3",
"7 2 3 4 1 5 8 6 9;5 1 7 8 6 5 1 7 8 6 5",
"7 2 3 4 1 5 8 6 9;5 8 7",
"1 6 5 4 2 3 9 8 7;9 3",
"8 2 1 4 6 5 3 9 7;7 8",
"8 5 1 3 9 6 7 4 2;4 5",
"7 8 3 5 9 1 6 4 2;6 5 9 2 8",
"7 8 3 5 9 1 6 4 2;6 8",
"7 8 3 5 9 1 6 4 2;6 5 9",
"3 8 6 7 5 2 4 9 1;6 9",
"3 6 9 4 2 8 7 5 1;9 2",
"9 2 3 1 6 5 4 8 7;4 1 5",
"4 6 1 3 7 8 5 2 9;3 5 2",
"2 3 9 1 7 6 5 8 4;2 1 5 3 2",
"3 4 7 2 5 1 6 9 8;2 3 8",
"6 8 2 5 4 1 3 7 9;7 8 4 1 7",
"3 5 9 2 6 4 8 7 1;9 2 5 7",
"6 9 5 3 4 2 7 8 1;1 2 5",
"9 7 5 8 3 6 1 4 2;3 4 7 1 7 1",
"5 8 6 4 2 9 3 1 7;2 8 7 1 6 9 9 1",
"5 3 2 7 6 9 8 4 1;3 8 6 9",
"4 5 2 9 1 7 8 6 3;5 6 7 5 4 9 3 8 3 5 1 4",
"5 8 2 6 9 3 1 4 7;1 8 6 4 8 7 9", 
"2 8 9 5 3 7 6 1 4;8 5 9",
"9 8 3 2 4 5 7 6 1;9 2 8 4",
"1 8 4 3 9 6 2 7 5;2 8 3 5",
"8 3 1 9 2 6 7 5 4;1 9 5 2",
"9 7 4 3 1 6 8 2 5;2 4 9"
);
var demoencours=false;
function demo2() {
var k =Math.floor(demotable.length*Math.random());
document.frm2.p.value=demotable[k];
demoencours=true;
usager();
}
function nextdemo2() {
if(iddemo!=null) clearTimeout(iddemo);
if(kdemo<0) {
document.getElementById("commt").innerHTML="<br />Fin de la <span style='cursor:pointer;color:blue;' onclick='demo2();'>DEMO</span>"
demoencours=false;
document.getElementById("fl").style.display="none"
return
}
var u = parseInt(demotab[demotab.length-kdemo-1])-1
chge(u);
kdemo--;
iddemo=setTimeout("nextdemo2();",3200);
}