import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Calendar;
import java.util.Random;
import java.util.ArrayList;
public class QQWing {
public static final int ONE_LINE = 1;
public static final int COMPACT = 2;
public static final int READABLE = 3;
public static final int CSV = 4;
public static final int UNKNOWN = 1;
public static final int SIMPLE = 2;
public static final int EASY = 3;
public static final int INTERMEDIATE = 4;
public static final int EXPERT = 5;
public static final int GRID_SIZE = 3;
public static final int ROW_LENGTH = (GRID_SIZE*GRID_SIZE);
public static final int COL_HEIGHT = (GRID_SIZE*GRID_SIZE);
public static final int SEC_SIZE = (GRID_SIZE*GRID_SIZE);
public static final int SEC_COUNT = (GRID_SIZE*GRID_SIZE);
public static final int SEC_GROUP_SIZE = (SEC_SIZE*GRID_SIZE);
public static final int NUM_POSS = (GRID_SIZE*GRID_SIZE);
public static final int BOARD_SIZE = (ROW_LENGTH*COL_HEIGHT);
public static final int POSSIBILITY_SIZE = (BOARD_SIZE*NUM_POSS);
public static final int NONE = 1;
public static final int GENERATE = 2;
public static final int SOLVE = 3;
public static Random r;
int lastSolveRound;
int[] puzzle;
int[] solution;
int[] solutionRound;
int[] possibilities;
int[] randomBoardArray;
int[] randomPossibilityArray;
boolean recordHistory;
boolean logHistory;
ArrayList<LogItem> solveHistory;
ArrayList<LogItem> solveInstructions;
int printStyle;
public QQWing(){
puzzle = new int[BOARD_SIZE];
solution = new int[BOARD_SIZE];
solutionRound = new int[BOARD_SIZE];
possibilities = new int[POSSIBILITY_SIZE];
recordHistory = false;
printStyle = READABLE;
randomBoardArray = new int[BOARD_SIZE];
randomPossibilityArray = new int[NUM_POSS];
solveHistory = new ArrayList<LogItem>();
solveInstructions = new ArrayList<LogItem>();
for (int i=0; i<BOARD_SIZE; i++){
randomBoardArray[i] = i;
}
for (int i=0; i<NUM_POSS; i++){
randomPossibilityArray[i] = i;
}
}
int getGivenCount(){
int count = 0;
for (int i=0; i<BOARD_SIZE; i++){
if (puzzle[i] != 0) count++;
}
return count;
}
boolean setPuzzle(int[] initPuzzle) throws Exception {
for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = (initPuzzle == null) ? 0:initPuzzle[i];
}
return reset();
}
boolean reset() throws Exception {
for (int i=0; i<BOARD_SIZE; i++){
solution[i] = 0;
}
for (int i=0; i<BOARD_SIZE; i++){
solutionRound[i] = 0;
}
for (int i=0; i<POSSIBILITY_SIZE; i++){
possibilities[i] = 0;
}
for (int i=0;i<solveHistory.size();i++){
solveHistory.remove(i);
}
solveHistory.clear();
solveInstructions.clear();
int round = 1;
for (int position=0; position<BOARD_SIZE; position++){
if (puzzle[position] > 0){
int valIndex = puzzle[position]-1;
int valPos = getPossibilityIndex(valIndex,position);
int value = puzzle[position];
if (possibilities[valPos] != 0) return false;
mark(position,round,value);
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.GIVEN, value, position));
}
}
return true;
}
int getDifficulty(){
if (getGuessCount() > 0) return EXPERT;
if (getBoxLineReductionCount() > 0) return INTERMEDIATE;
if (getPointingPairTripleCount() > 0) return INTERMEDIATE;
if (getHiddenPairCount() > 0) return INTERMEDIATE;
if (getNakedPairCount() > 0) return INTERMEDIATE;
if (getHiddenSingleCount() > 0) return EASY;
if (getSingleCount() > 0) return SIMPLE;
return UNKNOWN;
}
String getDifficultyAsString(){
int difficulty = getDifficulty();
switch (difficulty){
case EXPERT: return "Expert";
case INTERMEDIATE: return "Intermediate";
case EASY: return "Easy";
case SIMPLE: return "Simple";
default: return "Unknown";
}
}
int getSingleCount(){
return getLogCount(solveInstructions, LogItem.SINGLE);
}
int getHiddenSingleCount(){
return (
getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_ROW) +
getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_COLUMN) +
getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_SECTION)
);
}
int getNakedPairCount(){
return (
getLogCount(solveInstructions, LogItem.NAKED_PAIR_ROW) +
getLogCount(solveInstructions, LogItem.NAKED_PAIR_COLUMN) +
getLogCount(solveInstructions, LogItem.NAKED_PAIR_SECTION)
);
}
int getHiddenPairCount(){
return (
getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_ROW) +
getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_COLUMN) +
getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_SECTION)
);
}
int getPointingPairTripleCount(){
return (
getLogCount(solveInstructions, LogItem.POINTING_PAIR_TRIPLE_ROW)+
getLogCount(solveInstructions, LogItem.POINTING_PAIR_TRIPLE_COLUMN)
);
}
int getBoxLineReductionCount(){
return (
getLogCount(solveInstructions, LogItem.ROW_BOX)+
getLogCount(solveInstructions, LogItem.COLUMN_BOX)
);
}
int getGuessCount(){
return getLogCount(solveInstructions, LogItem.GUESS);
}
int getBacktrackCount(){
return getLogCount(solveHistory, LogItem.ROLLBACK);
}
void markRandomPossibility(int round) throws Exception {
int remainingPossibilities = 0;
for (int i=0; i<POSSIBILITY_SIZE; i++){
if (possibilities[i] == 0) remainingPossibilities++;
}
int randomPossibility = Math.abs(r.nextInt())%remainingPossibilities;
int possibilityToMark = 0;
for (int i=0; i<POSSIBILITY_SIZE; i++){
if (possibilities[i] == 0){
if (possibilityToMark == randomPossibility){
int position = i/NUM_POSS;
int value = i%NUM_POSS+1;
mark(position, round, value);
return;
}
possibilityToMark++;
}
}
}
void shuffleRandomArrays(){
shuffleArray(randomBoardArray, BOARD_SIZE);
shuffleArray(randomPossibilityArray, NUM_POSS);
}
void clearPuzzle() throws Exception {
for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = 0;
}
reset();
}
boolean generatePuzzle() throws Exception {
boolean recHistory = recordHistory;
setRecordHistory(false);
boolean lHistory = logHistory;
setLogHistory(false);
clearPuzzle();
shuffleRandomArrays();
solve();
rollbackNonGuesses();
for (int i=0; i<BOARD_SIZE; i++){
puzzle[i] = solution[i];
}
shuffleRandomArrays();
for (int i=0; i<BOARD_SIZE; i++){
int position = randomBoardArray[i];
if (puzzle[position] > 0){
int savedValue = puzzle[position];
puzzle[position] = 0;
reset();
if (countSolutions(2, true) > 1){
puzzle[position] = savedValue;
}
}
}
reset();
setRecordHistory(recHistory);
setLogHistory(lHistory);
return true;
}
void rollbackNonGuesses(){
for (int i=2; i<=lastSolveRound; i+=2){
rollbackRound(i);
}
}
void setPrintStyle(int ps){
printStyle = ps;
}
void setRecordHistory(boolean recHistory){
recordHistory = recHistory;
}
void setLogHistory(boolean logHist){
logHistory = logHist;
}
void addHistoryItem(LogItem l){
if (logHistory){
l.print();
System.out.println();
}
if (recordHistory) {
solveHistory.add(l); solveInstructions.add(l); } else {
l = null;
}
}
void printHistory(ArrayList<LogItem> v){
if (!recordHistory){
System.out.println("History was not recorded.");
if (printStyle == CSV){
System.out.println(" -- ");
} else {
System.out.println();
}
}
for (int i=0;i<v.size();i++){
System.out.println(i+1+". ");
(v.get(i)).print();
if (printStyle == CSV){
System.out.println(" -- ");
} else {
System.out.println();
}
}
if (printStyle == CSV){
System.out.println(",");
} else {
System.out.println();
}
}
void printSolveInstructions(){
if (isSolved()){
printHistory(solveInstructions);
} else {
System.out.println("No solve instructions - Puzzle is not possible to solve.");
}
}
void printSolveHistory(){
printHistory(solveHistory);
}
boolean solve() throws Exception {
reset();
shuffleRandomArrays();
return solve(2);
}
boolean solve(int round) throws Exception {
lastSolveRound = round;
while (singleSolveMove(round)){
if (isSolved()) return true;
if (isImpossible()) return false;
}
int nextGuessRound = round+1;
int nextRound = round+2;
for (int guessNumber=0; guess(nextGuessRound, guessNumber); guessNumber++){
if (isImpossible() || !solve(nextRound)){
rollbackRound(nextRound);
rollbackRound(nextGuessRound);
} else {
return true;
}
}
return false;
}
int countSolutions() throws Exception {
boolean recHistory = recordHistory;
setRecordHistory(false);
boolean lHistory = logHistory;
setLogHistory(false);
reset();
int solutionCount = countSolutions(2, false);
setRecordHistory(recHistory);
setLogHistory(lHistory);
return solutionCount;
}
int countSolutions(int round, boolean limitToTwo) throws Exception {
while (singleSolveMove(round)){
if (isSolved()){
rollbackRound(round);
return 1;
}
if (isImpossible()){
rollbackRound(round);
return 0;
}
}
int solutions = 0;
int nextRound = round+1;
for (int guessNumber=0; guess(nextRound, guessNumber); guessNumber++){
solutions += countSolutions(nextRound, limitToTwo);
if (limitToTwo && solutions >=2){
rollbackRound(round);
return solutions;
}
}
rollbackRound(round);
return solutions;
}
void rollbackRound(int round){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.ROLLBACK));
for (int i=0; i<BOARD_SIZE; i++){
if (solutionRound[i] == round){
solutionRound[i] = 0;
solution[i] = 0;
}
}
for (int i=0; i<POSSIBILITY_SIZE; i++){
if (possibilities[i] == round){
possibilities[i] = 0;
}
}
while(solveInstructions.size() > 0 && (solveInstructions.get(solveInstructions.size()-1)).getRound() == round){
int i = solveInstructions.size()-1;
solveInstructions.remove(i);
}
}
boolean isSolved(){
for (int i=0; i<BOARD_SIZE; i++){
if (solution[i] == 0){
return false;
}
}
return true;
}
boolean isImpossible(){
for (int position=0; position<BOARD_SIZE; position++){
if (solution[position] == 0){
int count = 0;
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0) count++;
}
if (count == 0) {
return true;
}
}
}
return false;
}
int findPositionWithFewestPossibilities(){
int minPossibilities = 10;
int bestPosition = 0;
for (int i=0; i<BOARD_SIZE; i++){
int position = randomBoardArray[i];
if (solution[position] == 0){
int count = 0;
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0) count++;
}
if (count < minPossibilities){
minPossibilities = count;
bestPosition = position;
}
}
}
return bestPosition;
}
boolean guess(int round, int guessNumber) throws Exception {
int localGuessCount = 0;
int position = findPositionWithFewestPossibilities();
for (int i=0; i<NUM_POSS; i++){
int valIndex = randomPossibilityArray[i];
int valPos = getPossibilityIndex(valIndex,position);
if (possibilities[valPos] == 0){
if (localGuessCount == guessNumber){
int value = valIndex+1;
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.GUESS, value, position));
mark(position, round, value);
return true;
}
localGuessCount++;
}
}
return false;
}
boolean singleSolveMove(int round) throws Exception {
if (onlyPossibilityForCell(round)) return true;
if (onlyValueInSection(round)) return true;
if (onlyValueInRow(round)) return true;
if (onlyValueInColumn(round)) return true;
if (handleNakedPairs(round)) return true;
if (pointingRowReduction(round)) return true;
if (pointingColumnReduction(round)) return true;
if (rowBoxReduction(round)) return true;
if (colBoxReduction(round)) return true;
if (hiddenPairInRow(round)) return true;
if (hiddenPairInColumn(round)) return true;
if (hiddenPairInSection(round)) return true;
return false;
}
boolean colBoxReduction(int round){
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
for (int col=0; col<9; col++){
int colStart = columnToFirstCell(col);
boolean inOneBox = true;
int colBox = -1;
for (int i=0; i<3; i++){
for (int j=0; j<3; j++){
int row = i*3+j;
int position = rowColumnToCell(row, col);
int valPos = getPossibilityIndex(valIndex,position);
if(possibilities[valPos] == 0){
if (colBox == -1 || colBox == i){
colBox = i;
} else {
inOneBox = false;
}
}
}
}
if (inOneBox && colBox != -1){
boolean doneSomething = false;
int row = 3*colBox;
int secStart = cellToSectionStartCell(rowColumnToCell(row, col));
int secStartRow = cellToRow(secStart);
int secStartCol = cellToColumn(secStart);
for (int i=0; i<3; i++){
for (int j=0; j<3; j++){
int row2 = secStartRow+i;
int col2 = secStartCol+j;
int position = rowColumnToCell(row2, col2);
int valPos = getPossibilityIndex(valIndex,position);
if (col != col2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.COLUMN_BOX, valIndex+1, colStart));
return true;
}
}
}
}
return false;
}
boolean rowBoxReduction(int round){
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
for (int row=0; row<9; row++){
int rowStart = rowToFirstCell(row);
boolean inOneBox = true;
int rowBox = -1;
for (int i=0; i<3; i++){
for (int j=0; j<3; j++){
int column = i*3+j;
int position = rowColumnToCell(row, column);
int valPos = getPossibilityIndex(valIndex,position);
if(possibilities[valPos] == 0){
if (rowBox == -1 || rowBox == i){
rowBox = i;
} else {
inOneBox = false;
}
}
}
}
if (inOneBox && rowBox != -1){
boolean doneSomething = false;
int column = 3*rowBox;
int secStart = cellToSectionStartCell(rowColumnToCell(row, column));
int secStartRow = cellToRow(secStart);
int secStartCol = cellToColumn(secStart);
for (int i=0; i<3; i++){
for (int j=0; j<3; j++){
int row2 = secStartRow+i;
int col2 = secStartCol+j;
int position = rowColumnToCell(row2, col2);
int valPos = getPossibilityIndex(valIndex,position);
if (row != row2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.ROW_BOX, valIndex+1, rowStart));
return true;
}
}
}
}
return false;
}
boolean pointingRowReduction(int round){
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
for (int section=0; section<9; section++){
int secStart = sectionToFirstCell(section);
boolean inOneRow = true;
int boxRow = -1;
for (int j=0; j<3; j++){
for (int i=0; i<3; i++){
int secVal=secStart+i+(9*j);
int valPos = getPossibilityIndex(valIndex,secVal);
if(possibilities[valPos] == 0){
if (boxRow == -1 || boxRow == j){
boxRow = j;
} else {
inOneRow = false;
}
}
}
}
if (inOneRow && boxRow != -1){
boolean doneSomething = false;
int row = cellToRow(secStart) + boxRow;
int rowStart = rowToFirstCell(row);
for (int i=0; i<9; i++){
int position = rowStart+i;
int section2 = cellToSection(position);
int valPos = getPossibilityIndex(valIndex,position);
if (section != section2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.POINTING_PAIR_TRIPLE_ROW, valIndex+1, rowStart));
return true;
}
}
}
}
return false;
}
boolean pointingColumnReduction(int round){
for (int valIndex=0; valIndex<NUM_POSS; valIndex++){
for (int section=0; section<9; section++){
int secStart = sectionToFirstCell(section);
boolean inOneCol = true;
int boxCol = -1;
for (int i=0; i<3; i++){
for (int j=0; j<3; j++){
int secVal=secStart+i+(9*j);
int valPos = getPossibilityIndex(valIndex,secVal);
if(possibilities[valPos] == 0){
if (boxCol == -1 || boxCol == i){
boxCol = i;
} else {
inOneCol = false;
}
}
}
}
if (inOneCol && boxCol != -1){
boolean doneSomething = false;
int col = cellToColumn(secStart) + boxCol;
int colStart = columnToFirstCell(col);
for (int i=0; i<9; i++){
int position = colStart+(9*i);
int section2 = cellToSection(position);
int valPos = getPossibilityIndex(valIndex,position);
if (section != section2 && possibilities[valPos] == 0){
possibilities[valPos] = round;
doneSomething = true;
}
}
if (doneSomething){
if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem.POINTING_PAIR_TRIPLE_COLUMN, valIndex+1, colStart));
return true;
}
}
}
}
return fa