//
//  sudoku.java
//  sudoku solver
//
//  Created by Perette Barella on 2006-06-06.
//  Copyright (c) 2006 Perette Barella. All rights reserved.
//	$Id: SudokuResolver.java,v 1.5 2006/08/08 03:25:21 perette Exp $
//

import java.util.*;


/**
 * Status data for each sudoku algorithm.
 */
class ResolverStatus {
	/** Was the algorithm enabled during the run? */
	boolean enabled = true;
	/** How many times did the algorithm run? */
	int groupsAnalyzed;
	/** How many times did the algorithm make progress?
		Progress made may vary widely -- it could be elimination of a single possibility,
		or eliminating several values to result at a conclusion. */
	int reductionsMade;
}

/**
 * Analyzer for sudoku grids, determining values which can be
 * concluded from existing values.  Monitors for contradictions; <tt>isGridValid</tt>
 * can be used to determine if the grid is valid.  Algorithms can be enabled
 * and disabled, and statistics on execution and performance of each algorithm
 * are collected.
 */
class SudokuResolver extends SudokuGrid {
	/** The number of algorithms implemented in the Sudoku resolver. */
	public static final int NUMBER_OF_ALGORITHMS = 6;
	/** Names for each of the resolver algorithms. */
	public static final String[] ALGORITHM_NAME = {
		"Singles",
		"Locked candidates",
		"Hidden pairs",
		"Naked pairs",
		"Cyclical groups",
		"X-wing"
	};
	
	/** Flag for the grid validity. */
	private boolean gridIsValid = true;
	/** Flag for when the grid is completed. */

	private boolean gridIsComplete = false;
	/** Algorithm performance data. */	
	public ResolverStatus status [] = new ResolverStatus [NUMBER_OF_ALGORITHMS];
	{
		// Initialize the performance data, enabling all the resolvers.
		for (int x= 0; x < status.length; x++) {
			status [x] = new ResolverStatus ();
		}
	}

	/** Number of bits worth of data stored in the bit counting table. */
	private static final int BIT_TABLE_NUMBER_OF_BITS = 9;
	/** Maximum entry number in bit counting table. */
	private static final int BIT_TABLE_MAX = (1 << BIT_TABLE_NUMBER_OF_BITS) - 1;
	/** Table of number of 1 bits in various binary values. */
	private static int possiBitCount [] = new int [BIT_TABLE_MAX + 1];
	static {
		// Initialize the value-to-set-bits map.
		for (int x = 0; x < possiBitCount.length; x++) {
			int count = 0;
			for (int y = 1; y <= x; y <<= 1) {
				if ((x & y) != 0) {
					count ++;
				}
			}
			possiBitCount [x] = count;
		}
	}
	
	
	
	/**
	 * Create a new sudoku resolver with all algorithms enabled.
	 * @param grid	The sudoku to resolve.
	 */
	SudokuResolver (int [][] grid) {
		super (grid);
		
		// Try to resolve.
		resolve ();
	}
	
	/**
	 * Create a new sudoku resolver, selecting algorithms.
	 * Disabling algorithm A (basic elimination) will cause unpredictable
	 * results.
	 * @param grid		The sudoku to resolve.
	 * @param active	A <tt>boolean [NUMBER_OF_ALGORITHMS]</tt> array,
	 *					each value representing a corresponding algorithm.
	 */
	SudokuResolver (int [][] grid, boolean [] active) {
		super (grid);
		assert (NUMBER_OF_ALGORITHMS == active.length);
		for (int x = 0; x < active.length; x++) {
			status [x].enabled = active [x];
		}
		resolve ();
	}

	/**
	 * Count the possibilities indicated by a value.
	 * The value is a bitmask, and a 1 represents a possible value.
	 * Look up the number in the table, but if <tt>possibility</tt> is
	 * more than <tt>BIT_TABLE_NUMBER_OF_BITS</tt> long then loop through looking
	 * up <tt>BIT_TABLE_NUMBER_OF_BITS</tt> in each iteration.
	 * @param possibility	The possibility mask.
	 * @return				The number of possibilities represented by the mask.
	 * 
	 */
	 private int getPossibleCount (long possibility) {
		int count = 0;
		while (possibility != 0) {
			count += possiBitCount [(int) (possibility & BIT_TABLE_MAX)];
			possibility >>>= BIT_TABLE_NUMBER_OF_BITS;
		}
		return (count);
	 }

	
	/**
	 * Convert from a possibilities mask to a specific value, if possible.
	 * Exactly one bit in the mask must be set for this to succeed.
	 * @param possibility	The possibilities mask.
	 * @return				The value indicated by the mask, or 0 if a
	 *						singular value is not indicated.
	 */
	private int getValueFromPossibilities (long possibility) {
		if (getPossibleCount (possibility) == 1) {
			for (int z = 0; z < getGridSize (); z++) {
				if (possibility == (1 << z)) {
					return (z + 1);
				}
			}
			assert false : "Statement should be unreachable";
		}
		return (0);
	}
	
	/**
	 * Analyze the grid from each of the perspectives: column, row, quadrant.
	 * Invoke increasingly complex resolvers if a given algorithm isn't
	 * making progress.
	 */
	private void resolve () {
		boolean changed;

		do {
			changed = false;
			for (AccessMethod m : AccessMethod.values()) {
				setAccessMode (m);
				gridIsComplete = true;
				for (int group = 0; group < getGridSize (); group++) {
					setGroupNumber (group);
					for (int algorithm = 0; algorithm < NUMBER_OF_ALGORITHMS; algorithm++) {
						if (!status [algorithm].enabled)
							continue;
						boolean progress = false;
						switch (algorithm) {
							case 0: progress = solutionA (); break;
							case 1: progress = solutionB (m, group); break;
							case 2: progress = solutionC (); break;
							case 3: progress = solutionD (); break;
							case 4: continue;
							case 5: continue;
							default:  assert false: "Statement shouldn't be reached.";
						}
						status [algorithm].groupsAnalyzed++;
						if (progress) {
							status[algorithm].reductionsMade++;
							// If we made progress, then the grid changed:
							// Don't move onto harder resolvers.
							changed = true;
							break;
						}
					}
				}
				if (gridIsComplete) {
					break;
				}
				if (!changed && status [5].enabled) {
					status [5].groupsAnalyzed++;
					changed = solutionF (m);
					if (changed) {
						status [5].reductionsMade++;
					}
				}
			}
		} while (changed && !gridIsComplete);
	}

	/**
	 * Simple deduction and elimination:
	 * Scan the grid and try to determine some values.  Two techniques
	 * are used: 1. If there is only one possible value left for a particular
	 * location, and 2. if a value only fits in one possible location.
	 * Either one results in the value being inserted into the grid.
	 * @return			Returns <tt>true</tt> if eliminations were successful.

	 */
	private boolean solutionA () {
		long possibility;
		boolean change = false;

		for (int x = 0; x < getGridSize (); x++) {
			possibility = getPossibilities (x);
			// If there's no possibilities left, the grid is invalid.
			if (possibility == 0) {
				gridIsValid = false;
			}
			if (getValue (x) == 0) {
				// This position still needs to be resolved.
				// First, see if only one value fits in this box.
				int newValue = getValueFromPossibilities (possibility);
				// Next, see if one of the values only fits in this box.
				if (newValue == 0) {
					for (int z = 0; z < getGridSize (); z++) {
						if (z != x) {
							possibility = possibility & ~(getPossibilities (z));
						}
					}
					newValue = getValueFromPossibilities (possibility);
				}
				if (newValue == 0) {
					gridIsComplete = false;
				} else {
					setValue (x, newValue);
					change = true;
				}
			}
		}
		return (change);
	}
	
	/**
	 * Try to eliminate some possibilities in the grid.  This does not
	 * result in any values being placed (although placement may happen
	 * during the next simple elimination cycle).
	 * The idea here is that if we know the row or column within a
	 * quadrant that contains a value (either because it doesn't fit anywhere
	 * else in that row, column, or quad), then it must occur there and
	 * not elsewhere in the row or column that is outside the quadrant.
	 * @param manner	The manner of scanning the grid.
	 * @param group		The group number for processing.
	 * @return			Returns <tt>true</tt> if eliminations were successful.
	 */
	private boolean solutionB (AccessMethod manner, int group) {
		boolean change = false;
		for (int z = 1; z <= getGridSize (); z++) {
			long bit = 1 << (z - 1);
			long possibleLocations = 0;
			int x;
			
			for (x = 0; x < getGridSize (); x++) {
				if (getValue (x) == z) {
					break;
				}
				if ((getPossibilities (x) & bit) != 0) {
					possibleLocations |= 1 << (x / getQuadSize ());
				}
			}
			if (x >= getGridSize ()) {
				// System.out.println ("thinkHard: " + manner + " y = " + y + ", z = " + z + ", possibleLocations=" + Long.toHexString (possibleLocations));
				int location = getValueFromPossibilities (possibleLocations);
				if (location > 0) {
					location --;
					int safetyStart = -1;
					AccessMethod newMode;
					int newGroup;
					Coordinates coord = getCoordinates (location * getQuadSize());
					// System.out.println ("thinkHard " + manner + ", y=" + y + ", value=" + z + " : coords = {" + coord.column + "," + coord.row + "}");
					switch (manner) {
						case BY_ROW:
							newMode = AccessMethod.BY_QUAD_ROW;
							newGroup = (coord.row / getQuadSize ()) * getQuadSize() +
									   (coord.column / getQuadSize ());
							safetyStart = (coord.row % getQuadSize ()) * getQuadSize();
							break;
						case BY_QUAD_ROW:
							newMode = AccessMethod.BY_ROW; 
							newGroup = coord.row; 
							safetyStart = (coord.column / getQuadSize ()) * getQuadSize();
							break;
						case BY_COLUMN:
							newMode = AccessMethod.BY_QUAD_COLUMN; 
							newGroup = (coord.row / getQuadSize ()) * getQuadSize() +
									   (coord.column / getQuadSize ());
							safetyStart = (coord.column % getQuadSize ()) * getQuadSize();
							break;
						case BY_QUAD_COLUMN:
							newMode = AccessMethod.BY_COLUMN; 
							newGroup =  (coord.column); 
							safetyStart = (coord.row / getQuadSize ()) * getQuadSize();
							break;
						default:
							assert false : "Shouldn't get here.";
							newMode = AccessMethod.BY_COLUMN;
							newGroup = -1;
					}
					setAccessMode (newMode);
					setGroupNumber (newGroup);
					if (eliminate (0, safetyStart - 1, z)) {
						change = true;
					}
					if (eliminate (safetyStart + getQuadSize (), getGridSize () - 1, z)) {
						change = true;
					}
					setAccessMode (manner);
					setGroupNumber (group);
				}
			}
		}
		return (change);
	}



	/**
	 * Store intermediate data for solution method C (hidden pairs).
	 */
	class Cinfo {
		/** A bitmask containing a value for which placement is sought. */
		long value;
		/** The possible locations in which that value can fit. */
		long locations;
		Cinfo (long value, long locations) {
			this.value = value;
			this.locations = locations;
		}
	}
	
	/**
	 * Hidden pairs:
	 * Look at a row in the solution grid to see if there is a number
	 * that occurs only twice in the row. If the cells they occur in
	 * match identically with another number that satisfies this criterion,
	 * then those cells must contain that number pair - so eliminate the
	 * other options in those cells. Again, this is repeated for columns
	 * and blocks. This method is also repeated for triplets and upwards.
	 * (http://www.sudokusolver.co.uk/solvemethods.html)
	 *
	 * Stated more generically:
	 * Look for N numbers that occur in N cells in a group.  If all N
	 * numbers occur only within the N cells of that group, then those
	 * cells must contain all N numbers (and therefore not any others).
	 *
	 * Note that each number need not occur N times; it may occur in
	 * only a subset of the cells.
	 * @return			Returns <tt>true</tt> if eliminations were successful.
	 */
	private boolean solutionC () {
		boolean changed = false;
		Cinfo[] possiGroup = new Cinfo[getGridSize ()];
		int entries = 0;
		// Gather the possibilities & locations for incomplete cells
		for (int x = 0; x < getGridSize (); x++) {
			long where = getPositions (x);
			if (getPossibleCount (where) > 1) {
				possiGroup [entries++] = new Cinfo (1 << x, where);
			}
		}
		// Permute over all combinations of the data we collected.
		int permutations = 1 << entries;
		for (int permute = 1; permute < permutations; permute++) {
			long combinedValue = 0;
			long combinedLocations = 0;
			int count = 0;
			for (int x = 0; x < entries; x++) {
				if ((permute & (1 << x)) != 0) {
					combinedValue |= possiGroup [x].value;
					combinedLocations |= possiGroup [x].locations;
					count++;
				}
			}
			if (count == getPossibleCount (combinedLocations)) {
				// The number of values needing homes equals the number of open cells accomodating them.
				for (int x = 0; x < getGridSize (); x++) {
					// Where these values fit
					if (((1 << x) & combinedLocations) != 0) {
						// Eliminate everything that's not one of the values.
						if (eliminate (x, ~combinedValue)) {
							changed = true;
						}
					}
				}
			} else if (getPossibleCount (combinedLocations) < count) {
				// There are fewer open cells than values to fit in them -- something is wrong.
				gridIsValid = false;
			}
		}
		return (changed);
	}



	/**
	 * Store intermediate data for solution method D (naked pairs).
	 */
	class Dinfo {
		/** The possibilities available for a cell */
		long possibilities;
		/** A bitmask representing the location of the cell. */
		long location;
		Dinfo (long location, long possibilities) {
			this.possibilities = possibilities;
			this.location = location;
		}
	}

	/**
	 * Naked pairs:
	 * Look at a row in the solution grid to see if there is a group of N
	 * cells which contain only N possible numbers. If such a 'chain' exists,
	 * then those cells must contain these numbers, so we can eliminate these
	 * numbers from other cells in the row.
	 * (from http://www.sudokusolver.co.uk/solvemethods.html)
	 *
	 * Note: Cells with the set of numbers need not have every number in the set.
	 * @return			Returns <tt>true</tt> if eliminations were successful.
	 */
	private boolean solutionD () {
		boolean changed = false;
		Dinfo[] possiGroup = new Dinfo[getGridSize ()];
		int entries = 0;
		// Gather the possibilities & locations for incomplete cells
		for (int x = 0; x < getGridSize (); x++) {
			if (getValue (x) == 0) {
				possiGroup [entries++] = new Dinfo (1 << x, getPossibilities (x));
			}
		}
		// Permute over all combinations of the data we collected.
		int permutations = 1 << entries;
		for (int permute = 1; permute < permutations; permute++) {
			long combinedPossi = 0;
			long combinedLocation = 0;
			int count = 0;
			for (int x = 0; x < entries; x++) {
				if ((permute & (1 << x)) != 0) {
					combinedPossi |= possiGroup [x].possibilities;
					combinedLocation |= possiGroup [x].location;
					count++;
				}
			}
			if (count == getPossibleCount (combinedPossi)) {
				// The number of empty cells equals the number of things that fit in them.
				for (int x = 0; x < getGridSize (); x++) {
					// In any of the cells that aren't part of the group we found...
					if (((1 << x) & combinedLocation) == 0) {
						// eliminate the values that are in our set.
						if (eliminate (x, combinedPossi)) {
							changed = true;
						}
					}
				}
			} else if (getPossibleCount (combinedPossi) < count) {
				// There is less stuff than cells for it -- something is wrong.
				gridIsValid = false;
			}
		}
		return (changed);
	}


	/**
	 * Store intermediate data for solution method D (naked pairs).
	 */
	class Finfo {
		/** A bitmask representing the group for the cells. */
		long group;
		/** The positions available for the value in the group */
		long positions;
		Finfo (long group, long positions) {
			this.group = group;
			this.positions = positions;
		}
	}

	/**
	 * X-wing / Jellyfish
	 * Look at a row in the solution grid to see if there is a value which
	 * potentially fits exactly the same N cells in N different rows/columns.
	 * Then the value must be in one of those N^2 locations, and thus is not
	 * possible in the other cells of the cross-hatched columns/rows.
	 *
	 * Note: The value need not be present in every cell in each row.  But
	 * it must not be in other cells for the set of rows chosen.
	 * @param manner	The manner of scanning the grid.
	 * @return			Returns <tt>true</tt> if eliminations were successful.
	 */
	private boolean solutionF (AccessMethod method) {	
		if (method != AccessMethod.BY_ROW && method != AccessMethod.BY_COLUMN) {
			return (false);
		}

		boolean changed = false;
		for (int value = 0; value < getGridSize (); value++) {
			// Collect the possible locations for each group.
			Finfo[] possiGroup = new Finfo[getGridSize ()];
			int entries = 0;
			for (int group = 0; group < getGridSize (); group++) {
				setGroupNumber (group);
				long positions = getPositions (value);
				if (getPossibleCount (positions) > 1 && getPossibleCount (positions) < getGridSize ()) {
					possiGroup [entries++] = new Finfo (1 << group, positions);
				}
			}

			// Permute over all combinations of the data we collected.
			int permutations = 1 << entries;
			for (int permute = 1; permute < permutations; permute++) {
				long combinedGroup = 0;
				long combinedPositions = 0;
				int count = 0;
				for (int x = 0; x < entries; x++) {
					if ((permute & (1 << x)) != 0) {
						combinedGroup |= possiGroup [x].group;
						combinedPositions |= possiGroup [x].positions;
						count++;
					}
				}
				if (count == getPossibleCount (combinedPositions)) {
					// The value fits in only in the same N cells of the groups
					// that we're permuting on, and therefore it must be in one
					// of these cells for the groups represented.  Eliminate it from
					// these cells of other groups.
					for (int elimGroup = 0; elimGroup < getGridSize (); elimGroup++) {
						if ((combinedGroup & (1 << elimGroup)) == 0) {
							// In the groups not in this permutation
							setGroupNumber (elimGroup);
							for (int elimCell = 0; elimCell < getGridSize (); elimCell++) {
								// In the cell positions in this permutation
								if ((combinedPositions & (1 << elimCell)) != 0) {
								// Eliminate everything the value.
									if (eliminate (elimCell, 1 << value)) {
										changed = true;
									}
								}
							}
						}
					} // end for elimGroup
				} // end if
			} // end permuting
		} // end looping over values
		return (changed);
	}

	/**
	 * Indicate if the resolved sudoku is (so far as we were able to tell) valid.
	 * @return	<tt>true</tt> if the Sudoku is not known to be invalid.
	 */
	public boolean isValid () {
		return gridIsValid;
	}
	
	/**
	 * Indicate if the resolved sudoku was resolved completely.
	 * @return	<tt>true</tt> if the Sudoku is complete.
	 */
	public boolean isComplete () {
		return gridIsComplete;
	}

	/**
	 * Convert the sudoku into string form.
	 * @return		A string containing the sudoku state.
	 */
	public String toString () {
		return (super.toString() + "\nComplete: " + gridIsComplete
				+ "\nValid: " + gridIsValid + "\n");
	}
}