//remove loners/duplicates / cull list needs to be iterative - until progress not made



var sroot=3
var side=sroot * sroot;
var sodu=new Array();
var sogrid=new Array();
var visi=new Array();
var sudoku=new Array();
var nums="123456789";
var avail="123456789"
var cullistx=""
var cullisty=""
var carrot=0
var thisone=" ";
var solvable=0
var grouppos="";
var progress=0;// changed

var yc=0;
var xc=0;
var xname=-1; // name of table x position (column)
var yname=-1; 
var thickx=-1; // count to thick line at sroot
var thicky=0;

var lastx=0
var lasty=0
var delast=0
var givens=0

var setit=0

// +++++++++++++++++++ from make sudoku ++++++++++++++++++++++++++
function makesudoku(){
	nums="123456789";
	avail="123456789";
	cullisty="";
	cullistx="";
	// 1 create centre grid
	for (x=4; x<7; x++){
		for (y=4; y<7; y++){
			carrot=Math.round(Math.random()*(nums.length-1))
			sodu[x+"-"+y]=nums.charAt(carrot)
			nums=nums.replace(nums.charAt(carrot),"")
		}
	}
	
	foldout (4,7,4,7,1)
	// 3 fold the top one out both sides
	foldout (1,4,4,7,0)
	// put available numbers in remaining boxes and then cull, pick at random, etc.
	halffoldout (4,7,4,7)
	halffoldout (7,10,4,7)

	removeduplicates()
	removeloners()
	randomassign()
}

// 2 fold it out to create correct numbers all the way down the centre
function intersect (mainarray,otherone){
	//return intersection of the two strings
	var inter="";
	for (i=0; i<=otherone.length; i++){
		if (mainarray.indexOf(otherone.charAt(i))>=0){
			inter=inter+otherone.charAt(i)
		}
	}
	return inter;
}

function indie (mainarray,otherone){
	// get mainarray without anything from otherone
	var inter=mainarray;
	for (i=0; i<=otherone.length; i++){
		if (mainarray.indexOf(otherone.charAt(i))>=0){
			inter=inter.replace(otherone.charAt(i),"")
		}
	}
	return inter;
}

function foldout(rxmin,rxmax,ymin,ymax,horizontal){
	var rnums=" ";
	var lnums=" ";
	var lastone="";
	for (rx=rxmin; rx<rxmax; rx++){// column we're expanding
		avail="123456789";
		for (y=ymin; y<ymax; y++){ // row
			if (horizontal==1){
			avail=avail.replace(sodu[rx+"-"+y],"")
			}else{
			avail=avail.replace(sodu[y+"-"+rx],"")
			}
		}
		//get anything from rnums first, because numbers from rnums need to be in lnums eventually
		lavailb=indie(avail,lnums)// without the ones we used
		lavail=intersect(lavailb,rnums)// the ones we have no used on this side, but have on the other
		// LEFT / UPPER half
		for (y=1; y<=3; y++){// y can be x coordinate if horizontal=0
			if (lavail.length>0){
				carrot=Math.round(Math.random()*(lavail.length-1))
				thisone=lavail.charAt(carrot)
			}else{
				carrot=Math.round(Math.random()*(lavailb.length-1))
				thisone=lavailb.charAt(carrot)
			}
			if (horizontal==1){
				sodu[rx+"-"+y]=thisone
			}else{
				sodu[y+"-"+rx]=thisone
			}
			lavail=lavail.replace(thisone,"")
			lavailb=lavailb.replace(thisone,"")
			avail=avail.replace(thisone,"")
			lnums=lnums+thisone
		}
		
		// RIGHT / LOWERr half
		//intersect / inter - not necessary - there are only three numbers left!
		for (y=7; y<=9; y++){
			carrot=Math.round(Math.random()*(avail.length-1))
			thisone=avail.charAt(carrot)
			if (horizontal==1){
				sodu[rx+"-"+y]=thisone
			}else{
				sodu[y+"-"+rx]=thisone
			}
			avail=avail.replace(thisone,"")
			rnums=rnums+thisone
		}
	}
}

function halffoldout(rxmin,rxmax,ymin,ymax){
// shows all options
	for (rx=rxmin; rx<rxmax; rx++){// column we're expanding
		avail="123456789";
		for (y=ymin; y<ymax; y++){ // row
			
			avail=avail.replace(sodu[y+"-"+rx],"")
			
		}
		for (y=1; y<=3; y++){
		sodu[y+"-"+rx]=avail
		}
		for (y=7; y<=9; y++){
		sodu[y+"-"+rx]=avail
		}
	}
}



function cull(xpos,ypos){
	
	var victim=sodu[xpos+"-"+ypos]
	var lowestx=0
	var lowesty=0
	var highesty=0
	var highestx=0
	var charc="";
	var group=0
	for (cy=1; cy<=side; cy++){
		if (cy!=ypos & sodu[xpos+"-"+cy].length>1){
			sodu[xpos+"-"+cy]=sodu[xpos+"-"+cy].replace(victim,"")
			if (sodu[xpos+"-"+cy].length==1){
				cullistx=cullistx+xpos
				cullisty=cullisty+cy
				if (visi[xpos+"-"+cy]!=1){
						visi[xpos+"-"+cy]=2					
				}
			}
		}
	}
	for (cx=1; cx<=side; cx++){
		if (cx!=xpos & sodu[cx+"-"+ypos].length>1){
			sodu[cx+"-"+ypos]=sodu[cx+"-"+ypos].replace(victim,"")
			if (sodu[cx+"-"+ypos].length==1){
				cullistx=cullistx+cx
				cullisty=cullisty+ypos
				if (visi[cx+"-"+ypos]!=1){
						visi[cx+"-"+ypos]=2					
				}
			}
		}
	}

	group=Math.round(((xpos-1)/sroot)-0.5)
	lowestx=sroot*group+1;
	highestx=lowestx+2;
	group=Math.round(((ypos-1)/sroot)-0.5)
	lowesty=sroot*group+1;
	highesty=lowesty+2;
	for (cy=lowesty; cy<=highesty; cy++){
		for (cx=lowestx; cx<=highestx; cx++){
			charc="+"+sodu[cx+"-"+cy];
			if (cx==xpos & cy==ypos){
				//document.write("on small square")
			}else if (charc.length>2){
				sodu[cx+"-"+cy]=charc.replace(victim,"")
				sodu[cx+"-"+cy]=sodu[cx+"-"+cy].replace("+","")
				if (sodu[cx+"-"+cy].length==1){
					if (visi[cx+"-"+cy]!=1){
						visi[cx+"-"+cy]=2					
					}
					progress=1;// changed 
					cullistx=cullistx+cx
					cullisty=cullisty+cy
				}
			}else if (charc.length==2 & charc.indexOf(victim)>=0){
				if(setit==0){
					makesudoku()
				}
			}
		}
	}
}

function removeduplicates(){
// from a position of some unique numbers, and some strings of numbers, remove all the duplicates where single numbers repeated in groups of possibilities
	for (yd=1; yd<=side; yd++){
		for (xd=1; xd<=side; xd++){
			sodu[xd+"-"+yd]="+"+sodu[xd+"-"+yd]
			sodu[xd+"-"+yd]=sodu[xd+"-"+yd].replace("+","")
			if (sodu[xd+"-"+yd].length==1){

				cull(xd,yd)
			}
		}
	}
}

function removeloners(){
	//if we have, on a line, something like 1239 456 78 1234 5678 2781634 1238 182376 134, then the 9 must be in the first group because its the only one
	var xcount=0
	var ycount=0
	var gcount=new Array();
	var lastoneg=new Array();
	var lasto=""
	var dex=0
	var arcel=""
	var xco=0
	var yco=0
	var xm=0;
	var ym=0;
	for (n=1; n<=side; n++){
		
		for (ym=1; ym<=side; ym++){	
			xcount=0;
			ycount=0;
			for (xm=1; xm<=side; xm++){
				arcel="@"+sodu[xm+"-"+ym];
				dex=arcel.indexOf(n);
				//document.write("<br>"+n+" in "+arcel+"occurs at "+dex)
				if(dex>=0){
					xcount++;
					lastonex=xm+"-"+ym;
					//document.write("found")
				}
				arcel="@"+sodu[ym+"-"+xm];
				dex=arcel.indexOf(n)
				if(dex>=0){
					ycount++;
					lastoney=ym+"-"+xm;
				}	
			}
			//document.write(xcount+" occurences of "+n+"<br>")
			if (xcount==1){	
				if (sodu[lastonex].length>1){
					sodu[lastonex]=n
					cull(lastonex.charAt(0),lastonex.charAt(2))
					grouppos=lastonex.charAt(0)+"-"+lastonex.charAt(2)
					visi[lastonex.charAt(0)+"-"+lastonex.charAt(2)]=2
					progress=2;// changed 
				}
			}
			if (ycount==1){
			
				if (sodu[lastoney].length>1){
					sodu[lastoney]=n
					cull(lastoney.charAt(0),lastoney.charAt(2))
					grouppos=lastoney.charAt(0)+"-"+lastoney.charAt(2)
					visi[lastoney.charAt(0)+"-"+lastoney.charAt(2)]=2
					progress=3;// changed 
				}
			}

		}
				
		// ++++++++++ now look in GROUPs ++++++++++++++++
		for (gcy=0; gcy<sroot; gcy++) {
			for (gcx=0; gcx<sroot; gcx++) {
				gname=gcx+"-"+gcy
				gcount[gname]=0
				for (xm=1; xm<=sroot; xm++){
					for (ym=1; ym<=sroot; ym++){
						xco=3*gcx+xm
						yco=3*gcy+ym
						arcel="@"+sodu[xco+"-"+yco];
						dex=arcel.indexOf(n);
						if(dex>=0){
							gcount[gname]++;
							lastoneg[gname]=xco+"-"+yco;	
						}
					}
				}
			}
		}
		
		for (gcy=0; gcy<=sroot; gcy++) {
			for (gcx=0; gcx<=sroot; gcx++) {
				lasto=lastoneg[gcx+"-"+gcy]
				if (gcount[gcx+"-"+gcy]==1){
					if (sodu[lasto].length>1){
						sodu[lasto]=n
						grouppos=lasto.charAt(0)+"-"+lasto.charAt(2)
						visi[lasto.charAt(0)+"-"+lasto.charAt(2)]=2
						cull(lasto.charAt(0),lasto.charAt(2))
						progress=4;// changed 
					}
				}
			}
		}
		
		// +++++++++++++++ group done ++++++++++++++++
	}
}


function randomassign(){
// from a position of some unique numbers, and some strings of numbers, remove all the duplicates where single numbers repeated in groups of possibilities
	for (y=1; y<=side; y++){
		for (x=1; x<=side; x++){
			if (sodu[x+"-"+y].length>1){

				sodu[x+"-"+y]=sodu[x+"-"+y].charAt(1)// +++++++ make it RANDOM later ++++++++++++++
				cull(x,y)
				sortcullist()
				removeloners()
			}
		}
		//showit()
	}
}



function sortcullist(){
	while (cullistx.length>0){
		progress=5;// changed 
		cull(cullistx.charAt(0),cullisty.charAt(0))
		cullistx=cullistx.substr(1)
		cullisty=cullisty.substr(1)
		visi[cullistx+"-"+cullisty]=2
	}
}

function addnewknown(){
	var xa=20
	var xb=20
	xa=Math.round(Math.random()*10)
	xb=Math.round(Math.random()*10)
	if (visi[xa+"-"+xb]==0 & visi[(10-xa)+"-"+(10-xb)]==0){
		visi[xa+"-"+xb]=1
		//visi[xb+"-"+xa]=1
		visi[(10-xb)+"-"+(10-xa)]=1
		//visi[(10-xa)+"-"+(10-xb)]=1
	}
}


function alignsodu(){
	solvable=1
	var failcount=0;
	var lastfailurex=""
	var lastfailurey=""
	var bestholecount=0;
	for (jx=1; jx<=side; jx++){
			for (jy=1; jy<=side; jy++){
				if (visi[jx+"-"+jy]==1 || visi[jx+"-"+jy]==2){
					sodu[jx+"-"+jy]=sudoku[jx+"-"+jy]
				}else{
					solvable=0
					sodu[jx+"-"+jy]="123456789"
					lastfailurex=lastfailurex+jx
					lastfailurey=lastfailurey+jy
					failcount++;
				}
			}
	}

	var xalist=""
		var xblist=""
		for (l=0; l<lastfailurex.length; l++){
		var holecount=0;
		
			for (n=0; n<lastfailurex.length; n++){
				// ie 3,4 has matches with 4,3 , 7,6 and 6,7
				if (lastfailurex.charAt(n)==lastfailurey[l] && lastfailurey[n]==lastfailurex[l]){
					holecount++;
				}
				//if (lastfailurex[n]==(10-lastfailurey[l]) && lastfailurey[n]==(10-lastfailurex[l])){
				//	holecount++;
				//}
				//if (lastfailurex[n]==(10-lastfailurex[l]) && lastfailurey[n]==(10-lastfailurey[l])){
				//	holecount++;
				//}
			}

			if (holecount>bestholecount){
				var xa=lastfailurex.charAt(l)
				var xb=lastfailurey.charAt(l)
				bestholecount=holecount;
			}else if (holecount==bestholecount){
				xalist=xalist+lastfailurex.charAt(l)
				xblist=xblist+lastfailurey.charAt(l)
				bestholecount=holecount;
			}
		}

		if  (xalist.length>0){//  choose a good one at random
			var randomsquare=Math.round(Math.random()*xalist.length)
			var xa=xalist.charAt(randomsquare)
			var xb=xblist.charAt(randomsquare)
		}else if (bestholecount==0 & solvable==0){	
			var randomsquare=Math.round(Math.random()*lastfailurex.length)
			var xa=lastfailurex.charAt(randomsquare)
			var xb=lastfailurey.charAt(randomsquare)
		}
		visi[xa+"-"+xb]=1
		//visi[xb+"-"+xa]=1
		//visi[(10-xb)+"-"+(10-xa)]=1
		//visi[(10-xa)+"-"+(10-xb)]=1
		sodu[xa+"-"+xb]=sudoku[xa+"-"+xb]
		//sodu[xb+"-"+xa]=sudoku[xb+"-"+xa]
		//sodu[(10-xb)+"-"+(10-xa)]=sudoku[(10-xb)+"-"+(10-xa)]
		//sodu[(10-xa)+"-"+(10-xb)]=sudoku[(10-xa)+"-"+(10-xb)]
}

function calcvisible(){
	var jx=0
	var jy=0
	for (jx=1; jx<=side; jx++){
		for (jy=1; jy<=side; jy++){
			visi[jx+"-"+jy]=0
		}
	}
	for (n=1; n<2; n++){
		addnewknown()
	}
	while (solvable==0){
		alignsodu()
		removeduplicates()
		sortcullist()
		removeloners()
	}
}

function replicatesodu(){
	for (jx=1; jx<=side; jx++){
		for (jy=1; jy<=side; jy++){
			sudoku[jx+"-"+jy]=sodu[jx+"-"+jy]
		}
	}
}

function showpuzzle(){
	var jx=0
	var jy=0
	document.write("<table>")
	for (jy=1; jy<=side; jy++){
		document.write("<tr>")
		for (jx=1; jx<=side; jx++){
			document.write("<td>")
			
				document.write(sodu[jx+"-"+jy])
			
			document.write("</td>")
		}
		document.write("</tr>")
	}
	document.write("</table>")
}

function showvisi(){
	var jx=0
	var jy=0
	document.write("<table>")
	for (jy=1; jy<=side; jy++){
		document.write("<tr>")
		for (jx=1; jx<=side; jx++){
			document.write("<td>")
			
			document.write(visi[jx+"-"+jy])
			
			document.write("</td>")
		}
		document.write("</tr>")
	}
	document.write("</table>")
}

function cellcorrect(number){
// make allowance for table references starting at zero and having extra cells
	if (number<4){
		number=number-1;
	}else if (number>6){
		number++;
	}
	return number;
}


function placejigsaw(){
	

}

function solve(){
	var gy=0;
	var gx=0;
	var hinted=0;
	var charof=""
	for (sy=1; sy<=side; sy++){
		if (sy==4 || sy==7){
			gy++;
		}
		gx=0;
		for (sx=1; sx<=side; sx++){
			if (sx==4 || sx==7){
				gx++;
		}

			if (sogrid[gx+"-"+gy]>0){
				sodu[sx+"-"+sy]=sogrid[gx+"-"+gy]

				//if (sodu[sx+"-"+sy] != sudoku[sx+"-"+sy]){
				//	colour="rgb(255, 00, 00)";
				//	document.getElementById("c"+gx+"-"+gy).style.background=colour;
				//	hinted=1;
				//}
			}else{
				sodu[sx+"-"+sy]="123456789"

			}
			gx++;		
		}

		gy++;
	}
	// make sodu representative of the grid as displayed (from sogrid - minus gaps for dark lines)
	progress=1 // changed
	while (progress>0){
		progress=0;
		//showpuzzle()
		removeduplicates()		
		sortcullist();
		removeloners()
		placejigsaw();
		//showpuzzle()
		//document.write("<br>Progress-"+progress+"-")
	}
	//document.write("<br>done with loop - should be finished")
	
	// and show what we're thinking of
	
	gy=0;
	for (sy=1; sy<=side; sy++){
		if (sy==4 || sy==7){
			gy++;
		}
		gx=0;
		for (sx=1; sx<=side; sx++){
			if (sx==4 || sx==7){
				gx++;
			}
			//document.write ("<br>out of if shownumber sodu["+sx+"-"+sy+"]("+sodu[sx+"-"+sy]+"),"+gx+","+gy)
			charof=sodu[sx+"-"+sy]+" ";
			if (charof.length==2){
				//sodu[sx+"-"+sy]=sogrid[gx+"-"+gy]
				shownumber(sodu[sx+"-"+sy],gx,gy)
				//document.write ("shownumber sodu["+sx+"-"+sy+"]("+sodu[sx+"-"+sy]+"),"+gx+","+gy)
				//if (sodu[sx+"-"+sy] != sudoku[sx+"-"+sy]){
				//	colour="rgb(255, 00, 00)";
				//	document.getElementById("c"+gx+"-"+gy).style.background=colour;
				//	hinted=1;
				//}
			}
			gx++;		
		}

		gy++;
	}

}
//makesudoku();
//replicatesodu();
//calcvisible();
setit=1

// +++++++++++++++++++++++ end of make sudoku +++++++++++++++++++++++++
function checkdone(){
	// are we there yet?
	var failed=0;
	var gx=0;
	var gy=0
	for (sy=1; sy<=side; sy++){
		if (sy==4 || sy==7){
			gy++;
		}
		gx=0;
		for (sx=1; sx<=side; sx++){
			if (sx==4 || sx==7){
				gx++;
			}
			if (sogrid[gx+"-"+gy]!=sudoku[sx+"-"+sy]){
				failed=1;
			}
			gx++;
		}	
		gy++;
	}
	gx=0;
	gy=0;
	if (failed==0){

		for (sy=1; sy<=side; sy++){
			if (sy==4 || sy==7){
				gy++;
			}
			gx=0;
			for (sx=1; sx<=side; sx++){
				if (sx==4 || sx==7){
					gx++;
				}
				// make each cell green
				document.getElementById("c"+gx+"-"+gy).style.background="#339933";
				gx++;
			}	
			gy++;
		}
	}
}


function checkothers(celno,rowno,colour){
	//highlight in colour, any duplicate numbers
	for (y=0; y<=yname; y++){
		if (sogrid[celno+"-"+y]==sogrid[celno+"-"+rowno] & y!=rowno){
			document.getElementById("c"+celno+"-"+rowno).style.background=colour;
			document.getElementById("c"+celno+"-"+y).style.background=colour;
		}
		
	}
	for (x=0; x<=xname; x++){ 
		if ((sogrid[x+"-"+rowno]==sogrid[celno+"-"+rowno]) & x!=celno){
			document.getElementById("c"+celno+"-"+rowno).style.background=colour;
			document.getElementById("c"+x+"-"+rowno).style.background=colour;
		}
	}
	//work out y in pos, y out pos, x in pos, x out pos for the block this one fits in
	var group=(Math.round((celno/(sroot+1))-0.5))
	lowestx=sroot*group+Math.round(group/sroot);
	highestx=lowestx+sroot;
	group=Math.round(((rowno)/(sroot+1))-0.5)
	lowesty=sroot*group+Math.round(group/sroot);
	highesty=lowesty+sroot;
	for (y=lowesty; y<=highesty; y++){
		for (x=lowestx; x<=highestx; x++){ 
			if ((sogrid[x+"-"+y]==sogrid[celno+"-"+rowno]) & (x!=celno) & (y!=rowno)){
				document.getElementById("c"+celno+"-"+rowno).style.background=colour;
				document.getElementById("c"+x+"-"+y).style.background=colour;
			}
		}
	}
	
}

function shownumber(toshow,celno,rowno){
	newout="<a href='javascript:enterdata(" + celno + "," + rowno + ")'><img src="+pics[toshow]+" name="+celno+"-"+rowno+" id="+celno+"-"+rowno+" border=0  width=56 height=56></a>";
	var v=document.getElementById('mainTable').rows[rowno].cells
	v[celno].innerHTML=newout
	sogrid[celno+"-"+rowno]=toshow;
	//checkothers(celno,rowno,'#FF0000');
	//checkdone();
	lastx=0;
	lasty=0;
	delast=0;
}



function enterdata(celno,rowno){
	var bg=document.getElementById("c"+celno+"-"+rowno).style.backgroundColor;
	if (bg=='rgb(255, 0, 0)'){
		document.getElementById("c"+celno+"-"+rowno).style.background='#CCCCCC';
		checkothers(celno,rowno,'#CCCCCC')
	}else{
	document.getElementById("c"+celno+"-"+rowno).style.background='#CCCCCC';
	}
	sogrid[celno+"-"+rowno]='';
	newout='<table cellpadding=0 cellspacing=0 border=0>';
	n=1;
	for (y=1; y<=sroot; y++){
		newout=newout + '<tr>';
		for (x=1; x<=sroot; x++){
			newout=newout + "<td><a href='javascript:shownumber("+n+","+celno+","+rowno+")'><img src='"+pics[n]+"' width=20 height=20 border=0></a></td>";
			n++;
		}
		newout=newout + '</tr>';
	}
	newout=newout + '</table>';
	var v=document.getElementById('mainTable').rows[rowno].cells
	v[celno].innerHTML=newout
	revert(lastx,lasty)
	delast=1
	lastx=celno
	lasty=rowno
	
}

function revert (celno,rowno){
	if (delast>0){
		newout="<img src='shim.gif' width=60 height=60 onMouseOver=\"enterdata(" + celno + "," + rowno + ")\" >";
		var v=document.getElementById('mainTable').rows[rowno].cells
		v[celno].innerHTML=newout
	}		
}


// now output the grid, with pictures

document.write("<table bgcolor='#999999' name='mainTable' id='mainTable' cellspacing=1 cellpadding=1>");
colspan=side+sroot-1;
for (y=1; y<=side; y++){
	thickx=-1;
	xname=-1;
	if (thicky>=sroot){
		document.write("<tr bgcolor='#000000'><td colspan="+colspan+"><img src=shim.gif width=1 height=1></td></tr>");
		yname++;
		thicky=0;
	}
	yname++;
	thicky++;
	document.write("<tr>");
	for (x=1; x<=side; x++){
		xname++;
		thickx++;
		if (thickx>=sroot){
			document.write("<td bgcolor='#000000'><img src=shim.gif width=1 height=1></td>");
			xname++;
			thickx=0;
		}
		spoint=x + "-" + y;	
		document.write("<td bgcolor='#CCCCCC' name=c"+xname+"-"+yname+" id=c"+xname+"-"+yname+"  valign=\"middle\" align=\"center\">");
		document.write("<img src='shim.gif' width=60 height=60 name="+xname+"-"+yname+" id="+xname+"-"+yname+" onMouseOver=\"enterdata(" + xname + "," + yname + ")\" >");
		
		document.write("</td>");
		
	}
	document.write("</tr>");
}
document.write("<tr><td colspan=6><font face ='arial' size='1'>"+givens+" squares shown to start.</font></td><td align='right' colspan=5><input type='button' name='c' value='Solve' onclick='javascript:solve()'></td></tr>");