package org.cmdline.sudoku;

import java.util.Stack;

public class SudokuBoard implements Constants {

	private int[] values = new int[81];
	private Stack guesses = new Stack();
	boolean inited = false;
	
	public static void main(String[] args) {
		byte num;
		int offset;
		
		if (args[0].equals("-t")) {		// test?
			SudokuBoard board = new SudokuBoard();
			for (int i=0;i<81;i++)
				board.set((byte)1,i);
			return;
		}	
		if (args.length < 2) {
			System.out.println("SudokuBoard: missing argument(s)");
			return;	
		}
		try {
			num = (byte)new Integer(args[0]).intValue();
			offset = new Integer(args[1]).intValue();
		}
		catch (Throwable tossed) { 
			tossed.printStackTrace();
			return;
		}
		SudokuBoard board = new SudokuBoard();
		board.set(num,offset);
	}
	
	public SudokuBoard() {
		
	}

	public int[] possibles(int offset,Stack solution) {
		int [] values = new int[81];
		int [] possibles = new int[81*9];
		for (int i=0;i<81;i++) 
			for (int j=0;j<9;j++) possibles[i*9+j] = j+1;
		for (int i=0;i<solution.size();i++) {
			SudokuCell cell = (SudokuCell)solution.elementAt(i);
			// Ignore anything user has done, just used defined puzzle to determine solution
// NEED TO take all filled in values in elimination 
//			if (!cell.getColor().equals(java.awt.Color.black)) {
//				System.out.println(cell.getRow() + " " + cell.getCol() + " color " + cell.getColor() + " skipped");
//				continue;
//			}
			// Set all possible values to 0
			for (int j=0;j<9;j++)
				possibles[cell.getIndex()*9+j] = 0;
			// Set taken to minus it's value to show taken
			possibles[cell.getIndex()*9+cell.getValue()-1] = -cell.getValue();
			values[cell.getIndex()] = cell.getValue();
		}
		int tbox = (offset / 27 * 3) + (offset % 9 / 3);
		int trow = offset / 9;
		int tcol = offset % 9;
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++) {
				// Check if the same box
				int i = row*COLS+col;
				if (values[i] == 0) continue;	// No value - no elimination
				int box = (i / 27 * 3) + (i % 9 /3);
				if (box == tbox) {
					if (possibles[offset*9+values[i]-1] != 0) {
						possibles[offset*9+values[i]-1] = 0;
						continue;
					}
					// else already done, not a change
				}
				if (row == trow) {
					if (possibles[offset*9+values[i]-1] != 0) {
						possibles[offset*9+values[i]-1] = 0;
						continue;
					}
					// else already done, not a change
				}
				if (col == tcol) 
					if (possibles[offset*9+values[i]-1] != 0) {
						possibles[offset*9+values[i]-1] = 0;
					}
					// else already done, not a change
			}
		}
		int[] index_possibles = new int[9];
		System.arraycopy(possibles,offset*9,index_possibles,0,index_possibles.length);
		return index_possibles;
	}
		
	public int[] solve(Stack solution) {
		int [] values = new int[81];
		int [] possibles = new int[81*9];
		for (int i=0;i<81;i++) 
			for (int j=0;j<9;j++) possibles[i*9+j] = j+1;
		for (int i=0;i<solution.size();i++) {
			SudokuCell cell = (SudokuCell)solution.elementAt(i);
			// Ignore anything user has done, just used defined puzzle to determine solution
			if (!cell.getColor().equals(java.awt.Color.black)) {
//				System.out.println(cell.getRow() + " " + cell.getCol() + " color " + cell.getColor() + " skipped");
				continue;
			}
			// Set all possible values to 0
			for (int j=0;j<9;j++)
				possibles[cell.getIndex()*9+j] = 0;
			// Set taken to minus it's value to show taken
			int taken = -cell.getValue();
			possibles[cell.getIndex()*9+cell.getValue()-1] = -cell.getValue();
			values[cell.getIndex()] = cell.getValue();
		}
		try {
			solve(values,possibles);
		}
		catch (Throwable tossed) { tossed.printStackTrace(); }
		return values;
	}

	private void solve(int [] values,int[] possibles) {
		boolean changed = false;			// If we make no changes, we have a problem
		for (int offset = 0; offset < 81; offset++) {
			int poffset = offset * 9;	// offset into possible values
			// For now we assume all values are good, no solution has gotten off-track already
			if (values[offset] != 0) continue;
			int tbox = (offset / 27 * 3) + (offset % 9 / 3);
			int trow = offset / 9;
			int tcol = offset % 9;
			for (int row = 0; row < 9; row++) {
				for (int col = 0; col < 9; col++) {
					// Check if the same box
					int i = row*COLS+col;
					if (values[i] == 0) continue;	// No value - no elimination
					int box = (i / 27 * 3) + (i % 9 /3);
					if (box == tbox) {
						if (possibles[offset*9+values[i]-1] != 0) {
							possibles[offset*9+values[i]-1] = 0;
							changed = true;	
							continue;
						}
						// else already done, not a change
					}
					if (row == trow) {
						if (possibles[offset*9+values[i]-1] != 0) {
							possibles[offset*9+values[i]-1] = 0;
							changed = true;	
							continue;
						}
						// else already done, not a change
					}
					if (col == tcol) 
						if (possibles[offset*9+values[i]-1] != 0) {
							possibles[offset*9+values[i]-1] = 0;
							changed = true;
						}
						// else already done, not a change
				}
			}
		}
	
		boolean guess = true;	// Assume we have to guess
		for (int i = 0; i < 81; i++) {
			int first = 0;
			for (int j=0;j<9;j++) {
				if (possibles[i*9+j] < 0) break;	// taken
				if (possibles[i*9+j] != 0) {
					if (first != 0) {
						first = 0;		// too many counts as none
						break;		
					}	
					first = possibles[i*9+j]; 
				}
			}
			if (first != 0) {			// had a single possible value?
				guess = false;			// don't need to yet
				if (!check(values,i,first)) {
					backup(values,possibles);
					solve(values,possibles);		// Should of made a change there so recursion not a problem
					return;
				}
				changed = true;
				values[i] = first;
				possibles[i*9+first-1] = -first;	// set it as taken
			}
		}
		if (guess) {
			changed = true;
			if (!guess(values,possibles))	
				backup(values,possibles);	// failed to make a valid guess, time to backup again
		}
		if (complete(values)) return;		
		if (!changed)
			throw new IllegalStateException("No changes to solution");
		solve(values,possibles);	// recurse with new changes we just made to solution
	}
	
	public boolean complete(int[] values) {
		for (int i=0;i<values.length;i++)
			if (values[i] == 0) return false;
		return true;
	}

	private void backup(int[] values,int[] possibles) {
		if (guesses.size() == 0) {	// Should not happen
			for (int ix=0;ix<81;ix++) {
				for (int j=0;j<9;j++)
					if (possibles[ix*9+j] != 0) System.out.print(possibles[ix*9+j] + " ");
				System.out.println("");
			}
			throw new IllegalStateException("Duplicated value without a guess");
		}
		// There should of been a guess, we now should back up to it 
		// and start over with next value 
		for (;;) {
			Guess g = erase(values,possibles);	// should do the backup part
			int index = g.getIndex();
			for (int j=0;j<9;j++) {
				if (possibles[index*9+j] < 0) // shouldn't happen
					throw new IllegalStateException("Value set on a next try");
				// Find new first non-zero possibility and use as next guess
				if (possibles[index*9+j] > 0) {
// create new guess before we make any changes to values or possibles
					g = new Guess(index,possibles[index*9+j],values,possibles);
					values[index] = possibles[index*9+j];
					for (int k=0;k<9;k++)		// zero out all possibles
						possibles[index*9+k] = 0;
					possibles[index*9+j] = -values[index];				
					guesses.push(g);
					// We should of made a change by here? So recursion not a worry
//					solve(values,possibles);
					return;
				}	
			}
			if (guesses.size() == 0) 
				throw new IllegalStateException("Can't erase previous guess");
		}				
	}
	
	private boolean guess(int[] values,int[] possibles) {
		boolean success = false;
		// We look for possibles with minimum remaining for better odds on guess
		for (int count=2;count<10;count++) {
			for (int i=0;i<81;i++) {
				int left = 0;
				int first = 0;
				for (int j=0;j<9;j++) {
					if (possibles[i*9+j] < 0) {
						left = count+1;				// already set, set to fail as guess
						break;
					}
					else if (possibles[i*9+j] > 0) {
						left++;
						if (first == 0) first = possibles[i*9+j];
					}
					if (left > count) break;
				}
				if (first != 0 && left <= count) {	
					success = true;
					Guess g = new Guess(i,first,values,possibles);
					guesses.push(g);
					for (int j=0;j<9;j++)		// zero out all possibles
						possibles[i*9+j] = 0;
					values[i] = first;
					possibles[i*9+first-1] = -first;	// add back the one we're guessing
					break;
				}
			}
			if (success) break;
		}
		if (!success) {
/* DEBUG
			for (int i=0;i<81;i++) {
				for (int j=0;j<9;j++)
					if (possibles[i*9+j] != 0) System.out.print(possibles[i*9+j] + " ");
				System.out.println("");
			}
*/
			return false;
		}
		return true;
	}
	
	class Guess {
		int value = 0, index = 0;
		int[] values,possibles;
		
		public Guess(int index,int value,int[] values,int[] possibles) {
			this.index = index;
			this.value = value;
			this.values = new int[values.length]; 
			System.arraycopy(values,0,this.values,0,values.length);
			this.possibles = new int[possibles.length]; 
			System.arraycopy(possibles,0,this.possibles,0,possibles.length);
		}
		
		public int getIndex() { return index; }
		public int getValue() { return value; }
		public int[] getValues() { return values; }
		public int[] getPossibles() { return possibles; }
	}
		
	private Guess erase(int[] values,int[] possibles) {
		boolean first = false;
		Guess g = (Guess)guesses.pop();
		int index = g.getIndex();
		int value = g.getValue();
		System.arraycopy(g.getValues(),0,values,0,values.length);			// restore prior values
		System.arraycopy(g.getPossibles(),0,possibles,0,possibles.length);	// restore prior possibles
		// remove current value as possible value 
		possibles[index*9+value-1] = 0;				
		return g;
	}
	
	private boolean check(int[] values,int offset,int value) {
		int box = (offset / 27 * 3) + (offset % 9 / 3);
		int row = offset / 9;
		int col = offset % 9;
		for (int i=0;i<values.length;i++) {
			int tbox = (i / 27 * 3) + (i % 9 / 3);
			int trow = i / 9;
			int tcol = i % 9;
			if (values[i] == 0 || i == offset) continue;
			if (tbox == box) 	// same box?
				if (values[i] == value) return false;
			if (trow == row)
				if (values[i] == value) return false;
			if (tcol == col) 
				if (values[i] == value) return false;
		}
		return true;
	}

	public int set(byte num,int offset) {
		if (num == 0) {
			values[offset] = 0;
			return 0;
		}
		int box,row,col;
		box = (offset / 27 * 3) + (offset % 9 / 3);
		row = offset / 9;
		col = offset % 9;
		int result = test(num,box,row,col);
		// set in box
		if (result == 0) values[offset] = num;
		return result;
	}
	
	// Generate a new grid with valid numbers
	public int[] generate(long seed) {
		java.util.Random rand = new java.util.Random(seed);
		int[] board = new int[81];
		int[] init = new int[] { 1,2,3,4,5,6,7,8,9 };
		// get first row
		for (int i=0;i<init.length-1;i++) {
			int idx = Math.abs(rand.nextInt()) % (init.length-i);
			board[i] = init[idx];	
			for (int j=idx;j<init.length-1;j++)
				init[j] = init[j+1];	
			init[init.length-1] = 0;	
		}
		board[8] = init[0];
		// Now solve 
		int [] possibles = new int[81*9];
		for (int i=0;i<81;i++) 
			for (int j=0;j<9;j++) possibles[i*9+j] = j+1;
		for (int i=0;i<9;i++) {
			// Set all possible values to 0
			for (int j=0;j<9;j++)
				possibles[i*9+j] = 0;
			// Set taken to minus it's value to show taken
			possibles[i*9+board[i]-1] = -board[i];
		}
		solve(board,possibles);
/*
		for (int i=0;i<81;i++) {
			System.out.print(board[i] + " ");
			if (i % 9 == 8) System.out.println("");
		}
*/
		return board;
	}
	
	private int test(byte num,int newBox,int newRow,int newCol) {
		for (int i=0;i<81;i++) {
			int box = (i / 27 * 3) + (i % 9 /3);
			if ((byte)values[i] != num) continue; 
			if (newBox == box) return i;
			int row = i / 9;
			if (newRow == row) return i;
			int col = i % 9;
			if (newCol == col) return i;
		}
		return 0;
	}
	

}