211hw11_details_S11

Comp211 HW11  Supporting Code Details

Core Data Structures

 The main data structures are represented by only a few interfaces:

• ICell --  a single square on the Sudoku board.  
  • A cell has a set of integer values, which are accessible either as a HashSet<Integer>  or as an array of integers. 
  • A cell also has a collection (Vector<ICell>) of ICellSets to which it belongs.   These are the cell's row, column and block, in that order.
    • Don't forget that the cell is also a member of every ICellSet that it references.  
  • A cell can be in one of three logical states:
    • Empty - there are no values contained in the cell.   This corresponds to the situation where the board is unsolvable because a cell has no possible value.

    • Solved - the cell contains exactly one value.   If and only if you know for sure that the cell is in this state, then the single value can be accessed as aCell.getValueArray()[0].

    • Unsolved - the cell contains multiple possible values.   At most, a cell could contain order*order values.
  • Cell is a concrete implementation of ICell.
  • An ICell accepts an ICellVisitor which has cases for each of the 3 logical states, described above.
    • The ACellVisitor class is an abstract convenience class that provide a default return value for any cases that the developer does not which to override.   There is no requirement to use this class, though it may simplify certain code. 
• ICellSet -- A collection of ICells that represents a row, column or block. 
  •  For convenience sake, the cells are in a distinct order (i.e. left-to right for a row) and thus each cell is addressable by an index value.
  •  An ICellSet is Iterable which means that it can be used in for-each loops, e.g.

    for(ICell c : aCellSet) {
        ...
    }
    

• Board -- A set of 3 Vector<ICellSet>'s where each element of the vector is an ICellSet.   These vectors represent the entire set of rows, columns or blocks in a game. 
  • A Board has the ability to make a "deep" copy of itself, where everything, all the way down to the individual cells, is copied.  This is the clone() method.
  • The Board also has a utility method for generating empty cell sets, which is used during initialization. 
  • It should be noted that since every cell appears exactly once in each of the rows, cols, and blks Vectors of a Board, any of those 3 vectors will server equally well as a means to iterate over all the cells of a Board

Utility Data Structures Delegation-model programming and imperative (conditional and loop-based) programming have a fundamental incompatibility:   Delegation works by having code on the inside of an object (i.e. a method of that object) perform the object-specific processes.  On the other hand, imperative programming utilizes program structures (conditionals and loops) which are outside the object to perform object-specific processes.    This can cause major architectural headaches when combining both styles in a program, which is what we are doing here.  For instance, see the programming hints section on the previous wiki page on how to control loops and mutate data while in the middle of a delegation process.The following utility data structures are designed to handle the situation where an operation has more than 2 or more possible outcomes.  

Model-View-Controller Architecture

Puzzle Generation Utilities