inoxor

import java.util.*;public class Sudoku {	private boolean[][] finalSolution = null;		public Sudoku() {		boolean[][] possibleNums = readInput();				printTable(possibleNums);		if(!checkAndGuess(possibleNums))			System.out.println("Oops not possible");		if(finalSolution != null)			printTable(finalSolution);	}		public boolean[][] readInput() {		Scanner sc = new Scanner(System.in);		String in = "";		boolean[][] possibleNums = new boolean[9*9][9];				// all nums are possible		for(int i = 0; i < 9*9; i++)			for(int j = 0; j < 9; j++)				possibleNums[i][j] = true;				for(int i = 0; i < 9; i++) {			in += sc.next();		}				if(in.length() %9 != 0) {			System.err.println("Lines must be 9 char");			System.exit(0);		}				for(int i = 0; i < 9*9; i++) {	// transfer to array of possible numbers			if(in.charAt(i) >= '1' && in.charAt(i) <= '9') {				for(int j = 0; j < 9; j++) {					if(j != (in.charAt(i) -49))						possibleNums[i][j] = false;				}			}		}				return possibleNums;	}		public void printTable(boolean[][] possibleNums) {		for(int i = 0; i < 9*9; i++) {			String tmp = "";			for(int j = 0; j < 9; j++) {				if(possibleNums[i][j])					tmp += j+1;			}			System.out.printf("%9s ", tmp);			if((i+1)%3 == 0)				System.out.print("|");			if((i+1)%9 == 0)				System.out.println();			if((i+1)%(9*3) == 0) {				for(int j = 0; j < (9*9+12); j++) {					System.out.print("-");				}				System.out.println();			}		}	}		public boolean checkAndGuess(boolean[][] possibleNums) {		boolean[][] workNums = new boolean[9*9][9];		int[] makeGuess = new int[2];				if(!eliminate(possibleNums)) {			System.out.println("Not possible!");			return false;		}				for(int i = 0; i < 9*9; i++) {			int numInPos = 0;			makeGuess[0] = -1;	// so we can check if we saved a value!						for(int j = 0; j < 9; j++) {				if(possibleNums[i][j]) {					if(makeGuess[0] < 0) {						makeGuess[0] = i;	// position						makeGuess[1] = j;	// lets save the first value we encounter					}					numInPos++;				}			}			if(numInPos > 1) {		// here we make the guess				System.out.println("Guessing " + makeGuess[0] + " num:" + (makeGuess[1]+1));								for(int k = 0; k < 9*9; k++) {					for(int l = 0; l < 9; l++) {						if(k == makeGuess[0])							workNums[k][l] = false;						else							workNums[k][l] = possibleNums[k][l];	// copy					}				}								workNums[makeGuess[0]][makeGuess[1]] = true;	// set the actual guess value to true								// Here the call chain starts				if(!checkAndGuess(workNums)) {	// this did not work!					possibleNums[makeGuess[0]][makeGuess[1]] = false;					return checkAndGuess(possibleNums);				}				else {					return true;				}			}		}				if(finalSolution == null)	// done!!			finalSolution = possibleNums;				return true;	}		// returns false if this is not a possible sudoku, else true. also eliminates until no more is possible	public boolean eliminate(boolean[][] possibleNums) {		boolean didChange = false;				for(int i = 0; i < 9*9; i++) {			int numInPos = 0, theNumber = -1;			for(int j = 0; j < 9; j++) {				if(possibleNums[i][j]) {					numInPos++;					theNumber = j; // save for later				}			}						if(numInPos == 1) {				if(eliminateRow(possibleNums, i, theNumber) || eliminateCol(possibleNums, i, theNumber)					|| eliminateBox(possibleNums, i, theNumber) )						didChange = true;			}		}				// we're done		if(!didChange)			return isPossible(possibleNums);	// check if it is valid				return eliminate(possibleNums);	}		public boolean eliminateRow(boolean[][] possibleNums, int i, int num) {		boolean didChange = false;		int begin = i/9;		begin = begin*9;				for(int j = 0; j < 9; j++) {			if((begin+j) != i) {	// do not remove the fixed number				if(possibleNums[begin+j][num]) {					possibleNums[begin+j][num] = false;					didChange = true;				}			}		}		return didChange;	}		public boolean eliminateCol(boolean[][] possibleNums, int i, int num) {		boolean didChange = false;		int offset = i%9;				for(int j = 0; j < 9; j++) {			if((offset+j*9) != i) {	// do not remove the fixed number				if(possibleNums[offset+j*9][num]) {					possibleNums[offset+j*9][num] = false;					didChange = true;				}			}		}		return didChange;	}		public boolean eliminateBox(boolean[][] possibleNums, int i, int num) {		boolean didChange = false;		int offsetCol = (i%9)/3;		offsetCol = offsetCol*3;		int offsetRow = i/9;		offsetRow = offsetRow/3;		offsetRow = offsetRow*9*3;				for(int j = 0; j < 3; j++) {			for(int k = 0; k < 3; k++) {				if((offsetRow+j*9+offsetCol+k) != i) {					if(possibleNums[offsetRow+j*9+offsetCol+k][num]) {						possibleNums[offsetRow+j*9+offsetCol+k][num] = false;						didChange = true;					}				}			}		}		return didChange;	}		// returns false if there is a place with no possible number	public boolean isPossible(boolean[][] possibleNums) {		for(int i = 0; i < 9*9; i++) {			int numInPos = 0;						for(int j = 0; j < 9; j++)				if(possibleNums[i][j])					numInPos++;						if(numInPos == 0)	// must be at least 1 possible number per position				return false;		}		return true;	}		public static void main(String[] args) {		new Sudoku();	}}