/* wyxGen.js wyxGen.2
  génère des grilles de solutions de Wyx
  Copyright (C) 2006 Jean-Paul Davalan
*/
function bij(t, k) {
var i, j, a
for(i=k-1;i>0;i--) {
j=Math.floor((i+1.0)*Math.random())
if(j!=i) {
a=t[j];t[j]=t[i];t[i]=a
}
}
}
var V=[
[0,1],[0,2],[0,3],[0,4],[1,1],[1,2],[1,3],[1,4],
[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[4,1],[4,2],
[1,0],[2,0],[3,0],[4,0],[0,-1],[0,-2],[0,-3],[0,-4],
[1,-1],[1,-2],[1,-3],[1,-4],[2,-1],[2,-2],[2,-3],[2,-4],
[3,-1],[3,-2],[4,-1],[4,-2],[-1,1],[-1,2],[-1,3],[-1,4],
[-2,1],[-2,2],[-2,3],[-2,4],[-3,1],[-3,2],[-4,1],[-4,2],
[-1,0],[-2,0],[-3,0],[-4,0],[-1,-1],[-1,-2],[-1,-3],[-1,-4],
[-2,-1],[-2,-2],[-2,-3],[-2,-4],[-3,-1],[-3,-2],[-4,-1],[-4,-2]]
var alphanumb=["Zéro","Une","Deux","Trois","Quatre","Cinq","Six","Sept","Huit","Neuf","Dix","Onze","Douze","Treize","Quatorze","Quinze","Seize","Dix-sept","Dix-huit","dix-neuf","Vingt"]
function sol() {
var ecart=7, i, j
var     p=new Array(13),
b=new Array(13),
ens=new Array(12),
vv=new Array(12),
v=new Array(12)
for(i=0;i<13;i++) {
b[i]=new Array()
p[i]=new Array()
}
for(i=0;i<12;i++) {
ens[i]=new Array()
vv[i]=new Array()
}
b[0][1]=b[0][2]=b[0][3]=b[0][4]=0
p[0][0]=0;p[0][1]=0
for(i=0;i<64;i++) {ens[0][i]=i;}
bij(ens[0],64)
for(v[0]=0;v[0]<64;v[0]++) {
var i, j
vv[0]=ens[0][v[0]]
p[1][0]=p[0][0]+V[vv[0]][0]
p[1][1]=p[0][1]+V[vv[0]][1]
b[1][0]=b[1][1]=b[1][2]=b[1][3]=0
if(p[1][0]<0) b[1][0]=p[1][0]
if(p[1][0]>0) b[1][1]=p[1][0]
if(p[1][1]<0) b[1][2]=p[1][1]
if(p[1][1]>0) b[1][3]=p[1][1]
if(b[1][1]-b[1][0]>ecart || b[1][3]-b[1][2]>ecart) continue
for(i=0, j=0;i<64;i++) {
if(ens[0][i]!=vv[0]) {
ens[1][j]=ens[0][i]
j++
}
}
bij(ens[1],63)
for(v[1]=0;v[1]<63;v[1]++) {
var i, j
vv[1]=ens[1][v[1]]
p[2][0]=p[1][0]+V[vv[1]][0]
p[2][1]=p[1][1]+V[vv[1]][1]
if(p[2][0]<b[1][0]) b[2][0]=p[2][0]
else b[2][0]=b[1][0]
if(p[2][0]>b[1][1])b[2][1]=p[2][0]
else b[2][1]=b[1][1]
if(p[2][1]<b[1][2])b[2][2]=p[2][1]
else b[2][2]=b[1][2]
if(p[2][1]>b[1][3])b[2][3]=p[2][1]
else b[2][3]=b[1][3]
if(b[2][1]-b[2][0]>ecart || b[2][3]-b[2][2]>ecart) continue
var test=0
for(i=0;!test && i<2;i++) {
if(p[i][0]==p[2][0] && p[i][1]==p[2][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<63;i++) {
if(ens[1][i]!=vv[1]) {
ens[2][j]=ens[1][i]
j++
}
}
bij(ens[2],62)
for(v[2]=0;v[2]<62;v[2]++) {
var i, j
vv[2]=ens[2][v[2]]
p[3][0]=p[2][0]+V[vv[2]][0]
p[3][1]=p[2][1]+V[vv[2]][1]
if(p[3][0]<b[2][0]) b[3][0]=p[3][0]
else b[3][0]=b[2][0]
if(p[3][0]>b[2][1])b[3][1]=p[3][0]
else b[3][1]=b[2][1]
if(p[3][1]<b[2][2])b[3][2]=p[3][1]
else b[3][2]=b[2][2]
if(p[3][1]>b[2][3])b[3][3]=p[3][1]
else b[3][3]=b[2][3]
if(b[3][1]-b[3][0]>ecart || b[3][3]-b[3][2]>ecart) continue
var test=0
for(i=0;!test && i<3;i++) {
if(p[i][0]==p[3][0] && p[i][1]==p[3][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<62;i++) {
if(ens[2][i]!=vv[2]) {
ens[3][j]=ens[2][i]
j++
}
}
bij(ens[3],61)
for(v[3]=0;v[3]<61;v[3]++) {
var i, j
vv[3]=ens[3][v[3]]
p[4][0]=p[3][0]+V[vv[3]][0]
p[4][1]=p[3][1]+V[vv[3]][1]
if(p[4][0]<b[3][0]) b[4][0]=p[4][0]
else b[4][0]=b[3][0]
if(p[4][0]>b[3][1])b[4][1]=p[4][0]
else b[4][1]=b[3][1]
if(p[4][1]<b[3][2])b[4][2]=p[4][1]
else b[4][2]=b[3][2]
if(p[4][1]>b[3][3])b[4][3]=p[4][1]
else b[4][3]=b[3][3]
if(b[4][1]-b[4][0]>ecart || b[4][3]-b[4][2]>ecart) continue
var test=0
for(i=0;!test && i<4;i++) {
if(p[i][0]==p[4][0] && p[i][1]==p[4][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<61;i++) {
if(ens[3][i]!=vv[3]) {
ens[4][j]=ens[3][i]
j++
}
}
bij(ens[4],60)
for(v[4]=0;v[4]<60;v[4]++) {
var i, j
vv[4]=ens[4][v[4]]
p[5][0]=p[4][0]+V[vv[4]][0]
p[5][1]=p[4][1]+V[vv[4]][1]
if(p[5][0]<b[4][0]) b[5][0]=p[5][0]
else b[5][0]=b[4][0]
if(p[5][0]>b[4][1])b[5][1]=p[5][0]
else b[5][1]=b[4][1]
if(p[5][1]<b[4][2])b[5][2]=p[5][1]
else b[5][2]=b[4][2]
if(p[5][1]>b[4][3])b[5][3]=p[5][1]
else b[5][3]=b[4][3]
if(b[5][1]-b[5][0]>ecart || b[5][3]-b[5][2]>ecart) continue
var test=0
for(i=0;!test && i<5;i++) {
if(p[i][0]==p[5][0] && p[i][1]==p[5][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<60;i++) {
if(ens[4][i]!=vv[4]) {
ens[5][j]=ens[4][i]
j++
}
}
bij(ens[5],59)
for(v[5]=0;v[5]<59;v[5]++) {
var i, j
vv[5]=ens[5][v[5]]
p[6][0]=p[5][0]+V[vv[5]][0]
p[6][1]=p[5][1]+V[vv[5]][1]
if(p[6][0]<b[5][0]) b[6][0]=p[6][0]
else b[6][0]=b[5][0]
if(p[6][0]>b[5][1])b[6][1]=p[6][0]
else b[6][1]=b[5][1]
if(p[6][1]<b[5][2])b[6][2]=p[6][1]
else b[6][2]=b[5][2]
if(p[6][1]>b[5][3])b[6][3]=p[6][1]
else b[6][3]=b[5][3]
if(b[6][1]-b[6][0]>ecart || b[6][3]-b[6][2]>ecart) continue
var test=0
for(i=0;!test && i<6;i++) {
if(p[i][0]==p[6][0] && p[i][1]==p[6][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<59;i++) {
if(ens[5][i]!=vv[5]) {
ens[6][j]=ens[5][i]
j++
}
}
bij(ens[6],58)
for(v[6]=0;v[6]<58;v[6]++) {
var i, j
vv[6]=ens[6][v[6]]
p[7][0]=p[6][0]+V[vv[6]][0]
p[7][1]=p[6][1]+V[vv[6]][1]
if(p[7][0]<b[6][0]) b[7][0]=p[7][0]
else b[7][0]=b[6][0]
if(p[7][0]>b[6][1])b[7][1]=p[7][0]
else b[7][1]=b[6][1]
if(p[7][1]<b[6][2])b[7][2]=p[7][1]
else b[7][2]=b[6][2]
if(p[7][1]>b[6][3])b[7][3]=p[7][1]
else b[7][3]=b[6][3]
if(b[7][1]-b[7][0]>ecart || b[7][3]-b[7][2]>ecart) continue
var test=0
for(i=0;!test && i<7;i++) {
if(p[i][0]==p[7][0] && p[i][1]==p[7][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<58;i++) {
if(ens[6][i]!=vv[6]) {
ens[7][j]=ens[6][i]
j++
}
}
bij(ens[7],57)
for(v[7]=0;v[7]<57;v[7]++) {
var i, j
vv[7]=ens[7][v[7]]
p[8][0]=p[7][0]+V[vv[7]][0]
p[8][1]=p[7][1]+V[vv[7]][1]
if(p[8][0]<b[7][0]) b[8][0]=p[8][0]
else b[8][0]=b[7][0]
if(p[8][0]>b[7][1])b[8][1]=p[8][0]
else b[8][1]=b[7][1]
if(p[8][1]<b[7][2])b[8][2]=p[8][1]
else b[8][2]=b[7][2]
if(p[8][1]>b[7][3])b[8][3]=p[8][1]
else b[8][3]=b[7][3]
if(b[8][1]-b[8][0]>ecart || b[8][3]-b[8][2]>ecart) continue
var test=0
for(i=0;!test && i<8;i++) {
if(p[i][0]==p[8][0] && p[i][1]==p[8][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<57;i++) {
if(ens[7][i]!=vv[7]) {
ens[8][j]=ens[7][i]
j++
}
}
bij(ens[8],56)
for(v[8]=0;v[8]<56;v[8]++) {
var i, j
vv[8]=ens[8][v[8]]
p[9][0]=p[8][0]+V[vv[8]][0]
p[9][1]=p[8][1]+V[vv[8]][1]
if(p[9][0]<b[8][0]) b[9][0]=p[9][0]
else b[9][0]=b[8][0]
if(p[9][0]>b[8][1])b[9][1]=p[9][0]
else b[9][1]=b[8][1]
if(p[9][1]<b[8][2])b[9][2]=p[9][1]
else b[9][2]=b[8][2]
if(p[9][1]>b[8][3])b[9][3]=p[9][1]
else b[9][3]=b[8][3]
if(b[9][1]-b[9][0]>ecart || b[9][3]-b[9][2]>ecart) continue
var test=0
for(i=0;!test && i<9;i++) {
if(p[i][0]==p[9][0] && p[i][1]==p[9][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<56;i++) {
if(ens[8][i]!=vv[8]) {
ens[9][j]=ens[8][i]
j++
}
}
bij(ens[9],55)
for(v[9]=0;v[9]<55;v[9]++) {
var i, j
vv[9]=ens[9][v[9]]
p[10][0]=p[9][0]+V[vv[9]][0]
p[10][1]=p[9][1]+V[vv[9]][1]
if(p[10][0]<b[9][0]) b[10][0]=p[10][0]
else b[10][0]=b[9][0]
if(p[10][0]>b[9][1])b[10][1]=p[10][0]
else b[10][1]=b[9][1]
if(p[10][1]<b[9][2])b[10][2]=p[10][1]
else b[10][2]=b[9][2]
if(p[10][1]>b[9][3])b[10][3]=p[10][1]
else b[10][3]=b[9][3]
if(b[10][1]-b[10][0]>ecart || b[10][3]-b[10][2]>ecart) continue
var test=0
for(i=0;!test && i<10;i++) {
if(p[i][0]==p[10][0] && p[i][1]==p[10][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<55;i++) {
if(ens[9][i]!=vv[9]) {
ens[10][j]=ens[9][i]
j++
}
}
bij(ens[10],54)
for(v[10]=0;v[10]<54;v[10]++) {
var i, j
vv[10]=ens[10][v[10]]
p[11][0]=p[10][0]+V[vv[10]][0]
p[11][1]=p[10][1]+V[vv[10]][1]
if(p[11][0]<b[10][0]) b[11][0]=p[11][0]
else b[11][0]=b[10][0]
if(p[11][0]>b[10][1])b[11][1]=p[11][0]
else b[11][1]=b[10][1]
if(p[11][1]<b[10][2])b[11][2]=p[11][1]
else b[11][2]=b[10][2]
if(p[11][1]>b[10][3])b[11][3]=p[11][1]
else b[11][3]=b[10][3]
if(b[11][1]-b[11][0]>ecart || b[11][3]-b[11][2]>ecart) continue
var test=0
for(i=0;!test && i<11;i++) {
if(p[i][0]==p[11][0] && p[i][1]==p[11][1]) test=1
}
if(test==1) continue
for(i=0, j=0;i<54;i++) {
if(ens[10][i]!=vv[10]) {
ens[11][j]=ens[10][i]
j++
}
}
bij(ens[11],53)
for(v[11]=0;v[11]<53;v[11]++) {
var i, j
vv[11]=ens[11][v[11]]
p[12][0]=p[11][0]+V[vv[11]][0]
p[12][1]=p[11][1]+V[vv[11]][1]
if(p[12][0]<b[11][0]) b[12][0]=p[12][0]
else b[12][0]=b[11][0]
if(p[12][0]>b[11][1])b[12][1]=p[12][0]
else b[12][1]=b[11][1]
if(p[12][1]<b[11][2])b[12][2]=p[12][1]
else b[12][2]=b[11][2]
if(p[12][1]>b[11][3])b[12][3]=p[12][1]
else b[12][3]=b[11][3]
if(b[12][1]-b[12][0]>ecart || b[12][3]-b[12][2]>ecart) continue
var test=0
for(i=0;!test && i<12;i++) {
if(p[i][0]==p[12][0] && p[i][1]==p[12][1]) test=1
}
if(test==1) continue
var pts=[], vts=[]
for(i=0;i<13;i++) {
pts[2*i]=p[i][0]
pts[2*i+1]=p[i][1]
}
for(i=0;i<12;i++) {
vts[2*i]=V[vv[i]][0]
vts[2*i+1]=V[vv[i]][1]
}
var nsolus=nsols(pts[0],pts[1], pts, vts, 12)
var ret=""
for(i=0;i<13;i++) {
ret +=p[i][0]+" "+p[i][1]+"  "
}
ret +="\n"
for(i=0;i<12;i++) {
ret +=V[vv[i]][0]+" "+V[vv[i]][1]+"  "
}
ret +="\n"+nsolus
return ret
}}}}}}}}}}}}
}
pnoms="A B C D E F G H I J K L M N".split(/\s+/g)
vnoms="a b c d e f g h i j k l m".split(/\s+/g)
function brasse(t, k) {
var i,j,u,a
for(i=0;i<k;i++) t[i]=i
for(i=k-1;i>0;i--) {
u=Math.floor((i+1)*Math.random())
if(u!=i) {
a=t[i]
t[i]=t[u]
t[u]=a
}
}
}
function brasse1(t, k) {
var i
for(i=0;i<k;i++) t[i]=i
}
function brasse2(t, k) {
var i,j,u,a
for(i=0;i<k;i++) t[i]=i
for(i=k-2;i>1;i--) {
u=1+Math.floor((i)*Math.random())
if(u!=i) {
a=t[i]
t[i]=t[u]
t[u]=a
}
}
}
function prepare(str) {
var ret=""
var tab=str.split(/\n/g)
var p=tab[0].split(/\s+/g)
var v=tab[1].split(/\s+/g)
var nsolutions=parseInt(tab[2])
var xvect=[]
var yvect=[]
var rgv=[]
var xpt=[]
var ypt=[]
var rgp=[]
var lv=12
var vv=[]
brasse(vv, lv)
for(i=0;i<lv;i++) {
xvect[vv[i]]=parseInt(v[2*i])
yvect[vv[i]]=parseInt(v[2*i+1])
rgv[xvect[vv[i]]+" "+yvect[vv[i]]]=vv[i]
}
var vcorr="Vecteurs : "
for(i=0;i<lv;i++) {
vcorr +=vnoms[rgv[v[2*i]+" "+v[2*i+1]]]+" "
}
var lp=13
var pp=[]
brasse2(pp, lp)
for(i=0;i<lp;i++) {
xpt[pp[i]]=parseInt(p[2*i])
ypt[pp[i]]=parseInt(p[2*i+1])
rgp[xpt[pp[i]]+" "+ypt[pp[i]]]=pp[i]
}
var pcorr="Points : "
for(i=0;i<lp;i++) {
pcorr +=pnoms[rgp[p[2*i]+" "+p[2*i+1]]]+" "
}
nvect=[]
nvectP=[]
liste=[]
listeP=[]
for(i=0;i<lp;i++) {
listeP[i]=[]
liste[i]=[]
}
for(i=0;i<lp;i++) {
nvect[i]=0   
nvectP[i]=0  
for(j=0;j<lp;j++) {
if(j==i) continue
a=xpt[j]-xpt[i]
b=ypt[j]-ypt[i]
if(rgv[a+" "+b]==null) continue
liste[i][nvect[i]]=rgv[a+" "+b]
nvect[i]++
}
for(j=0;j<lp;j++) {
if(j==i) continue
a=xpt[i]-xpt[j]
b=ypt[i]-ypt[j]
if(rgv[a+" "+b]==null) continue
listeP[i][nvectP[i]]=rgv[a+" "+b]
nvectP[i]++
}
}
ret +="Points :\n--------\n"
for(i=0;i<lp;i++) {
ret +=pnoms[i]+"("+xpt[i]+", "+ypt[i]+") "
}
ret +="\n"
ret +="Vecteurs :\n----------\n"
for(i=0;i<lv;i++) {
ret +=vnoms[i]+"("+xvect[i]+", "+yvect[i]+") "
}
ret +="\n"
if(rgv[(-xpt[lv])+" "+(-ypt[lv])]==null) {
for(i=0;i<64;i++) {
if(V[i][0]==-xpt[lv]&&V[i][1]==-ypt[lv]) {
ret +="On pourrait compléter avec le vecteur m("+(-xpt[lv])+", "+(-ypt[lv])+") "+
"pour obtenir un circuit hamiltonien multicoloré.\n"
break
}
}
}
xmini=xmaxi=ymini=ymaxi=0
for(i=0;i<lp;i++) {
if(xpt[i]<xmini) xmini=xpt[i]
if(xpt[i]>xmaxi) xmaxi=xpt[i]
if(ypt[i]<ymini) ymini=ypt[i]
if(ypt[i]>ymaxi) ymaxi=ypt[i]
}
var quadr=[]
for(i=xmini;i<=xmaxi;i++) {
quadr[i]=[]
for(j=ymini;j<=ymaxi;j++) {
quadr[i][j]="   "
}
}
for(i=0;i<lp;i++) {
var u=xpt[i], v=ypt[i]
if(quadr[u]==null) quadr[u]=[]
quadr[u][v]=" "+pnoms[i]+" "
}
squad="\n"
squad+="Schéma des points :\n"+
"-------------------\n"
for(j=ymaxi;j>=ymini;j--) {
squad +="        "
for(i=xmini;i<=xmaxi;i++) {
squad +=quadr[i][j]
}
squad +="\n"
}
squad +="\n\n"
ret +=squad
var matrice=new Array()
for(i=0;i<lp;i++) {
matrice[i]=new Array()
for(j=0;j<lp;j++) {
x=xpt[j]-xpt[i]
y=ypt[j]-ypt[i]
if(rgv[x+" "+y]!=null) {
matrice[i][j]=rgv[x+" "+y]
} else {
matrice[i][j]=" "
}
}
}
ret +="Tableau :\n"+
"---------\n"
ret +="  | "
for(i=0;i<lp;i++) {
ret +=pnoms[i]+" "
}
ret +="\n"
ret +="--+-"
for(i=0;i<lp;i++) {
ret +="--"
}
ret +="\n"
for(i=0;i<lp;i++) {
ret +=pnoms[i]+" | "
for(j=0;j<lp;j++) {
if(matrice[i][j]!=" ") {
ret +=vnoms[matrice[i][j]]+" "
} else {
ret +="  "
}
}
ret +="\n"
}
ret +="\n"
if(nsolutions<=20) {
ret +=alphanumb[nsolutions]+" solution"+((nsolutions<2)?"":"s")+"\n"
} else {
ret +=nsolutions+" solutions\n"
}
last[current]=ret
var corrige=document.frm.r.checked
lastsolution[current]="\nSolution : \n"+
"----------\n\n\n\n\n\n\n\n"+pcorr+"\n"+vcorr+"\n\n\n\n\n\n\n\n\n\n\n\n"
if(corrige) {
ret +=lastsolution[current]
}
currentpos=current
current++
return ret
}
var last=[]
var lastsolution=[]
var current=0
var currentpos=0
function exple() {
document.frm.a.value=""
stri=sol()
document.frm.a.value=prepare(stri)
}
function chge() {
document.frm.r.checked=!document.frm.r.checked
clique()
}
function clique() {
if(current<=0) return
if(document.frm.r.checked) {
document.frm.a.value=last[current-1]+lastsolution[current-1]
} else {
document.frm.a.value=last[current-1]
}
}
function suivant(n) {
currentpos +=n
document.frm.a.value=""
if(currentpos>=current-1) currentpos=current-1
if(currentpos<0) currentpos=0
if(currentpos>=current) return
if(document.frm.r.checked && last[currentpos]!=null) {
document.frm.a.value=last[currentpos]+lastsolution[currentpos]
} else {
document.frm.a.value=last[currentpos]
}
}
function clearHistory() {
delete(last)
delete(lastsolution)
last=new Array()
last[0]=""
lastsolution=new Array()
lastsolution[0]=""
current=0
currentpos=0
document.frm.a.value=""
}
function nsols(x0,y0, p, v, nv) {
if(nv==0){ 
return 1
}
var total=0
var rgp=[],     
rgv=[]
for(var i=0;i<nv+1;i++) {
rgp[p[2*i]+" "+p[2*i+1]]=i
}
for(var i=0;i<nv;i++) {
rgv[v[2*i]+" "+v[2*i+1]]=i
}
for(var i=0;i<nv;i++) {
var a=x0+v[2*i]
var b=y0+v[2*i+1]
if(rgp[a+" "+b]==null) continue
var p1=[]
var v1=[]
var k=0
for(var j=0;j<nv;j++) {
if(j==i) continue
v1[2*k]=v[2*j]
v1[2*k+1]=v[2*j+1]
k++
}
k=0
for(var j=0;j<nv+1;j++) {
if(p[2*j]==x0 && p[2*j+1]==y0) continue
p1[2*k]=p[2*j]
p1[2*k+1]=p[2*j+1]
k++
}
total +=nsols(a, b, p1, v1, nv-1)
}
return total
}