HTML of QQWing

/*
 * qqwing - A Sudoku solver and generator
 * Copyright (C) 2006-2007 Stephen Ostermiller
 * http://ostermiller.org/qqwing/
 * Copyright (C) 2007 Jacques Bensimon (jacques@ipm.com)
 * Copyright (C) 2007 Joel Yarde (joel.yarde - gmail.com)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Calendar;
import java.util.Random;
import java.util.ArrayList;

/**
 * The board containing all the memory structures and
 * methods for solving or generating sudoku puzzles.
 */
public class QQWing {
    /**
     * PrintStyle
     */
    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;

    /**
     * Difficulty
     */
    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; 
    /**
     * The last round of solving
     */
    int lastSolveRound;

    /**
     * The 81 integers that make up a sudoku puzzle.
     * Givens are 1-9, unknows are 0.
     * Once initialized, this puzzle remains as is.
     * The answer is worked out in "solution".
     */
    int[] puzzle;

    /**
     * The 81 integers that make up a sudoku puzzle.
     * The solution is built here, after completion
     * all will be 1-9.
     */
    int[] solution;

    /**
     * Recursion depth at which each of the numbers
     * in the solution were placed.  Useful for backing
     * out solve branches that don't lead to a solution.
     */
    int[] solutionRound;

    /**
     * The 729 integers that make up a the possible
     * values for a suduko puzzle. (9 possibilities
     * for each of 81 squares).  If possibilities[i]
     * is zero, then the possibility could still be
     * filled in according to the sudoku rules.  When
     * a possibility is eliminated, possibilities[i]
     * is assigned the round (recursion level) at
     * which it was determined that it could not be
     * a possibility.
     */
    int[] possibilities;

    /**
     * An array the size of the board (81) containing each
     * of the numbers 0-n exactly once.  This array may
     * be shuffled so that operations that need to
     * look at each cell can do so in a random order.
     */
    int[] randomBoardArray;

    /**
     * An array with one element for each position (9), in
     * some random order to be used when trying each
     * position in turn during guesses.
     */
    int[] randomPossibilityArray;

    /**
     * Whether or not to record history
     */
    boolean recordHistory;

    /**
     * Whether or not to print history as it happens
     */
    boolean logHistory;

    /**
     * A list of moves used to solve the puzzle.
     * This list contains all moves, even on solve
     * branches that did not lead to a solution.
     */
    ArrayList<LogItem> solveHistory;

    /**
     * A list of moves used to solve the puzzle.
     * This list contains only the moves needed
     * to solve the puzzle, but doesn't contain
     * information about bad guesses.
     */
    ArrayList<LogItem> solveInstructions;

    /**
     * The style with which to print puzzles and solutions
     */
    int printStyle;

    /**
     * Create a new Sudoku board
     */
    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;
        }
    }

    /**
     * Get the number of cells that are
     * set in the puzzle (as opposed to
     * figured out in the solution
     */
    int getGivenCount(){
        int count = 0;
        for (int i=0; i<BOARD_SIZE; i++){
            if (puzzle[i] != 0) count++;
        }
        return count;
    }

    /**
     * Set the board to the given puzzle.
     * The given puzzle must be an array of 81 integers.
     */
    boolean setPuzzle(int[] initPuzzle) throws Exception {
        for (int i=0; i<BOARD_SIZE; i++){
                puzzle[i] = (initPuzzle == null) ? 0:initPuzzle[i];
        }
        return reset();
    }

    /**
     * Reset the board to its initial state with
     * only the givens.
     * This method clears any solution, resets statistics,
     * and clears any history messages.
     */
    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;
    }

    /**
     * Get the difficulty rating.
     */
    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;
    }

    /**
     * Get the difficulty rating.
     */
    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";
        }
    }

    /**
     * Get the number of cells for which the solution was determined
     * because there was only one possible value for that cell.
     */
    int getSingleCount(){
        return getLogCount(solveInstructions, LogItem.SINGLE);
    }

    /**
     * Get the number of cells for which the solution was determined
     * because that cell had the only possibility for some value in
     * the row, column, or section.
     */
    int getHiddenSingleCount(){
        return (
            getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_ROW) +
            getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_COLUMN) +
            getLogCount(solveInstructions, LogItem.HIDDEN_SINGLE_SECTION)
        );
    }

    /**
     * Get the number of naked pair reductions that were performed
     * in solving this puzzle.
     */
    int getNakedPairCount(){
        return (
            getLogCount(solveInstructions, LogItem.NAKED_PAIR_ROW) +
            getLogCount(solveInstructions, LogItem.NAKED_PAIR_COLUMN) +
            getLogCount(solveInstructions, LogItem.NAKED_PAIR_SECTION)
         );
    }

    /**
     * Get the number of hidden pair reductions that were performed
     * in solving this puzzle.
     */
    int getHiddenPairCount(){
        return (
            getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_ROW) +
            getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_COLUMN) +
            getLogCount(solveInstructions, LogItem.HIDDEN_PAIR_SECTION)
        );
    }

    /**
     * Get the number of pointing pair/triple reductions that were performed
     * in solving this puzzle.
     */
    int getPointingPairTripleCount(){
        return (
            getLogCount(solveInstructions, LogItem.POINTING_PAIR_TRIPLE_ROW)+
            getLogCount(solveInstructions, LogItem.POINTING_PAIR_TRIPLE_COLUMN)
        );
    }

    /**
     * Get the number of box/line reductions that were performed
     * in solving this puzzle.
     */
    int getBoxLineReductionCount(){
        return (
            getLogCount(solveInstructions, LogItem.ROW_BOX)+
            getLogCount(solveInstructions, LogItem.COLUMN_BOX)
        );
    }

    /**
     * Get the number lucky guesses in solving this puzzle.
     */
    int getGuessCount(){
        return getLogCount(solveInstructions, LogItem.GUESS);
    }

    /**
     * Get the number of backtracks (unlucky guesses) required
     * when solving this puzzle.
     */
    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 {
        // Clear any existing puzzle
        for (int i=0; i<BOARD_SIZE; i++){
                puzzle[i] = 0;
        }
        reset();
    }

    boolean generatePuzzle() throws Exception {

        // Don't record history while generating.
        boolean recHistory = recordHistory;
        setRecordHistory(false);
        boolean lHistory = logHistory;
        setLogHistory(false);

        clearPuzzle();

        // Start by getting the randomness in order so that
        // each puzzle will be different from the last.
        shuffleRandomArrays();

        // Now solve the puzzle the whole way.  The solve
        // uses random algorithms, so we should have a
        // really randomly totally filled sudoku
        // Even when starting from an empty grid
        solve();

        // Rollback any square for which it is obvious that
        // the square doesn't contribute to a unique solution
        // (ie, squares that were filled by logic rather
        // than by guess)
        rollbackNonGuesses();

        // Record all marked squares as the puzzle so
        // that we can call countSolutions without losing it.
        for (int i=0; i<BOARD_SIZE; i++){
            puzzle[i] = solution[i];
        }

        // Rerandomize everything so that we test squares
        // in a different order than they were added.
        shuffleRandomArrays();

        // Remove one value at a time and see if
        // the puzzle still has only one solution.
        // If it does, leave it0 out the point because
        // it is not needed.
        for (int i=0; i<BOARD_SIZE; i++){
            // check all the positions, but in shuffled order
            int position = randomBoardArray[i];
            if (puzzle[position] > 0){
                // try backing out the value and
                // counting solutions to the puzzle
                int savedValue = puzzle[position];
                puzzle[position] = 0;
                reset();
                if (countSolutions(2, true) > 1){
                    // Put it back in, it is needed
                    puzzle[position] = savedValue;
                }
            }
        }

        // Clear all solution info, leaving just the puzzle.
        reset();

        // Restore recording history.
        setRecordHistory(recHistory);
        setLogHistory(lHistory);

        return true;
    }

    void rollbackNonGuesses(){
        // Guesses are odd rounds
        // Non-guesses are even rounds
        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); //->push_back(l);
            solveInstructions.add(l); //->push_back(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 {
        // Don't record history while generating.
        boolean recHistory = recordHistory;
        setRecordHistory(false);
        boolean lHistory = logHistory;
        setLogHistory(false);

        reset();
        int solutionCount = countSolutions(2, false);

        // Restore recording history.
        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