//
//  SudokuGrid.java
//  Sudoku
//
//  Created by Perette Barella on 2006-07-31.
//  Copyright 2006 Perette Barella. All rights reserved.
//

import java.util.*;

/**
 * A simple class to contain sudoku cell coordinates.
 */
class Coordinates {
	/** The column number of the cell */
	public int column;
	/** The row number of the cell */
	public int row;
	
	Coordinates (int c, int r) {
		column = c;
		row = r;
	}
}

/**
 * Sudoku grid access methods.
 */
enum AccessMethod {
	BY_ROW,
	BY_QUAD_ROW,
	BY_COLUMN,
	BY_QUAD_COLUMN
};

/**
 * Sudoku engine for square grids of up to 64x64.  Stores numbers in the grid
 * and monitors possibilities throughout the grid.  Translates between
 * coordinate systems, allowing resolver methods to analyze columns/rows/quadrants
 * from a single implementation.
 * <p>
 * <b>Terminology:</b>
 * <dl>
 * <dt>cell</dt><dd>A single element within the grid, capable of holding one value.</dd>
 * <dt>sudoku grid</dt><dd>The whole grid.<dd>
 * <dt>quad<dt><dt>quadrant</dt><dd>A subsection of the sudoku grid.  The length of
 *		an edge is the square root of the length of the sudoku grid.  Technically,
 *		a quadrant would be one-fourth of the grid.  However, terms such as <i>block</i>
 *		can be confusing as to whether they refer to a cell or a quadrant; quadrant
 *		clearly distinguishes between the two.
 * </dl>
 * @author	Perette Barella
 * @version	$Id: SudokuGrid.java,v 1.3 2006/08/04 23:47:20 perette Exp $
 */
class SudokuGrid {
	/** The number of cells along one edge of the sudoku grid. */
	private int gridSize;
	/** The number of cells along one edge of one quadrant within the sudoku grid. */
	private int quadSize;
	/** The known values within the sudoku grid. */
	private int griddata [][];
	/** The possibilities for each value within the sudoku grid.  A single bit set means
		that cell can only contain a single value.  Multiple bits indicate which values
		may still potentially fit.  A zero indicates a contradiction, and that the
		sudoku is invalid. */
	private long possibilities [][];
	/** The manner of accessing the cells within the sudoku grid. */
	private AccessMethod accessMode = AccessMethod.BY_ROW;
	/** The group number that is being accessed via the <tt>accessMode</tt>.  This
		is a row, column, or quadrant number. */
	private int groupNumber = 0;
	/** Flag to enable debug output for this class. */
	private boolean debug = false;
	
	/**
	 * Instantiate and initialize the grid.
	 * @param	quad	The size of a sudoku grid quadrant.
	 *					For example, 3 results in a 9*9 Sudoku grid.
	 */
	SudokuGrid (int quad) {
		quadSize = quad;
		gridSize = quad * quad;
		griddata = new int[gridSize][gridSize];
		possibilities = new long [gridSize][gridSize];
		
		for (int y = 0; y < gridSize; y++) {
			for (int x = 0; x< gridSize; x++) {
				possibilities [x][y] = (1 << gridSize) - 1;
			}
		}
	}

	/**
	 * Create a new sudoku sudoku grid.
	 * @param grid		The values with which to fill the grid.
	 * 
	 */
	SudokuGrid (int [][] grid) {
		// figure out the size of the grid the user sent us.
		quadSize = 1;
		while (quadSize * quadSize < grid.length) {
			quadSize++;
		}
		gridSize = quadSize * quadSize;
		// Validate the grid the user sent us.
		if (gridSize != grid.length) {
			System.out.println ("Invalid grid: Improper size.");
			System.exit (1);
		}
		for (int row = 0; row < gridSize; row++) {
			if (gridSize != grid [row].length) {
				System.out.println ("Invalid grid: Improper size: row=" + row);
				System.exit (1);
			}
		}
		// Initialize griddata and possibilities
		griddata = new int[gridSize][gridSize];
		possibilities = new long [gridSize][gridSize];
		for (int y = 0; y < gridSize; y++) {
			for (int x = 0; x< gridSize; x++) {
				possibilities [x][y] = (1 << gridSize) - 1;
			}
		} 
		// Transcribe the array into the grid.
		// We could just duplicate the array, but then we'd need to
		// fight to set up the possibilities array so it's easier to
		// just transcribe the array in entry-by-entry.
		setAccessMode (AccessMethod.BY_ROW);
		for (int y = 0; y < gridSize; y++) {
			setGroupNumber (y);
			for (int x = 0; x < gridSize; x++) {
				setValue (x, grid [y][x]);
			}
		}
	}
	
	/**
	 * Generate a string containing the current state of the grid.
	 * @return	The known values grid and possibilities grid. 
	 */
	public String toString () {
		String result = "", possibs = "";
		int x, y;
		for (y = 0; y < gridSize; y++) {
			if (y > 0 && (y % quadSize) == 0) {
				result += "------+-------+------\n";
				possibs += "---------------+----------------+---------------\n";
			}
			for (x = 0; x < gridSize; x++) {
				if (x > 0 && (x % quadSize) == 0) {
					result += "| ";
					possibs += "| ";
				}
				result += Integer.toHexString (griddata [x][y]) + " ";
				StringBuffer possibility = new StringBuffer (Long.toHexString (possibilities [x][y]));
				while (possibility.length() < 4) {
					possibility.insert (0, ' ');
				}
				possibs += possibility + " ";
			}
			result += "\n";
			possibs += "\n";
		}
		return ("sudoku:\n" + result + "possibilities:\n" + possibs);
	}
	
	/**
	 * Sets the access mode for the grid (by row, by column, by quadrant).
	 * Which row/column/quadrant to access is set by <tt>setGroupNumber</tt>, and
	 * the cell within the group is chosen when calling <tt>getValue</tt>
	 * or <tt>getPossibilities</tt>.
	 * @param	mode	The new access mode.
	 */
	public void setAccessMode (AccessMethod mode) {
		accessMode = mode;
	}
	
	/**
	 * Set the group number for grid access.  Which manner of access (by row,
	 * by column, or by quadrant) of group is set by <tt>setAccessMode</tt>.
	 * @param	group	Which row/column/quadrant to access.
	 */
	public void setGroupNumber (int group) {
		assert (group >= 0 && group < gridSize) : "Invalid group " + group + " passed to setGroupNumber";
		groupNumber = group;
	}
	
	/**
	 * Given an item number, uses the values set by <tt>setAccessMode</tt> and
	 * <tt>setGroupNumber</tt>, determines the array coordinates to interact
	 * with.  This translates from the logical access method to the
	 * physical access method.  Rows are numbered starting with 0 at the left;
	 * within rows cells are numbered left to right.
	 * Columns are numbered with 0 at the top; within columns cells are numbered
	 * top to bottom.  Grids are numbered as follows:
	 * <pre>
	 * 0|1|2
	 * -----
	 * 3|4|5
	 * -----
	 * 6|7|8
	 * </pre>
	 * When accessing by quadrant by row, cells are accessed similarly; but when accessing
	 * by quadrant by column cells are numbered this way:
	 * <pre>
	 * 0|3|6
	 * -----
	 * 1|4|7
	 * -----
	 * 2|5|8
	 * </pre>
	 @param	cellNumber	The item number to access.
	 @return			A <tt>Coordinates</tt> object containing the array coordinates.
	 */
	protected Coordinates getCoordinates (int cellNumber) {
		int column, row;
		switch (accessMode) {
			case BY_ROW:
			default:
				// access by row
				column = cellNumber;
				row = groupNumber;
				break;
			case BY_COLUMN:
				// access by column
				row = cellNumber;
				column = groupNumber;
				break;
			case BY_QUAD_ROW:
				// access by subsection of the grid, line by line.
				column = (groupNumber % quadSize) * quadSize + cellNumber % quadSize;
				row = (groupNumber / quadSize) * quadSize + cellNumber / quadSize;
				break;
			case BY_QUAD_COLUMN:
				// access by subsection of the grid, column by column.
				column = (groupNumber % quadSize) * quadSize + cellNumber / quadSize;
				row = (groupNumber / quadSize) * quadSize + cellNumber % quadSize;
				break;
		}
		Coordinates coord = new Coordinates (column, row);
		return (coord);
	}
	
	/**
	 * Get the size of the grid.
	 * @return			The number of cells along one edge of the sudoku grid.
	 */
	public int getGridSize () {
		return gridSize;
	}
	
	/**
	 * Get the size of a quadrant of the grid.
	 * @return			The number of cells along one edge of a quadrant.
	 */
	public int getQuadSize () {
		return quadSize;
	}
	
	/**
	 * Get a value from the grid.  The current access mode and group
	 * are used along with the method's parameter to determine which value
	 * to return.
	 * @param cellNumber	The cell number to retreive.
	 * @return				The value for the cell, or 0 if it's not determined.
	 */
	public int getValue (int cellNumber) {
		Coordinates coord = getCoordinates (cellNumber);
		return (griddata [coord.column][coord.row]);
	}
	
	/**
	 * Get the possibilities from the grid.  The current access mode and group
	 * and method parameter are used to determine which cell for which to
	 * return data.
	 * @param cellNumber	The cell number to retreive.
	 * @return				The possibilities for the cell, which is a bitmask.
	 */
	public long getPossibilities (int cellNumber) {
		Coordinates coord = getCoordinates (cellNumber);
		return (possibilities [coord.column][coord.row]);
	}
	
	
	/**
	 * Get the positions in which a value may fit.  The current access mode and
	 * group are used to determine which cells to search for potential locations
	 * the the value.
	 * @param value		The value to retrieve positions for.
	 * @return			A bitmask representing positions in which a value may
	 *					potentially fit.
	 */
	public long getPositions (int value) {
		long mask = 0;
		long bit = 1 << value;
		for (int x = 0; x < gridSize; x++) {
			if ((getPossibilities (x) & bit) != 0) {
				mask |= (1 << x);
			}
		}
		return (mask);
	}
		
	 
	/**
	 * Set a value in the grid.  An existing value can not be changed.
	 * The possibilities are updated, eliminating the value set, in the
	 * row, column, and quadrant in which the value is inserted.
	 * @param	cellNumber		The item number to update.
	 * @param	value			The new value for the box.
	 */
	public void setValue (int cellNumber, int value) {
		// ignore setting unknown values to unknown
		if (value == 0) {
			return;
		}
		
		// Make sure the value we've gotten passed is valid
		assert (value >= 1 && value <= gridSize) : "setValue: Invalid value passed = " + value;
		
		// Figure out where this value goes.
		Coordinates coord = getCoordinates (cellNumber);
		
		// Make sure we're not modifying an existing value in the grid		
		assert (griddata [coord.column][coord.row] == 0) :
			"Data already present in grid [" + coord.column + ", " + coord.row + "] = "
			+ griddata [coord.column][coord.row]
			+ "; can't set to " + value + "\n" + toString ();
		
		// Update the data in the grid
		griddata [coord.column][coord.row] = value;
		
		// Okay, now eliminate this option from possiblities table.
		long bit = 1 << (value - 1);
		for (int lcv = 0; lcv < gridSize; lcv++) {
			possibilities [coord.column][lcv      ] &= (~bit);
			possibilities [lcv         ][coord.row] &= (~bit);
			possibilities [(coord.column / quadSize) * quadSize + lcv / quadSize]
						  [(coord.row    / quadSize) * quadSize + lcv % quadSize] &= (~bit);
		}
		possibilities [coord.column][coord.row] = bit;
	}
	
	/**
	 * Eliminate several values from a single cell in the possibilities table.
	 * @param cellNumber		The cell number to eliminate values from.
	 * @param mask				The possibilities to eliminate, as a bitmask.
	 * @return					Returns <tt>true</tt> when elimination was successful.
	 */
	 protected boolean eliminate (int cellNumber, long mask) {
		boolean changed = false;
		Coordinates coord = getCoordinates (cellNumber);
		if ((possibilities [coord.column][coord.row] & mask) != 0) {
			possibilities [coord.column][coord.row] &= ~mask;
			return (true);
		}
		return (false);
	 }
	 
	
	/**
	 * Eliminate a single value from several cells in possibilities table.
	 * @param startCell		The starting cell number.
	 * @param endCell		The ending cell number.
	 * @param value			The value to be eliminated.
	 * @return				Returns <tt>true</tt> if changes have been made to possibilities data.
	 */
	 boolean eliminate (int startCell, int endCell, int value) {
		if (debug) {
			System.out.print ("eliminate " + accessMode + ", group=" + groupNumber + ", items {" + startCell + "," + endCell + "} value=" + value + ": ");
		}
		long bit = 1 << (value - 1);
		boolean changed = false;
		for (int cellNumber = startCell; cellNumber <= endCell; cellNumber++) {
			Coordinates coord = getCoordinates (cellNumber);
			if ((possibilities [coord.column][coord.row] & bit) != 0) {
				changed = true;
				possibilities [coord.column][coord.row] &= ~bit;
				if (debug) {
					System.out.print (" {" + coord.column + "," + coord.row + "}");
				}
			}
		}
		if (debug) {
			System.out.println (changed ? "Yay!" : "");
		}
		return (changed);
	 }
}