ConstrainedGroup represents a group of squares within a
* Sudoku Board. Each square within the group must have a unique
* value. The primary task of a ConstrainedGroup is to track the
* mappings from values to squares.
*
* For every value that must be present in the group, the
* ConstrainedGroup keeps track of the squares that can possibly
* hold that value. (In other words, ConstrainedGroup tracks
* mappings from values to possible squares. Compare this with the
* Square class, which tracks the mapping from a particular square
* to a set of possible values.) When there is exactly one possible square for
* a value, the value of that square becomes "known." The Square
* object that represents the known square can be set, and the possible values
* of all the other Squares in the group can be constrained.
* Furthermore, whenever a square in the group becomes known, that square can
* be removed from the sets of squares that might hold other values. In these
* ways, the effects of updates and constraints are propagated to
* Squares. (The Squares, in turn, propagate their
* updates to the Solver for the Board.)
*
*
ConstrainedGroup is the superclass for classes that
* represent particular kinds of groups on a Sudoku board: i.e., rows, columns,
* and blocks. Although the shapes of the various groups are different, all
* groups share the rule that every member of the group must have a unique
* value. The purpose of the ConstrainedGroup class is to capture
* and implement that rule.
*/
public abstract class ConstrainedGroup {
/**
* The Board to which this group belongs.
*/
protected final Board board;
/**
* The mappings from square values to the indices of squares that may
* contain those values.
*
*
The possibleSquares array is indexed by possible square
* values, i.e., integers between {@link Square.MIN_SQ_VALUE} and
* {@link Square.MAX_SQ_VALUE} inclusive. For a given value
* n, the value of possibleSquares[n] is a set
* that describes the squares in the group that can possibly hold the value
* n. Squares are identified by "index" within a
* ConstrainedGroup, not by their row and column coordinates
* on the Sudoku board. Thus, the value of possibleSquares[n]
* is a set of indices.
*
*
The method {@link #getSquare(int)} returns the First, this method removes the known square from the sets of squares
* that might hold other values. This might cause the locations of some
* other values to become known, in which case the appropriate
* Second, this method tells the other To handle this kind of update, this method only needs to remove the
* updated square from the set of squares that might hold the indicated
* value. This might cause the location of that value to become known, in
* in which case the appropriate Square
* for a given index.
*/
protected final BitSet[] possibleSquares;
/*************************************************************************/
/**
* Creates a new ConstrainedGroup. The group is initialized
* to indicate that every square value may be contained in any square
* within the group. In other words, nothing is known about the assignment
* of values to squares.
*
* @param board the Board to which this group belongs
*/
public ConstrainedGroup(Board board) {
this.board = board;
possibleSquares = new BitSet[Square.MAX_SQ_VALUE + 1];
for (int i = Square.MIN_SQ_VALUE; i <= Square.MAX_SQ_VALUE; ++i) {
BitSet bs = new BitSet(Board.BOARD_SIZE);
bs.set(0, Board.BOARD_SIZE);
possibleSquares[i] = bs;
}
}
/**
* Returns the index for the square that is described by the given
* Update. Essentially, this is a mapping from row and column
* coordinates to a single number that identifies the square within the
* ConstrainedGroup.
*
* @param u the Update to be examined
* @return the index of the updated square within this group
*/
protected abstract int updateToIndex(Update u);
/**
* Returns the Square that is identified by the given index
* number within the ConstrainedGroup. Essentially, this is a
* mapping from a (single) identifying number to row and column
* coordinates.
*
* @param index the index number
* @return the Square corresponding to the index
*/
protected abstract Square getSquare(int index);
/**
* Processes an Update that affects this group. This method
* simply dispatches the update to one of two helper methods,
* {@link #processIs} and {@link processIsNot}, according to the type of
* the update.
*
* @param u the Update to be dealt with
* @param solver the Solver that will be notified in case
* the processing of u causes more updates
*/
public void processUpdate(Update u, Solver solver) {
switch (u.type) {
case Update.IS:
processIs(u, solver);
break;
case Update.IS_NOT:
processIsNot(u, solver);
break;
default:
System.err.println("error: unrecognized Update type ignored");
break;
}
}
/**
* Processes an "is" Update that affects this group. An "is"
* update says that a square's value has become known. To handle this kind
* of update, this method does two things.
*
* Squares are set (via {@link Square#setTo(int, Solver)}).
*
* Square in the group
* that they cannot hold the known square's value (via
* {@link Square#constrainFrom(int, Solver)}).
*
* @param u the Update to be dealt with
* @param solver the Solver that will be notified in case
* the processing of u causes more updates
*
* @see #processIsNot(Update, Solver)
*/
private void processIs(Update u, Solver solver) {
// Update this group's `possibleSquares' sets, and notify Squares as
// appropriate.
for (int i = Square.MIN_SQ_VALUE; i <= Square.MAX_SQ_VALUE; ++i) {
int updatedSqIndex = updateToIndex(u);
if (i != u.value) {
// If the updated square appears as a possible square for value
// `i', remove it from the possibleSquares set for `i'.
if (possibleSquares[i].get(updatedSqIndex) == true) {
possibleSquares[i].clear(updatedSqIndex);
// If there is only one possible square for value `i', set
// that square.
//
// Note that we don't have to update our `possibleSquares'
// sets for this newly discovered fact. Setting the square
// will cause an update for (row, col, IS, i) to be posted,
// and we'll catch up when we process that.
if (possibleSquares[i].cardinality() == 1) {
int knownSqIndex = possibleSquares[i].nextSetBit(0);
Square knownSq = getSquare(knownSqIndex);
knownSq.setTo(i, solver);
}
}
} else {
// At this point, `i' is equal to `u.value'.
// Remember what squares could have held value `i'.
BitSet couldHaveBeenSquares
= (BitSet) possibleSquares[i].clone();
// Change the set of possible squares for value `i' to contain
// just the one square that actually holds that value.
possibleSquares[i].clear();
possibleSquares[i].set(updatedSqIndex);
// Tell all the other candidate squares that they cannot have
// value `i'.
for (int j = 0; j < Board.BOARD_SIZE; ++j) {
if ((j != updatedSqIndex)
&& (couldHaveBeenSquares.get(j) == true)) {
Square sq = getSquare(j);
sq.constrainFrom(i, solver);
}
}
}
}
}
/**
* Processes an "is-not" Update that affects this group. An
* "is-not" update says that a square cannot contain a particular
* value.
*
* Square is set (via
* {@link Square#setTo(int, Solver)}).
*
* @param u the Update to be dealt with
* @param solver the Solver that will be notified in case
* the processing of u causes more updates
*
* @see #processIs(Update, Solver)
*/
private void processIsNot(Update u, Solver solver) {
// TODO: implement this method! (About ten lines of code.)
//
// Here's a description of what needs to be done:
//
// From the value in the update (`u.value'), find the `possibleSquares'
// set that describes where that value can go within this group. Call
// that set S.
//
// If the square described in `u' is not in S, then the update isn't
// "news." In this case, you're done. Return from this method.
//
// Otherwise, remove the indicated square from S.
//
// Now, if S only contains one square index, we've learned something!
// In particular, we've learned where the value `u.value' needs to go
// in this group.
//
// If S contains only one square index, get the Square object for that
// index. Tell that Square that its value must be `u.value'.
}
}
// End of file.