// Copyright
// Rajko Zschiegner
// Reichenbacher Str. 20
// D-07973 Greiz

var i;

var sudoku = new Array(81);
var read_only = new Array(81);
var s_blocked = new Array(810);
var solutions = new Array();
var source = document.getElementById("rz_sudoku_form");
var num_div = document.getElementById("rz_sudoku_numbers");
var num_img = new Array(10);
var num_img_r = new Array(10);

for (i=1;i<10;i++) {
	num_img[i] = new Image(); num_img[i].src = "buttons/"+i+".png";
	num_img_r[i] = new Image(); num_img_r[i].src = "buttons/"+i+"_r.png";
}
num_img[0] = new Image(); num_img[0].src = "buttons/space.png";
num_img_r[0] = new Image(); num_img_r[0].src = "buttons/space_r.png";

var examples = new Array(10);

examples[1] = [	0,8,2,0,0,6,0,0,0,
				0,0,0,0,8,0,0,0,4,
				0,0,0,9,0,0,0,0,1,
				9,0,0,0,3,0,4,0,0,
				0,7,0,1,0,5,0,6,0,
				0,0,8,0,9,0,0,0,2,
				5,0,0,0,0,8,0,0,0,
				3,0,0,0,2,0,0,0,0,
				0,0,0,5,0,0,7,4,0];
examples[2] = [	0,3,0,0,0,0,0,7,0,
				6,0,0,0,0,0,0,0,3,
				0,0,1,2,0,5,6,0,0,
				0,0,3,4,0,7,8,0,0,
				0,0,0,0,0,0,0,0,0,
				0,0,5,6,0,1,2,0,0,
				0,0,7,8,0,3,4,0,0,
				1,0,0,0,0,0,0,0,6,
				0,5,0,0,0,0,0,1,0];

var last_active=-1;

var num_div_x = new Array(9);
num_div_x = [30,55,80,108,133,158,82,107,132];
var num_div_y = new Array(9);
num_div_y = [30,55,80,108,133,34,62,87,112];

clear_field();
				
function clear_field() {
	for (i=0;i<81;i++) {
		sudoku[i]=0;
	}
	play_back();
}

function init_arrays() {
	var r,c,i;
	
	for (r=0;r<9;r++) {
		for (c=0;c<9;c++) {
			for (i=1;i<10;i++) {
				s_blocked[(r*9+c)*10+i]=1;
			}
		}
	}
}

function play_back() {
	var r,c;
	for (r=0;r<81;r++) {
		document.images[r].src = num_img[sudoku[r]].src;
	}
}

function load_sudoku(n) {
	var i;
	for (i=0;i<81;i++) {
		sudoku[i] = examples[n][i];
	}
	play_back();
	source.rz_sudoku_comment.value='';
	return false;
}

function clear_blocked_r_c(r,c) {
	var i;
	for (i=1;i<10;i++) s_blocked[(r*9+c)*10+i] = 0;
}

function clear_blocked(r,c,n) {
	var i,j;
	for (i=0;i<9;i++) {
		s_blocked[(i*9+c)*10+n] = 0;
		s_blocked[(r*9+i)*10+n] = 0;
	}
	var offset_r = r - (r % 3);
	var offset_c = c - (c % 3);
	for (i=0;i<3;i++) {
		var offset_r_c = (offset_r+i)*9+offset_c;
		for (j=0;j<3;j++) s_blocked[(offset_r_c+j)*10+n]=0;
	}
}

function reset_blocked(r,c,n) {
	var i,j;
	for (i=0;i<9;i++) {
		s_blocked[(i*9+c)*10+n] = 1;
		s_blocked[(r*9+i)*10+n] = 1;
	}
	var offset_r = r - (r % 3);
	var offset_c = c - (c % 3);
	for (i=0;i<3;i++) {
		var offset_r_c = (offset_r+i)*9+offset_c;
		for (j=0;j<3;j++) s_blocked[(offset_r_c+j)*10+n]=1;
	}
}

function can_set(r, c, n) {
	var i,j;
	var not_found = 1;

	for (i=0;(i<9 && not_found);i++) {
		if (sudoku[i*9+c] == n) not_found = 0;
		if (not_found && (sudoku[r*9+i] == n)) not_found = 0;
	}
	
	if (not_found) {
		var offset_r = r - (r % 3);
		var offset_c = c - (c % 3);
		for (i=0;(i<3 && not_found);i++) {
			var offset_r_c = (offset_r+i)*9+offset_c;
			for (j=0;(j<3 && not_found);j++) {
				if (sudoku[offset_r_c+j] == n) not_found = 0;
			}
		}
	}
	return not_found;
}

function only_1_position_possible() {
var r,c,n,i,j,n_sum,n_pos,n_posr,n_posc;
var changed = 0;
// in row
	for (r=0;r<9;r++) {
		for (n=1;n<10;n++){
			n_sum = 0;
			for (c=0;c<9;c++) {
				if ((s_blocked[(r*9+c)*10+n] == 1) && (sudoku[r*9+c] == 0)) {
					n_sum++; n_pos = c;
				}
			}
			if (n_sum == 1) {
				sudoku[r*9+n_pos] = n;
				clear_blocked(r,n_pos,n)
				clear_blocked_r_c(r,n_pos);
				changed = 1;
			}
		}
	}
// in col
	for (c=0;c<9;c++) {
		for (n=1;n<10;n++){
			n_sum = 0;
			for (r=0;r<9;r++) {
				if ((s_blocked[(r*9+c)*10+n] == 1) && (sudoku[r*9+c] == 0)) {
					n_sum++; n_pos = r;
				}
			}
			if (n_sum == 1) {
				sudoku[n_pos*9+c] = n;
				clear_blocked(n_pos,c,n)
				clear_blocked_r_c(n_pos,c);
				changed = 1;
			}
		}
	}
// in  3x3 block
	for (r=0;r<3;r++) {
		for (c=0;c<3;c++) {
			for (n=1;n<10;n++){
				n_sum = 0;
				for (i=0;i<3;i++) {
					for (j=0;j<3;j++) {
						if ((s_blocked[((r*3+i)*9+(c*3+j))*10+n] == 1)  && (sudoku[(r*3+i)*9+(c*3+j)] == 0)){
							n_sum++; n_posr = r*3+i; n_posc = c*3+j;
						}
					}
				}
				if (n_sum == 1) {
					sudoku[n_posr*9+n_posc] = n;
					clear_blocked(n_posr,n_posc,n);
					clear_blocked_r_c(n_posr,n_posc);
					changed = 1;
				}
			}
		}
	}
	return changed;
}

function only_1_number_possible() {
	var r,c,n,num_count,last_num;
	var changed = 0;
	for (r=0;r<9;r++) {
		for (c=0;c<9;c++) {
			num_count = 0;
			for (n=1;n<10;n++) {
				if ((s_blocked[r*90+c*10+n] == 1) && (sudoku[r*9+c] == 0)) {
					num_count++; last_num = n;
				}
			}
			if (num_count == 1) {
				sudoku[r*9+c] = last_num;
				clear_blocked(r,c,last_num);
				clear_blocked_r_c(r,c);
				changed = 1;
			}
		}
	}
	return changed;
}

function only_1_row_or_col_possible_for_n() {
	var n,r,c;
// rows
	for (n=1;n<10;n++) {
		for (r=0;r<3;r++) {
			for (c=0;c<3;c++) {
				if (((s_blocked[r*270+c*30+n]    + s_blocked[r*270+c*30+10+n]  + s_blocked[r*270+c*30+20+n]) > 0) && ((s_blocked[r*270+c*30+90+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+110+n] + s_blocked[r*270+c*30+180+n] + s_blocked[r*270+c*30+190+n] + s_blocked[r*270+c*30+200+n])==0)) {
					if (c != 0) {s_blocked[r*270+00+n]=0;s_blocked[r*270+10+n]=0;s_blocked[r*270+20+n]=0;}
					if (c != 1) {s_blocked[r*270+30+n]=0;s_blocked[r*270+40+n]=0;s_blocked[r*270+50+n]=0;}
					if (c != 2) {s_blocked[r*270+60+n]=0;s_blocked[r*270+70+n]=0;s_blocked[r*270+80+n]=0;}
				} 
				if (((s_blocked[r*270+c*30+90+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+110+n]) > 0) && ((s_blocked[r*270+c*30+n] + s_blocked[r*270+c*30+10+n] + s_blocked[r*270+c*30+20+n] + s_blocked[r*270+c*30+180+n] + s_blocked[r*270+c*30+190+n] + s_blocked[r*270+c*30+200+n])==0)) {
					if (c != 0) {s_blocked[r*270+ 90+n]=0;s_blocked[r*270+100+n]=0;s_blocked[r*270+110+n]=0;}
					if (c != 1) {s_blocked[r*270+120+n]=0;s_blocked[r*270+130+n]=0;s_blocked[r*270+140+n]=0;}
					if (c != 2) {s_blocked[r*270+150+n]=0;s_blocked[r*270+160+n]=0;s_blocked[r*270+170+n]=0;}
				} 
				if (((s_blocked[r*270+c*30+180+n] + s_blocked[r*270+c*30+190+n] + s_blocked[r*270+c*30+200+n]) > 0) && ((s_blocked[r*270+c*30+n] + s_blocked[r*270+c*30+10+n] + s_blocked[r*270+c*30+20+n] + s_blocked[r*270+c*30+90+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+110+n])==0)) {
					if (c != 0) {s_blocked[r*270+180+n]=0;s_blocked[r*270+190+n]=0;s_blocked[r*270+200+n]=0;}
					if (c != 1) {s_blocked[r*270+210+n]=0;s_blocked[r*270+220+n]=0;s_blocked[r*270+230+n]=0;}
					if (c != 2) {s_blocked[r*270+240+n]=0;s_blocked[r*270+250+n]=0;s_blocked[r*270+260+n]=0;}
				}
			}
		}
	}

// cols
	for (n=1;n<10;n++) {
		for (r=0;r<3;r++) {
			for (c=0;c<3;c++) {
				if (((s_blocked[r*270+c*30+n]    + s_blocked[r*270+c*30+90+n]  + s_blocked[r*270+c*30+180+n]) > 0) && ((s_blocked[r*270+c*30+10+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+190+n] + s_blocked[r*270+c*30+20+n] + s_blocked[r*270+c*30+110+n] + s_blocked[r*270+c*30+200+n])==0)) {
					if (r != 0) {s_blocked[ 00+c*30+n]=0;s_blocked[ 90+c*30+n]=0;s_blocked[180+c*30+n]=0;}
					if (r != 1) {s_blocked[270+c*30+n]=0;s_blocked[360+c*30+n]=0;s_blocked[450+c*30+n]=0;}
					if (r != 2) {s_blocked[540+c*30+n]=0;s_blocked[630+c*30+n]=0;s_blocked[720+c*30+n]=0;}
				} 
				if (((s_blocked[r*270+c*30+10+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+190+n]) > 0) && ((s_blocked[r*270+c*30+n] + s_blocked[r*270+c*30+90+n] + s_blocked[r*270+c*30+180+n] + s_blocked[r*270+c*30+20+n] + s_blocked[r*270+c*30+110+n] + s_blocked[r*270+c*30+200+n])==0)) {
					if (r != 0) {s_blocked[ 10+c*30+n]=0;s_blocked[100+c*30+n]=0;s_blocked[190+c*30+n]=0;}
					if (r != 1) {s_blocked[280+c*30+n]=0;s_blocked[370+c*30+n]=0;s_blocked[460+c*30+n]=0;}
					if (r != 2) {s_blocked[550+c*30+n]=0;s_blocked[640+c*30+n]=0;s_blocked[730+c*30+n]=0;}
				} 
				if (((s_blocked[r*270+c*30+20+n] + s_blocked[r*270+c*30+110+n] + s_blocked[r*270+c*30+200+n]) > 0) && ((s_blocked[r*270+c*30+n] + s_blocked[r*270+c*30+90+n] + s_blocked[r*270+c*30+180+n] + s_blocked[r*270+c*30+10+n] + s_blocked[r*270+c*30+100+n] + s_blocked[r*270+c*30+190+n])==0)) {
					if (r != 0) {s_blocked[ 20+c*30+n]=0;s_blocked[110+c*30+n]=0;s_blocked[200+c*30+n]=0;}
					if (r != 1) {s_blocked[290+c*30+n]=0;s_blocked[380+c*30+n]=0;s_blocked[470+c*30+n]=0;}
					if (r != 2) {s_blocked[560+c*30+n]=0;s_blocked[650+c*30+n]=0;s_blocked[740+c*30+n]=0;}
				}
			}
		}
	}

}

function solve(n) {
	var i,j,k,changed;
	var c = n % 9;
	var r = (n-c)/9;
	var blocked_offset = n*10;

//	if (c == 1) source.rz_sudoku_comment.value= n;

	if (n == 81) {
		// solution found
		solutions.push(sudoku);
		play_back();
	} else {
		if (read_only[n] == 1) {
			solve(n+1);
		} else {
			for (i=1;i<10;i++) {
				if (s_blocked[blocked_offset+i] == 1) {
					if (can_set(r,c,i)) {
						clear_blocked(r,c,i);
						sudoku[n] = i;
						solve(n+1);
						reset_blocked(r,c,i);
					}
				}
			}
			sudoku[n]=0;
		}
	}
	
}

function loesung() {
	var changed,sub_changed,r,c;
	init_arrays();

	for (r=0;r<9;r++) {
		for (c=0;c<9;c++) {
			if (sudoku[r*9+c] != 0) {
				clear_blocked(r,c,sudoku[r*9+c]);
				clear_blocked_r_c(r,c);
			}
		}
	}
	
	do {

		sub_changed = 0;

		only_1_row_or_col_possible_for_n();

		do {
			changed = only_1_position_possible();
			if (changed) sub_changed = 1;
		} while (changed);

		do {
			changed = only_1_number_possible();
			if (changed) sub_changed = 1;
		} while (changed);

		play_back();
	
	} while (sub_changed);

	for (r=0;r<9;r++) {
		for (c=0;c<9;c++) {
			if (sudoku[r*9+c] != 0) {
				clear_blocked(r,c,sudoku[r*9+c]);
				read_only[r*9+c]=1;
			} else {
				read_only[r*9+c]=0;
			}
		}
	}
	
	solutions = new Array();
	
	solve(0);

	source.rz_sudoku_comment.value="Solved! ";
	
	return false;
}

function go() {
		source.rz_sudoku_comment.value="Wait...";
		setTimeout("loesung()", 100);
}

function field_click(n) {
	if (last_active != -1) {
		document.images[last_active].src = num_img[sudoku[last_active]].src;
	}	
	last_active = n;
	document.images[n].src = num_img_r[sudoku[n]].src;
	num_div.style.left = num_div_x[n%9]+"px";
	num_div.style.top  = num_div_y[(n-(n%9))/9]+"px";
	num_div.style.visibility = "visible";
	return false;
}
function number_click(n) {
	sudoku[last_active] = n;
	document.images[last_active].src = num_img[sudoku[last_active]].src;
	num_div.style.visibility = "hidden";
	last_active = -1;
	return false;
}