DDTe2 hour 7 - The Generator Phase 1

This is a continuation of my series on the creation of Dozen Days of Tiles Episode 2. Previous articles have covered the sudoku model used for storing the puzzle and the hiding of the puzzle. We are now starting the lengthy process of creating a valid random puzzle. For those of you interested in playing the game, the target release date for the final version of this game is May 20th, 2011.

Generating  a random row, column, or group is very simple. If only we could generate 9 random groups, we would be set. The problem is that there are far more incorrect ways of generating a random puzzle then there are correct ways. Just generating random groups until we end up with a valid puzzle is not a viable solution. Instead, we need to generate random puzzles in such a way as to maximize the odds that we have a valid puzzle.

My first thought was to generate the first group randomly then fill out the rest of the puzzle by finding combinations of the remaining numbers that will fit into the puzzle. As I started working on this approach I quickly realized that the diagonal directions are independent of each other so the first phase of creating a solution is simply to generate three random groups. One for the top-left, one for the middle, and one for the bottom-right.

Generating a random group is simply a matter of mixing an array of the numbers 1 through 9. I use my card mixing method which simply randomly swaps each card in the deck with another card in the deck. This results in a really good shuffle.

SudokuGen.mixArray = function(arr)
{
   var len = arr.length;
   var swap, temp, cntr;

   for (cntr = 0; cntr < len; ++cntr) {
   swap = Math.floor(Math.random()*len);
   temp = arr[cntr];
   arr[cntr] = arr[swap];
   arr[swap] = temp;
   }
}

Once the array of numbers from 1 to 9 is scrambled, it is a simple matter of putting the numbers into the right place in our sudoku model. For speed of development, I am brute-forcing the placement of the numbers by duplicating the code for each group. Instead of duplicating code three times, this could be condensed into a single loop that determines the start and end positions of the loops algorithmically (cntr * 3 + 1). In hind-site, I should of done the cleaner version as it would not have been much work but other than a bit of bloat, there is nothing wrong with the current implementation of the first pass.

SudokuGen.Generator.prototype.phase1 = function()
{
   this._model.clear();
   var groupData  = new Array(1,2,3,4,5,6,7,8,9);
   var cntrRow, cntrCol, cntrList;
   SudokuGen.mixArray(groupData);
   cntrList = 0;
   for (cntrRow = 1; cntrRow < 4; ++cntrRow)
   for (cntrCol = 1; cntrCol < 4; ++cntrCol)
   this._model.setValue(cntrRow,cntrCol,groupData[cntrList++]);
  
   SudokuGen.mixArray(groupData);
   cntrList = 0;
   for (cntrRow = 4; cntrRow < 7; ++cntrRow)
   for (cntrCol = 4; cntrCol < 7; ++cntrCol)
   this._model.setValue(cntrRow,cntrCol,groupData[cntrList++]);

   SudokuGen.mixArray(groupData);
   cntrList = 0;
   for (cntrRow = 7; cntrRow < 10; ++cntrRow)
   for (cntrCol = 7; cntrCol < 10; ++cntrCol)
   this._model.setValue(cntrRow,cntrCol,groupData[cntrList++]);

   this._phase = 2;
}

The next phase of generation will be filling in the rest of the puzzle by looking at the possible combinations that can fit into the rest of the puzzle. This, needless to say, requires the ability to determine the possible combinations so the next part will look at combination generation.