Page History

...

• 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.
    • Wiki Markup_Solved_ \ - the cell contains exactly one value.&nbsp;&nbsp; +If and only if you know for sure that the cell is in this state+, then the single value can be accessed as {{   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.

    Code Block
    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

...

• currentBoard - a field which references the board that is currently being solved.
  
• loadStrs -- takes a vector of strings, which are the rows of a puzzle, and translates the strings into the cells of a new current board.  This method is compatible with the puzzle generation utilities, but is not yet hooked up to them.
  
• validateBoard - performs a validation check on the current board and returns a string describing the current state of the board.   This method calls validateCellSet on every cell set of the rows, columns and blocks of the board.   Examine this method carefully to get ideas on how to process the board!
  • Important Note: This method should NOT BE USED as part of the solving process!!   It was designed to give textual feedback to the user and not to be part of a solving algorithm.   You will be marked down for using this method and attempting to parse it return string to determine the state of the board.  In fact, it is less effecient to separately check the validity of the board during the reduction and solving  process -- the board reduction algorithm (reduceBoard()) should be able to determine the status of the board as a byproduct of its actions, thus negating the need for a separate validation operation.
    
• getSolvedCellValues -- gets a HashSet<Integer> containing all the values from the solved cells in a cell set.   This is used when reducing a cell.
  
• countCellChoices -- a utility method that will return the number of choices in all the unsolved cells in a given cell set
  
• Wiki Markup{{{*}reduceCellSet{*}}} \ -\- \[<span style="color: #ff0000"><em>Student implemented</em></span>\]&nbsp; perform a single reduction pass on every cell in a given cell [Student implemented]  perform a single reduction pass on every cell in a given cell set.
  • Start by having reduceBoard simply call this method on a specific cell set.
    
  unmigrated-wiki-markup
  • 
    
  {{{*}
• reduceBoard{*}}} \ -\- \[<span style="color: #ff0000"><em>Student implemented</em></span>\]&nbsp; perform a single reduction pass on every cell in the board. Wiki Markup{{{*}solve{*}}} \-\- \[<span style="color: #ff0000"><em>Student implemented</em></span>\] perform reduction passes on the board until the board is either&nbsp;shown to be solved or unsolvable.&nbsp;&nbsp; This method should be able to handle boards that are reducible, irreducible, or [Student implemented]  perform a single reduction pass on every cell in the board.
• solve -- [Student implemented] perform reduction passes on the board until the board is either shown to be solved or unsolvable.   This method should be able to handle boards that are reducible, irreducible, or unsolvable.
  • The method is defined as also allowing a return status of "irreducible", though in the final implementation, that should never occur.    This return value is allowed so that you can do a partial implementation of the solve algorithm before you implement solveIrreducibleBoard. 
    
• Wiki Markup{{{*}findMinChoiceCell{*}}} \ -\- \[<span style="color: #ff0000"><em>Student implemented</em></span>\] Use some heuristic to find the best choice for a cell whose values represent the fastest path to a solution.&nbsp;&nbsp; This method is used when an irreducible board is encountered and the solving process needs to iterate through the choices of a given cell to test for possible solutions.&nbsp;&nbsp; If a board is solvable, on _any_ cell, &nbsp;at least one value choice in an unsolved cell will always lead towards a solution.&nbsp;&nbsp; Other choices may lead to unsolvable boards. \\[Student implemented] Use some heuristic to find the best choice for a cell whose values represent the fastest path to a solution.   This method is used when an irreducible board is encountered and the solving process needs to iterate through the choices of a given cell to test for possible solutions.   If a board is solvable, on any cell,  at least one value choice in an unsolved cell will always lead towards a solution.   Other choices may lead to unsolvable boards.
  
• solveIrreducibleBoard -- [Student implemented] Given an irreducible board (a board that doesn't change when a reduction pass is performed), looks for a solution by testing the choices of a chosen cell.   Note that a particular value choice in a cell could lead to an irreducible board, so this is fundamentally a recursive process!  Wiki Markup{{{*}solveIrreducibleBoard{*}}} \-\- \[<span style="color: #ff0000"><em>Student implemented</em></span>\] Given an irreducible board (a board that doesn't change when a reduction pass is performed), looks for a solution by testing the choices of a chosen cell.&nbsp;&nbsp; Note that a particular value choice in a cell could lead to an irreducible board, so this is fundamentally a recursive process\!&nbsp;

 Key Methods of IViewAdapter

...

GeneratePuzzleApp is a a simple GUI interface to GeneratePuzzle that allows the user to easily perform conversions.   Note that the higher numbered data files (located in data\puzzle-src) have more difficult puzzles.   Each data file contains about 10,000 puzzles numbered from 1-10000 (approx.).   An index of zero means to choose a random puzzle from the data file.   

Wiki Markup{\[GeneratePuzzleApp}} has its own {{main()}} method and thus can be run as a separate, stand-alone&nbsp;application apart from the Sudoko alone application apart from the Sudoko solver.

See the Javadocs for more detailed information on the individual methods. 

...