
/**
 * This is a program to solve sudoku puzzles, showing the effects of different strategies.
 *
 * @author chenowet.
 *         Created Aug 3, 2006.
 */


public class sudoku {

	private int [][] board = new int [9][9]; // the Sudoku game board
	private int [][] squareRating = new int [9][9]; // rating as to what to try first, next, etc.
	private int [] board_order = new int [81]; // order in which to go after filling squares
	private int [] board_rating = new int [81]; // ratings to go with this assignment
	private int final_used = 0; // last entry number in above tables
	private int initial_choices = 0; // how many choices initially, in all the individual squares
	private double initial_choices_product = 1; // their product, as a measure of complexity
	private int [][] board_order_refs = new int [9][9]; // refs from board to board_rating tbl
	private int [] board_order_backup = new int [81]; // to save prior version when creating new one
	private boolean prettySmartFlag = false; // do pretty smart choice at each deptFirst call.
	private boolean lookAheadSmartFlag = false; // look head a few moves to decide next move.
	private int lookAheadFreq = 30; // how often to do look-ahead switch
	private int lookAheadCount = 0;
	private boolean reallySmartFlag = false; // do a really smart choice at each depthFirst call.
	private boolean smarterRows = false; // to do smart search among row or column choices, etc.
	private boolean smarterCols = false; 
	private long cycles = 0; // how many times we called the recursive depth first search
	private int backtracks = 0; // & how many times we backtracked within that search
	private static long startTime; // to keep track of program execution time
	//private boolean solved = false; // keep track of overall solution status
	private int maxBop = 0; // debug -- what's the farthest we've gotten in solving this one?
	private int minBop = 81; // and least far, recently (last million cycles!)

	private boolean order1XOnly = true; // which methods to try -- in constructor, below (explained there)
	private boolean orderEachX = false;
	private boolean orderAndPick = false;
	private boolean lookAhead = true;
	private boolean orderRowByRow = false;
	private boolean orderRowByRowWOrdering = false;
	private boolean orderColByCol = false;
	private boolean orderColByColWOrdering = false;  // this one doesn't converge on puzzle # 6 !
	private boolean order3SqBy3Sq = false;
	private boolean orderDown3Cols = false;
	
	/**
	 * TODO Put here a description of what this constructor does.
	 *
	 */

	// Constructor -- build & do puzzle 5 different ways
	public sudoku() {
		boardToUse myBoard = new boardToUse();
//		int i=19;
		for (int i=1; i<=myBoard.boardsToTest() ; i++){
//		for (int i=11; i<12 ; i++){
			System.out.println("Now doing puzzle number "+i);
			
			// Solve it depending on the above flags that are set:
			// One choice - try solving it a supposedly smart way, which was ordering just once, by most constrained move first:
			if (this.order1XOnly){
				this.board = myBoard.loadIt(i);  // load the board from data, above
		 		this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this a supposedly 'smart' way, with most constrained first (ordered just once):");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.clearBoardOrder();
		 		this.setBoardOrder(-1); // decide order of trying to fill-in squares, starting at the beginning
		 		//this.scrambleBoardOrder(2); // As a test, to see what happens if we pick a less desirable ordering
		 		this.printBoardOrder(); // show the order we're using here
				System.out.println("We have "+this.final_used+" squares to find values for.");
		 		this.reallySmartFlag = false; // turn off all the special flags for this search
		 		this.prettySmartFlag = false;
		 		this.lookAheadSmartFlag = false;
		 		this.smarterRows = false;
		 		this.smarterCols = false;
		 		this.doThePuzzle(true); // do common routine and print the results

		 		System.out.println("------------------------");
				
			}
	 		
	 		// Another strategy - solving it an actually smart way, deciding what's most constrained before each move:
	 		if (this.orderEachX){
				this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like solved, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this the Pretty smart way, deciding most constrained before each move:");
		 		//this.printIt(); // show user what it looks like, a row at a time

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.clearBoardOrder();
		 		this.setBoardOrder(-1); // decide order of trying to fill-in squares, starting at the beginning
		 		//this.printBoardOrder(); // show the order we're using here
		 		//this.printBoardOrderRefs();
		 		this.reallySmartFlag = false; // do a really smart choice at each depthFirst call.
		 		this.lookAheadSmartFlag = false;
		 		this.smarterRows = false; // to do smart search among row or column choices, etc.
		 		this.smarterCols = false;
		 		this.prettySmartFlag = true; // organize the nodes every time, for most constrained first
		 		this.doThePuzzle(false); // do common routine and don't print the results
				
		 		System.out.println("------------------------");
	 			
	 		}
	 		
	 		// Another alternative -  solving it by looking ahead to decide what's most constrained before each move:
	 		if (this.lookAhead ){
				this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like solved, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this the Pretty smart way, deciding most constrained before each move:");
		 		//this.printIt(); // show user what it looks like, a row at a time

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.clearBoardOrder();
		 		this.setBoardOrder(-1); // decide order of trying to fill-in squares, starting at the beginning
		 		//this.printBoardOrder(); // show the order we're using here
		 		//this.printBoardOrderRefs();
		 		this.reallySmartFlag = false; // do a really smart choice at each depthFirst call.
		 		this.lookAheadSmartFlag = true;
		 		this.smarterRows = false; // to do smart search among row or column choices, etc.
		 		this.smarterCols = false;
		 		this.prettySmartFlag = false; // organize the nodes every time, for most constrained firs
		 		this.lookAheadCount = 0;
		 		this.doThePuzzle(false); // do common routine and don't print the results
				
		 		System.out.println("------------------------");
	 			
	 		}

	 		// Try solving it by deciding what's most constrained before each move, and then
	 		// picking one of the top choices that's also related to the one we just did, like in same row, etc.:
	 		if (this.orderAndPick){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like solved, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this the REALLY smart way, deciding most constrained & 'related' before each move:");
		 		//this.printIt(); // show user what it looks like, a row at a time

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.clearBoardOrder();
		 		this.setBoardOrder(-1); // decide order of trying to fill-in squares, starting at the beginning
		 		this.printBoardOrder(); // show the order we're using here
		 		//this.printBoardOrderRefs();
		 		this.reallySmartFlag = true; // organize every time & pick a close one
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false;
		 		this.smarterCols = false;
		 		this.doThePuzzle(false); // do common routine and don't print the results
				
		 		System.out.println("------------------------");
	
	 		}

	 		// Try solving it in some supposedly stupid ways, a few of which really aren't so stupid -- First, row-by-row:
	 		if (this.orderRowByRow){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this a stupider way, row by row:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false; // including smartening up this search method (done as next alternative, below)
		 		this.smarterCols = false;
		 		this.setBoardOrderOrig(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);
				
		 		System.out.println("------------------------");
	
	 		}

	 		// Slight alternative, row-by-row but picking most constrained within the row next:
	 		if (this.orderRowByRowWOrdering){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this row by row, but best choice within that:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = true; // try slightly smarter version
		 		this.smarterCols = false;
		 		this.clearBoardOrder();
		 		this.SetBoardRowsSmartly(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);

		 		System.out.println("------------------------");
	 			
	 		}

	 		// Next, try it column-by-column, to see if that gives the same exact amount of backtracking, or not:
	 		if (this.orderColByCol){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this another stupider way, column by column:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false; // just the basic version here
		 		this.smarterCols = false;
		 		this.clearBoardOrder();
				this.setBoardOrderByCol(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);

				System.out.println("------------------------");
	
	 		}

	 		// Slight var on column-by-column, with reordering within the column:
	 		if (this.orderColByColWOrdering){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying column by column, but best choice within that:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false; // just the basic version here
		 		this.smarterCols = true;
		 		this.clearBoardOrder();
		 		this.SetBoardColsSmartly(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);

				System.out.println("------------------------");
	
	 		}

	 		// Now try it by solving each 3x3 square, in turn (or trying to):
			if (this.order3SqBy3Sq){
		 		this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this a third stupider way, by 3x3 square:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false; // just the basic version here
		 		this.smarterCols = false;
		 		this.clearBoardOrder();
				this.setBoardOrderBySquare(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);

				System.out.println("------------------------");
				
			}
			// Finally, for variety, try it by solving 3 rows at a time, across each row, then down all the way:
			if (this.orderDown3Cols){
				this.board = myBoard.loadIt(i);  // load the board from data, above
		 		//this.printIt(); // show user what it looks like, a row at a time
		 		System.out.println();
		 		System.out.println("Trying this a fourth stupider way, by 3 across, then down:");

		 		sudoku.startTime = System.currentTimeMillis();
		 		this.reallySmartFlag = false; // make sure all the high-powered stuff is off
		 		this.lookAheadSmartFlag = false;
		 		this.prettySmartFlag = false;
		 		this.smarterRows = false; // just the basic version here
		 		this.smarterCols = false;
		 		this.clearBoardOrder();
				this.setBoardOrderByThrees(); // default to sequential order of trying to fill-in squares
		 		//this.printBoardOrder(); // show the order we're using here
		 		this.doThePuzzle(false);

				System.out.println("------------------------------------------------------------");
				
			}
		} // end for
	} // end sudoku constructor
	
// Common routine to do either smart or stupid searches:
	private void doThePuzzle(boolean printResults){
 		this.cycles = 0;
 		this.maxBop = 0; // debug values to test for, on long runs
 		this.minBop = 81;
 		this.backtracks = 0;
 		//this.solved = false;
		if (this.depthFirst(0)){ // try the search - it worked, because it returns true
 			System.out.println("Success!");
 			if (printResults){
 	 			this.printIt(); 
 			}
		} else { // failed
			System.out.println("Failure! -- last status was");
			this.printIt(); // show what we got, at least
		}
		System.out.println("Called depth first search recursively "+this.cycles+" times,");
		System.out.println(" with "+this.backtracks+" backtracks,");
		long endTime = System.currentTimeMillis();
		System.out.println("And we used "+ (endTime - sudoku.startTime) +" ms.");
	} // end doThePuzzle
	

	// print either the starting configuration or the answer
	private void printIt(){
		System.out.println("The board is:");
		int j=0;
		int k=0;
		for (k=0; k<9; k++){
			for (j=0; j<9; j++){
				if (this.board[j][k]==0){ // show a space instead of a zero
					System.out.print(" "+"_");
				} else if (this.board[j][k] <  10){
					System.out.print(" "+this.board[j][k]);
				} else { // this one needs 10 subtracted, because it's one of ours
					System.out.print(" "+(this.board[j][k] - 10));
				}
			}
			System.out.println();
		}
	} // end printIt
	
	// Rate all the squares for constraints (choices disallowed), creating a grid of these values matching board.
	private void rateSquares(){
		for (int j=0; j<9; j++){
			this.rateARow(j);
		}
	}

	// Find best next square to explore in a row, in smart row strategy
	private void SetBoardRowsSmartly(){
		this.setBoardOrderOrig();
		this.SetNextThingInRow(0);
	}

	// Similarly for columns
	private void SetBoardColsSmartly(){
		this.setBoardOrderByCol();
		this.SetNextThingInCol(0);
	}

	// order the next choice within a row (derived from bop)
	private void SetNextThingInRow(int bop){
		int currentSquare = this.board_order[bop]; // where to start checking first row
		int currentRow = currentSquare / 9;
		this.rateARow(currentRow); //figure out best starting order
		//this.printTemp();
		int currentBestSquare = currentSquare; // starting best square
		int currentBestRating = this.squareRating[currentSquare % 9][currentRow]; // starting value
		//System.out.println("Initial rating is "+currentBestRating);
		int poss_bop = bop+1; // place marker in board_order
		int nextSquare = this.board_order[poss_bop]; // get next square, to compare
		while (nextSquare / 9 == currentRow){ // still looking at first row
			//System.out.println("nextSquare = "+nextSquare+", currentBestRating = "+currentBestRating);
			if (this.squareRating[nextSquare % 9][currentRow] > currentBestRating){ // swap these two
				this.board_order[bop] = nextSquare;
				currentBestRating = this.squareRating[nextSquare % 9][currentRow];
				this.board_order[poss_bop] = currentBestSquare;
				currentBestSquare = nextSquare;
			}
			poss_bop++;
			nextSquare = this.board_order[poss_bop];
		}
	}
	
	// order the next choice within a col (derived from bop)
	private void SetNextThingInCol(int bop){
		int currentSquare = this.board_order[bop]; // where to start checking first row
		int currentCol = currentSquare % 9;
		this.rateACol(currentCol); //figure out best starting order
		//this.printTemp();
		int currentBestSquare = currentSquare; // starting best square
		int currentBestRating = this.squareRating[currentCol][currentSquare / 9]; // starting value
		//System.out.println("Initial rating is "+currentBestRating);
		int poss_bop = bop+1; // place marker in board_order
		int nextSquare = this.board_order[poss_bop]; // get next square, to compare
		while (nextSquare % 9 == currentCol){ // still looking at first row
			//System.out.println("nextSquare = "+nextSquare+", currentBestRating = "+currentBestRating);
			if (this.squareRating[currentCol][nextSquare / 9] > currentBestRating){ // swap these two
				this.board_order[bop] = nextSquare;
				currentBestRating = this.squareRating[currentCol][nextSquare / 9];
				this.board_order[poss_bop] = currentBestSquare;
				currentBestSquare = nextSquare;
			}
			poss_bop++;
			nextSquare = this.board_order[poss_bop];
		}
	}
	
	// Clear out any prior values from board order & rating lists, and square rating table
	private void clearBoardOrder(){
		for (int i = 0; i<81; i++){
			this.board_order[i] = 0;
			this.board_rating[i] = 0;
		}
		for (int i=0; i<9; i++){
			for (int j=0; j<9; j++){
				this.squareRating[i][j] = 0;
			}
		}
	}
	
	// Rate just those squares in a row --
	// This routine used by two of those above.
	private void rateARow(int j){
		for (int i=0; i<9; i++){ //ok, this is the square we're setting up now
			if (this.board[i][j]==0){ // it needs to be assigned a value
				// set a rating for the square, based on how many options there are:
				int myRating = 0; // count restricted values for this square
				for (int k=1; k<10; k++){
					if (!this.checkValues(i, j, k+10)){ //this value already is taken
						myRating++; // increment desirability
						//System.out.println("Existing value for "+i+","+j+"="+k);
					}
				}
				this.squareRating[i][j] = myRating; // save in temp table, before ordering the squares
			}
		}
	}

//	 Likewise for columns --
	// This routine used by SetNextThingInCol.
	private void rateACol(int i){
		for (int j=0; j<9; j++){ //ok, this is the square we're setting up now
			if (this.board[i][j]==0){ // it needs to be assigned a value
				// set a rating for the square, based on how many options there are:
				int myRating = 0; // count restricted values for this square
				for (int k=1; k<10; k++){
					if (!this.checkValues(i, j, k+10)){ //this value already is taken
						myRating++; // increment desirability
						//System.out.println("Existing value for "+i+","+j+"="+k);
					}
				}
				this.squareRating[i][j] = myRating; // save in temp table, before ordering the squares
			}
		}
	}
	
	// The smart way of setting board order of trying squares -- according to how few choices there are:
	private void setBoardOrder(int bop){
		this.rateSquares(); // create the ratings for each square
		// now pick off the values in order, put into board_order table
/*		for (int j=0;j<9;j++){ // clear the x-ref table, which is really used for debugging
			for (int i=0;i<9;i++){
				this.board_order_refs[i][j] = -1; // indicate not present (unless filled in by rtn, below)
			}
		}
*/		int m=bop+1; // index for board_order table
		for (int k=9; k>=0; k--){ // look through temp table 10x, once for each value level
			for (int j=0; j<9; j++){
				for (int i=0; i<9; i++){
					if (this.squareRating[i][j] == k && this.board[i][j]==0){
						this.board_order[m] = 9*j+i; // save this location next
						this.board_rating[m] = k; // and the rating for that location -- debug
						//this.board_order_refs[i][j] = m; // back pntrs to the ordered list - debug
						m++;
					}
				}
			}
		}
		this.final_used = m-1; // last live entry in these tables
		this.board_order[m] = -1; // flag final location we need to worry about
		while (m < 80){
			m++;
			this.board_order[m] = 0; // clear remaining fields, from any earlier puzzles done
		}
		//this.printTemp(); // debug -- show temp board values
	} // end setBoardOrder

	// Test to see what happens if we do the above ordering scheme and then scramble them somewhat:
	private void scrambleBoardOrder(int howManyTimes){
		for (int k=0; k<howManyTimes; k++){
			int firstToDo = (int)(this.final_used * Math.random());
			int secondToDo = (int)(this.final_used * Math.random());
			System.out.println("Random choices are "+ firstToDo +", and "+secondToDo);
			int tempValue = this.board_order[firstToDo]; // switch these two random values and their ratings
			int tempRating = this.board_rating[firstToDo];
			this.board_order[firstToDo] = this.board_order[secondToDo];
			this.board_rating[firstToDo] = this.board_rating[secondToDo];
			this.board_order[secondToDo] = tempValue;
			this.board_rating[secondToDo] = tempRating;
		}
	}
	
	// One stupid way of setting board order, just in sequential order of the ones we need to find values for:
	private void setBoardOrderOrig(){
		int m=0;
		for (int j=0; j<9; j++){
			for (int i=0; i<9; i++){ //ok, this is the square we're setting up now
				if (this.board[i][j]==0){ // it needs to be assigned a value
					this.board_order[m] = 9*j+i; // save in temp table, before ordering the squares
					m++;
				}
			}
		}
		this.final_used = m-1; // last live entry in these tables
		this.board_order[m] = -1; // flag final location we need to worry about
	}
	

	// The stupid other way of setting board order, just in sequential order, by column:
	private void setBoardOrderByCol(){
		int m=0;
		for (int j=0; j<9; j++){
			for (int i=0; i<9; i++){ //ok, this is the square we're setting up now
				if (this.board[j][i]==0){ // it needs to be assigned a value
					this.board_order[m] = 9*i+j; // save in temp table, before ordering the squares
					m++;
				}
			}
		}
		this.final_used = m-1; // last live entry in these tables
		this.board_order[m] = -1; // flag final location we need to worry about
	}
	
	// A stupid third way of setting board order, just a 3x3 square at a time:
	private void setBoardOrderBySquare(){
		int m=0;
		for (int n=0; n<3; n++){ // which 3x3 square across we're doing
			for (int p=0; p<3; p++){ // and which 3x3 square down we're doing
				for (int j=0; j<3; j++){ // inside this 3x3 square, set up each individual square -- index across
					for (int i=0; i<3; i++){ // and index down
						if (this.board[3*n+j][3*p+i]==0){ // it needs to be assigned a value
							this.board_order[m] = 9*(3*p+i)+(3*n+j); // save in temp table, before ordering the squares
							m++;
						}
					}
				}
				
			}
		}
		this.final_used = m-1; // last live entry in these tables
		this.board_order[m] = -1; // flag final location we need to worry about
	}
	
	private void setBoardOrderByThrees(){
		int m=0;
		for (int n=0; n<3; n++){// do next 3 across
			for (int j=0; j<9; j++){
				for (int i=0; i<3; i++){ //ok, this is the square we're setting up now
					if (this.board[3*n+i][j]==0){ // it needs to be assigned a value
						this.board_order[m] = 9*j+(3*n+i); // save in temp table, before ordering the squares
						m++;
					}
				}
			}
		}
		this.final_used = m-1; // last live entry in these tables
		this.board_order[m] = -1; // flag final location we need to worry about
	}
	
	// for debugging -- show the actual order of picking the next square to set a value into
	private void printBoardOrder(){
		this.initial_choices = 0; // report on complexity of this board in 2 ways
		this.initial_choices_product = 1;
		for (int k=0; k< this.board_order.length ; k++){
			System.out.print(" "+this.board_order[k]);
		}
		System.out.println();
		System.out.print(" with board choices ");
		for (int k=0; k< this.board_order.length ; k++){
			System.out.print(" "+this.board_rating[k]);
//			System.out.print(" "+this.initial_choices); // debug display for the ratings, below
			if (k<=this.final_used){ // accumulate values for board complexity ratings
				this.initial_choices = this.initial_choices + (9-this.board_rating[k]);
//				this.initial_choices_product = this.initial_choices_product * (9-this.board_rating[k]);
			}
		}
		System.out.println();
		System.out.println("Total choices in all these squares = "+ this.initial_choices);
		this.initial_choices_product = this.choices_product(-1); // now calls common routine
		System.out.println(" and their product, as a measure of complexity, = "+this.initial_choices_product);
		System.out.println();
	}
	
	// calc remaining complexity as a product, initially or during search:
	private double choices_product(int bop){
		double choices_product = 1;
		for (int k=bop+1; k<=this.final_used; k++){
			choices_product = choices_product * (9-this.board_rating[k]);
		}
		return choices_product;
	}
	
	// for debugging -- show the temporary table in which we assign weights to each square for ordering the search
	private void printTemp(){
		System.out.println("The temp_board is:");
		int j=0;
		int k=0;
		for (k=0; k<9; k++){
			for (j=0; j<9; j++){
				if (this.squareRating[j][k]==0){ // show a space instead of a zero
					System.out.print(" "+"_");
				} else if (this.squareRating[j][k] <  10){
					System.out.print(" "+this.squareRating[j][k]);
				} else { // this one needs 10 subtracted, because it's one of ours
					System.out.print(" "+(this.squareRating[j][k] - 10));
				}
			}
			System.out.println();
		}
	} // end printTemp
	
//	 for debugging -- show the temporary table in which we assign weights to each square for ordering the search
	private void printBoardOrderRefs(){
		System.out.println("The board order refs are:");
		int j=0;
		int k=0;
		for (k=0; k<9; k++){
			for (j=0; j<9; j++){
				if (this.board_order_refs[j][k]==-1){ // show a space instead of a zero
					System.out.print(" "+"_");
				} else {
					System.out.print(" "+this.board_order_refs[j][k]);
				}
			}
			System.out.println();
		}
	} // end printBoardOrderRefs
	
	// this is the main depth-first search routine -- keeps calling itself to progress to a new
	// square, returns on "false".  Has internal iterator to move through progressive choices of values
	// for a partcula square
	private boolean depthFirst(int bop){ // use bop = board order pointer, converted to row and column
		this.cycles++; // increment how many times we've entered this routine recursively
		if (bop > this.maxBop){ // for debugging purposes, keep track of the deepest we've gotten in solving this
			this.maxBop = bop;
		}
		if (bop < this.minBop){// and least backtracking, on later parts of the run
			this.minBop = bop;
		}
		if (this.cycles % 1000000 == 0){ // debug printout for runaways
			System.out.println("Now on cycle "+this.cycles+", bop = "+bop+", maxBop = "+this.maxBop+", out of "+this.final_used+", and minBop = "+this.minBop);
			this.maxBop = 0; // try this again, to see how it goes
			this.minBop = 81;
		}
		int next_i = this.board_order[bop] % 9; // column number to do
		int next_j = this.board_order[bop] / 9; // row number to do
		if (this.board[next_i][next_j] > 0 && this.board[next_i][next_j] <=9) {// this is a preset value in a cell, leave alone!
			bop++;
			if (this.depthFirst(bop)){ // recursive call - reports success at next one called, on up
				return true;
			} else { // can't fix anything here, pass failure message on down
				this.backtracks++;
				return false;
			}
		} else { // this square is ok for changing!
			for (int i = 1; i<10; i++){ // try all the possible values
				this.board[next_i][next_j] = i+10; // use 10 as a marker for these changing values
				if (this.checkValues(next_i, next_j, i+10)){ // it's an ok number to use here, for now
					if (this.board_order[bop+1]==-1){ // we're done!
						return true;
					} else if (this.prettySmartFlag){ // reevaluate all the existing nodes affected by setting this one
						this.setBoardOrder(bop); // reset the  board order for picking next square intelligently
						if (this.depthFirst(bop+1)) {
							return true;
						}
					} else if (this.lookAheadSmartFlag){ // check ahead to stopping place and try to reduce complexity
						this.setBoardOrder(bop); // reset the  board order for picking next square intelligently
				 		//this.printBoardOrder(); // show the order we're using here
				 		//System.out.println("cycles = "+this.cycles+", bop = "+bop+", maxBop = "+this.maxBop+", minBop = "+this.minBop);
				 		if (this.maxBop < this.cycles && bop+1 < this.maxBop) { // we've backtracked
				 			this.lookAheadCount++;
				 			if (this.lookAheadFreq <= this.lookAheadCount ){ // try doing it only infrequently
					 			//System.out.println("Switching "+bop+" with "+this.maxBop);
					 			int next_rating = this.board_rating[this.maxBop]; // try to pick a square value related to this one, next
								int next_order = this.board_order[this.maxBop];
								this.board_rating[this.maxBop] = this.board_rating[bop+1];
								this.board_order[this.maxBop] = this.board_order[bop+1];
//					 			int next_rating = this.board_rating[this.maxBop-1]; // try to pick a square value related to this one, next
//								int next_order = this.board_order[this.maxBop-1];
//								this.board_rating[this.maxBop-1] = this.board_rating[bop+1];
//								this.board_order[this.maxBop-1] = this.board_order[bop+1];
								this.board_rating[bop+1]= next_rating;
								this.board_order[bop+1] = next_order;
								this.maxBop = 0; // reset this until we know we've backtracked again
								this.lookAheadCount = 0; // and wait a bit even after that
				 			}
				 		}
				 		if (this.depthFirst(bop+1)) {
							return true;
						}
					} else if (this.smarterRows){ // check for a better choice in this row only
						   if (this.cycles % 1 == 0){ // it's one time in 2 -- do the smart stuff
								this.SetNextThingInRow(bop);
						   }
							if (this.depthFirst(bop+1)) {
								return true;
							}
					} else if (this.smarterCols){ // likewise for column only
						this.SetNextThingInCol(bop);
						if (this.depthFirst(bop+1)) {
							return true;
						}
					} else if (this.reallySmartFlag){ // reevaluate all existing nodes affected by setting this one
					   if (this.cycles % 1 == 0){ // it's one time in 9 or 3 or 2 -- do the smart stuff
						this.setBoardOrder(bop); // reset the  board order for picking next square intelligently
						int next_bop = bop+1; // try to pick a square value related to this one, next
						int bestRating = this.board_rating[next_bop];
						while ((this.board_rating[next_bop] == bestRating) && (next_bop <= this.final_used)){ // see if there's such a square related to us
							int new_i = this.board_order[next_bop] % 9;
							int new_j = this.board_order[next_bop] / 9;
							if ((new_i == next_i) || (new_j == next_j) || 
									(((new_i / 3) == (next_i / 3)) && ((new_j / 3) == (next_j / 3)) )){ // related
								int temp_to_do = this.board_order[bop+1]; // so exchange these two
								this.board_order[bop+1] = this.board_order[next_bop];
								this.board_order[next_bop] = temp_to_do;
							}
							next_bop++;
						}
					   }
						if (this.depthFirst(bop+1)) {
							return true;
						}
					} else if (this.depthFirst(bop+1)){ //we check all the rest and -- hey -- it worked!
						return true;
					} // else just continue trying the next value in the "for" loop
				}
			}
		}
		this.board[next_i][next_j] = 0; // reset the value in this cell, cleared for backtracking checks
		this.backtracks++;
		return false;
	} // end depthFirst method
	
	// This method returns true if myValue is otherwise unused in its row, column, or 3 x 3 square
	private boolean checkValues(int next_i, int next_j, int myValue){
		// check the row this value is in
		for (int i=0; i<9; i++){
			int boardValue = this.board[i][next_j];
			if (boardValue < 10) { // make the provided values look like my values, for cmparison
				boardValue=boardValue+10;
			}
			if (boardValue == myValue && i != next_i) { // uh oh, not right
				//System.out.println("Found "+myValue+" in row at "+i+", "+next_j);
				return false;
			}
		}
		// check the column it's in
		for (int j=0; j<9; j++){
			int boardValue = this.board[next_i][j];
			if (boardValue < 10) {
				boardValue=boardValue+10;
			}
			if (boardValue == myValue && j != next_j) { // uh oh, not right
				//System.out.println("Found "+myValue+" in column at "+next_i+", "+j);
				return false;
			}
		}
		// check its 3x3 square
		int i1 = next_i - (next_i % 3); // figure out where that starts
		int j1 = next_j - (next_j % 3);
		for (int i = i1; i<i1+3; i++){
			for (int j = j1; j<j1+3; j++){
				int boardValue = this.board[i][j];
				if (boardValue < 10) {
					boardValue=boardValue+10;
				}
				if (boardValue == myValue && (j != next_j || i != next_i)) { // uh oh, not right
					//System.out.println("Found "+myValue+" in 3x3 at "+i+", "+j);
					return false;
				}
			}
		}
		return true;
	} // end checkValues
	
	/**
	 * TODO Put here a description of what this method does.
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("Starting Sudoku");
		sudoku mySudoku = new sudoku();
	} // end main
} // end class
