// sudoku engine v2.3
// updated February 1, 2007
// copyright Patrick Lewis (patricklewis.net)

function GenSud () {
trials = 50;
GrAtt = 1;
for (Block=1;Block<11;Block++) {

/////////////////////////////////

	if (Block == 1){
	grid = new Array(9);
	BlAttempts = new Array(0,0,0,0,0,0,0,0,0,0,0);
	for (r=0;r<9;r++) {
		grid[r] = new Array(9);
		}
	Error = "";

	//block 1
	Error += "<br>Block 1 start<br>";
	temp = new Array(1,2,3,4,5,6,7,8,9);
	for (r=0;r<3;r++) {
		for (c=0;c<3;c++) {
			num = Math.floor(Math.random() * 9);
			if (!temp[num]){c--;}
			else {
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		}
	Error += "Block 1 done<br>";
	//alert("1 done");
	BlAttempts[1]++;
	if (BlAttempts[1] > trials) {Error += "Block 1 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 2){
	// block 2
	Error += "<br>Block 2 start<br>";
	for (r=0;r<3;r++) {
		for (c=3;c<6;c++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
			// remove numbers in block to the left same row
			temp[grid[r][0]-1] = "";
			temp[grid[r][1]-1] = "";
			temp[grid[r][2]-1] = "";
			if (c>3) {
				temp[grid[r][3]-1] = "";
				}
			if (c==5) {
				temp[grid[r][4]-1] = "";
				}
			if (r==1) {
				temp[grid[r-1][3]-1] = "";
				temp[grid[r-1][4]-1] = "";
				temp[grid[r-1][5]-1] = "";
				force = new Array(9);
				// force to take what is left in bottom row block to left
				for (b=0;b<3;b++) {
					bl = grid[r+1][b];
					if (temp.toString().indexOf(bl) > -1) {
						force[bl-1] = bl;
						temp[bl-1] = "";
						}
					}
				//Error +="forced "+ force +" : ";
				if (force.toString().match(/\d/g)) {
					temp = force;
					}
				//Error += "temp : "+temp +"<br>";
				}
			if (r==2) {
				temp[grid[r-1][3]-1] = "";
				temp[grid[r-1][4]-1] = "";
				temp[grid[r-1][5]-1] = "";
				temp[grid[r-2][3]-1] = "";
				temp[grid[r-2][4]-1] = "";
				temp[grid[r-2][5]-1] = "";
				}
			if (temp.toString() == ",,,,,,,,") {Error += "2 breaking (commas)<br>"; Block =1; break;}
			if (!temp.toString().match(/\d/)) {Error += "2 breaking (no # match)<br>"; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){c--;}
			else {
				//Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"]<br>";
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		}
	Error += "Block 2 done<br>";
	//alert("2 done");
	BlAttempts[2]++;
	if (BlAttempts[2] > trials) {Error += "Block 2 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 3){
	//block 3
	Error += "<br>Block 3 start<br>";
	for (r=0;r<3;r++) {
	temp = new Array(1,2,3,4,5,6,7,8,9);
		temp[grid[r][0]-1] = "";
		temp[grid[r][1]-1] = "";
		temp[grid[r][2]-1] = "";
		temp[grid[r][3]-1] = "";
		temp[grid[r][4]-1] = "";
		temp[grid[r][5]-1] = "";
		for (c=6;c<9;c++) {
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){c--;}
			else {
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		}
	Error += "Block 3 done<br>";
	//alert("3 done");
	BlAttempts[3]++;
	if (BlAttempts[3] > trials) {Error += "Block 3 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 4){
	// block 4
	Error += "<br>Block 4 start<br>";
	for (c=0;c<3;c++) {
		for (r=3;r<6;r++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
			// remove numbers in above block, same column
			temp[grid[0][c]-1] = "";
			temp[grid[1][c]-1] = "";
			temp[grid[2][c]-1] = "";
			if (c==1) {
				//remove numbers in same block, previous column
				temp[grid[3][c-1]-1] = "";
				temp[grid[4][c-1]-1] = "";
				temp[grid[5][c-1]-1] = "";
				}
			if (c==2) {
				//remove numbers in same block, previous 2 columns
				temp[grid[3][c-1]-1] = "";
				temp[grid[4][c-1]-1] = "";
				temp[grid[5][c-1]-1] = "";
				temp[grid[3][c-2]-1] = "";
				temp[grid[4][c-2]-1] = "";
				temp[grid[5][c-2]-1] = "";
				}
			// remove numbers in same block/column above current row
			if (r>3) {
				temp[grid[r-1][c]-1] = "";
				}
			if (r==5) {
				temp[grid[r-2][c]-1] = "";
				}
			if (temp.toString() == ",,,,,,,,") {Error += "4 breaking (commas)<br>"; Block=3; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){r--;}
			else {
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		}
	Error += "Block 4 done<br>";
	//alert("4 done");
	BlAttempts[4]++;
	if (BlAttempts[4] > trials) {Error += "Block 4 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 5){
	// block 5
	Error += "<br>Block 5 start<br>";
	for (r=3;r<6;r++) {
		for (c=3;c<6;c++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
			// remove numbers in block to the left same row
			temp[grid[r][0]-1] = "";
			temp[grid[r][1]-1] = "";
			temp[grid[r][2]-1] = "";
			if (c>3) {
				temp[grid[r][3]-1] = "";
				}
			if (c==5) {
				temp[grid[r][4]-1] = "";
				}
			if (r==4) {
				temp[grid[r][c-1]-1] = "";
				temp[grid[r-1][3]-1] = "";
				temp[grid[r-1][4]-1] = "";
				temp[grid[r-1][5]-1] = "";
				force = new Array();
				// force to take what is left in bottom row block to left
				for (b=0;b<3;b++) {
					bl = grid[r+1][b];
					if (temp.toString().indexOf(bl) > -1) {
						force[bl-1] = bl;
						temp[bl-1] = "";
						}
					}
				Error +="forced "+ force +" : ";
				if (force.toString().match(/\d/g)) {
					temp = force;
					}
				Error += "temp : "+temp +"<br>";
				}
			if (r==5) {
				temp[grid[r-1][3]-1] = "";
				temp[grid[r-1][4]-1] = "";
				temp[grid[r-1][5]-1] = "";
				temp[grid[r-2][3]-1] = "";
				temp[grid[r-2][4]-1] = "";
				temp[grid[r-2][5]-1] = "";
				temp[grid[r][c-1]-1] = "";
				temp[grid[r][c-2]-1] = "";
				}
			// remove numbers in block above same column
			temp[grid[0][c]-1] = "";
			temp[grid[1][c]-1] = "";
			temp[grid[2][c]-1] = "";
			if (temp.toString() == ",,,,,,,,") {Error += "5 breaking (commas)<br>"; Block = 4; break;}
			if (!temp.toString().match(/\d/)) {Error += "5 breaking (no # match)<br>"; Block = 4; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){c--;}
			else {
				Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"]<br>";
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		if (Block == 4 ) {break;}
		}
	Error += "Block 5 done<br>";
	//alert("5 done");
	BlAttempts[5]++;
	if (BlAttempts[5] > trials) {Error += "Block 5 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 6){
	// block 6
	Error += "<br>Block 6 start<br>";
	for (r=3;r<6;r++) {
		for (c=6;c<9;c++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
			// remove numbers in block to the left same row
			temp[grid[r][0]-1] = "";
			temp[grid[r][1]-1] = "";
			temp[grid[r][2]-1] = "";
			temp[grid[r][3]-1] = "";
			temp[grid[r][4]-1] = "";
			temp[grid[r][5]-1] = "";
			// remove numbers in block above same column
			temp[grid[0][c]-1] = "";
			temp[grid[1][c]-1] = "";
			temp[grid[2][c]-1] = "";
			if (c>6) {
				temp[grid[r][6]-1] = "";
				}
			if (c==8) {
				temp[grid[r][7]-1] = "";
				}
			if (r==4) {
				temp[grid[r][c-1]-1] = "";
				temp[grid[r-1][6]-1] = "";
				temp[grid[r-1][7]-1] = "";
				temp[grid[r-1][8]-1] = "";
				force = new Array();
				// force to take what is left in bottom row block to left
				for (b=3;b<6;b++) {
					bl = grid[r+1][b];
					if (temp.toString().indexOf(bl) > -1) {
						force[bl-1] = bl;
						temp[bl-1] = "";
						}
					}
				Error +="forced "+ force +" : ";
				if (force.toString().match(/\d/g)) {
					temp = force;
					}
				Error += "temp : "+temp +"<br>";
				}
			if (r==5) {
				temp[grid[r-1][6]-1] = "";
				temp[grid[r-1][7]-1] = "";
				temp[grid[r-1][8]-1] = "";
				temp[grid[r-2][6]-1] = "";
				temp[grid[r-2][7]-1] = "";
				temp[grid[r-2][8]-1] = "";
				temp[grid[r][c-1]-1] = "";
				temp[grid[r][c-2]-1] = "";
				Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"] **<br>";
				}
			if (temp.toString() == ",,,,,,,,") {Error += "6 breaking (commas)<br>"; Block = 5; break;}
			if (!temp.toString().match(/\d/)) {Error += "6 breaking (no # match)<br>"; Block = 5; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){c--;}
			else {
				Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"]<br>";
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		//	if (Block == 5 ) {break;}
		}
	Error += "Block 6 done<br>";
	//alert("6 done");
	BlAttempts[6]++;
	if (BlAttempts[6] > trials) {Error += "Block 6 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 7){
	//block 7
	Error += "<br>Block 7 start<br>";
	for (c=0;c<3;c++) {
	temp = new Array(1,2,3,4,5,6,7,8,9);
		temp[grid[0][c]-1] = "";
		temp[grid[1][c]-1] = "";
		temp[grid[2][c]-1] = "";
		temp[grid[3][c]-1] = "";
		temp[grid[4][c]-1] = "";
		temp[grid[5][c]-1] = "";
		for (r=6;r<9;r++) {
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){r--;}
			else {
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		}
	Error += "Block 7 done<br>";
	//alert("7 done");
	BlAttempts[7]++;
	if (BlAttempts[7] > trials) {Error += "Block 7 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 8){
	//block 8
	Error += "<br>Block 8 start<br>";
	for (c=3;c<6;c++) {
		for (r=6;r<9;r++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
			temp[grid[0][c]-1] = "";
			temp[grid[1][c]-1] = "";
			temp[grid[2][c]-1] = "";
			temp[grid[3][c]-1] = "";
			temp[grid[4][c]-1] = "";
			temp[grid[5][c]-1] = "";
		// remove block 7 numbers in this row.
			temp[grid[r][0]-1] = "";
			temp[grid[r][1]-1] = "";
			temp[grid[r][2]-1] = "";
		// remove numbers above in this row.
			if (r>6) {
				temp[grid[r-1][c]-1] = "";
				}
			if (r==8) {
				temp[grid[r-2][c]-1] = "";
				}
			if (temp.toString() == ",,,,,,,,") {Error += "8 breaking (commas)<br>"; Block = 7; break;}
			if (!temp.toString().match(/\d/)) {Error += "8 breaking (no # match)<br>"; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){r--;}
			else {
				Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"]<br>";
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		if (Block == 7 ) {break;}
		}
	Error += "Block 8 done<br>";
	//alert("8 done");
	BlAttempts[8]++;
	if (BlAttempts[8] > trials) {Error += "Block 8 attempted more than "+trials+" times.<br>"; Block=10; }
	}

/////////////////////////////////

	if (Block == 9){
	//block 9
	Error += "<br>Block 9 start<br>";
	for (c=6;c<9;c++) {
		for (r=6;r<9;r++) {
			temp = new Array(1,2,3,4,5,6,7,8,9);
		// remove number in same column
			temp[grid[0][c]-1] = "";
			temp[grid[1][c]-1] = "";
			temp[grid[2][c]-1] = "";
			temp[grid[3][c]-1] = "";
			temp[grid[4][c]-1] = "";
			temp[grid[5][c]-1] = "";
		// remove numbers in sampe row
			temp[grid[r][0]-1] = "";
			temp[grid[r][1]-1] = "";
			temp[grid[r][2]-1] = "";
			temp[grid[r][3]-1] = "";
			temp[grid[r][4]-1] = "";
			temp[grid[r][5]-1] = "";
		// remove numbers in this block
			if (c>6) {
				temp[grid[6][c-1]-1] = "";
				temp[grid[7][c-1]-1] = "";
				temp[grid[8][c-1]-1] = "";
				}
			if (c==8) {
				temp[grid[6][c-2]-1] = "";
				temp[grid[7][c-2]-1] = "";
				temp[grid[8][c-2]-1] = "";
				}
			if (temp.toString() == ",,,,,,,,") {Error += "9 breaking (commas)<br>"; Block = 8; break;}
			if (!temp.toString().match(/\d/)) {Error += "9 breaking (no # match)<br>"; break;}
			num = Math.floor(Math.random() * temp.length);
			if (!temp[num]){r--;}
			else {
				Error += r +","+c+") "+temp +" ["+ num +" - "+ temp[num] +"]<br>";
				grid[r][c] = temp[num];
				temp[num] = "";
				}
			}
		if (Block == 8 ) {break;}
		}
	Error += "Block 9 done<br>";
	//alert("9 done");
	BlAttempts[9]++;
	if (BlAttempts[9] > trials) {Error += "Block 9 attempted more than "+trials+" times.<br>"; Block=10;}
	}

/////////////////////////////////

	if (Block == 10){
		if (grid.toString().indexOf(",,") > -1) {
			// start over
			Block = 0;
			GrAtt ++;
			if (GrAtt == 10) {	alert("Generating random grid");}
			if (GrAtt == 20) {	alert("Still generating grid");}
			if (GrAtt == 30) {	alert("Almost done generating grid");}
			if (GrAtt == 40) {	alert("I promise, I am just about done generating grid");}
			}
		else {
			return grid;
			}
		}
	}
}