// 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;
			}
		}
	}
}