Monday, May 23, 2011

DDTe2 hours 10 to 13 The Generator Phase 2 to 4

This article continues my series on the development of my Sudoku Puzzle Generator which can be found at http://blazinggames.com/table/dozenDays/tiles/sudokuGen.php . Previous entries have covered the model class, covering up finished puzzles, the first phase of creating a random puzzle, and how to generate potential combinations of numbers.

The remaining portion of the sudoku puzzle potentially requires a lot of processing so the work has been broken up into three separate phases. To control the phases, a processPuzzle function has been created to simply determine what phase of generation the game is in and call the appropriate generation function. This has the added benefit that if the generation results in a failed puzzle, we simply need to change the next phase to 1 and a new puzzle will start being generated from scratch. The internals of this function is simply a switch statement so there is nothing to look at here. Where things are interesting is in the phaseN functions that handle the generation of phases two through four. While it may have been possible to write these as a single function that takes the phase as a parameter, I chose the quick and dirty route of duplicating code for the three separate functions. This was fairly simple to write and works quite well, but code purists will not like the code duplication that is a result of taking this development shortcut. Know that a cleaner implementation is possible.

The first step in the remaining phases is to loop through the three rows being processed and figure out which numbers are not in the row. Here is the code segment that does this. It is designed for phase3, but with some number changes works for the other two phases. As you can see, the constants could simply be replaced with a calculated number based on the phase being processed.

     groupData = new Array();
       for (cntrList = 1; cntrList < 10; ++cntrList) {
           if ((this._model.tileGrid[cntrRow][4] != cntrList) &&
                   (this._model.tileGrid[cntrRow][5] != cntrList) &&
                   (this._model.tileGrid[cntrRow][6] != cntrList))
               groupData.push(cntrList);
       }
     SudokuGen.mixArray(groupData);
    
This array of possible numbers is mixed to prevent the order that the combinations appear in the puzzle from being predictable. The potential combinations are processed in a do loop and we simply check to make sure that the potential combination does not result in an invalid puzzle. The heart of the loop that validates the combination for phase 3 is below. Notice that due to the non-linearity of the empty tiles, there is a bit more complexity required to determine if the numbers are valid.

     comboList = this.buildComboSet(groupData, combo);
       for (cntrList = 0; cntrList < 6; ++cntrList) {
           if (cntrList < 3) {
               tempCol = cntrList + 1;
               tempGroup = 4;
           } else {
               tempCol = cntrList + 4;
               tempGroup = 6;
           }
           if ( (this._model.countValueInCol(comboList[cntrList], tempCol) > 0) ||
                   (this._model.countValueInGroup(comboList[cntrList], tempGroup)>0) ){
               err = 1;//SudokuGen.COMBOCOUNT[8-cntrList];
               break;
           }
       }
 
The loop continues until a valid combination has been found or until all 720 combinations have been checked. If the later has occurred, the puzzle is not valid so we have to start the generation of the puzzle over again by setting the phase to 1. This is also where a bug in my original implementation occurred. I mistakenly  had the code to set the next phase placed here instead of after row loop. This misplaced code would result in the possibility of the invalid puzzle being passed to the next phase instead of the puzzle generation starting over.

The final thing to do to finish processing a row is to copy the valid combination into the puzzle model. This is a simple copying loop.
  
           cntrList = 0;
           for (cntrCol = 1; cntrCol < 4; ++cntrCol)
               this._model.tileGrid[cntrRow][cntrCol] = comboList[cntrList++];
           for (cntrCol = 7; cntrCol < 10; ++cntrCol)
               this._model.tileGrid[cntrRow][cntrCol] = comboList[cntrList++];
 
When all three rows of the phase have been processed successfully we set the next phase and if the next phase is 5 then we have randomly generated a valid puzzle. At this point we have a generator, but the generated puzzle is not in either a printable or playable state. Both these problems are simple to solve however.

No comments: