DDTe2 hours 8 and 9 - Combination generator

This post is a continuation of my series on the creation of Dozen Days of Tiles Episode 2: Sudoku Generator. In previous posts, we covered the sudoku model, covering puzzles, and the first phase of the generation of random puzzles.

With a chunk of the sudoku puzzle already filled out, the job remaining is to fill out the remaining portions of the puzzle. This is the simple task of taking the possible numbers that fill out the particular row and going through the possible combinations of those numbers until we either find a combination that will work with the puzzle or run out of combinations. Running out of combinations without finding an appropriate one simply indicates that we have an invalid puzzle so we start the generation of the puzzle over again.

When I was taking statistics in college, the teacher was more interested in teaching the math involved rather than explaining what the math was doing. In my opinion, this is a bad approach to teaching anything but I happen to be the type of person who cares more about the why then the how. Knowing why something works ultimately lets you take that knowledge and apply it to other things. The creation of my combination generator is an example of knowing how combinations work allows you to generate a particular combination in a consistent way so that you can easily loop through all possible combinations.

The best way of thinking of combinations is simply a set of positions for the elements of a set. The first element of the set can be in any of the n positions. The second element can be in any position that the first element is not in. The third element can be in any position that the first two elements are not in and so on until we get to the last element which must be in the single remaining position. If you are still not sure what I mean, the following table is a good summary.

1	2	3	4	5	6	First item possible positions
1	2	X	3	4	5	Second item possible positions
X	1	X	2	3	4	Third item possible positions
X	1	X	X	2	3	Fourth item possible positions
X	1	X	X	2	X	Fifth item possible positions
X	X	X	X	1	X	Sixth item only position

The code to generate a particular combo determines the positions based on the combo number by using the modulus of the number of positions remaining and skipping over already assigned slots to place values.

SudokuGen.Generator.prototype.buildComboSet = function(arr,combo)
{
   var len = arr.length;
   var last = len-1;
   var curCombo = combo
   var skip;
   var cntr, cntrPos;
   var positionList = new Array();
   var comboResult = new Array();
  
   // clear position list
   for (cntrPos = 0; cntrPos < arr.length; ++cntrPos)
       positionList[cntrPos] = last;

   // find positions for this particular combination
   for (cntr = last; cntr > 0; --cntr) {
       curCombo = combo % SudokuGen.COMBOCOUNT[cntr+1];
       skip = Math.floor(curCombo / SudokuGen.COMBOCOUNT[cntr])
       cntrPos = -1;
       while (skip >= 0) {
           ++cntrPos;
           if (positionList[cntrPos] == last)
               --skip;
       }
       positionList[cntrPos] = last - cntr;
   }
  
   // now fill out resulting combination
   for (cntr = 0; cntr < len; ++cntr) {
       comboResult[cntr] = arr[positionList[cntr]];
   }
  
   return comboResult;
}

This code doesn’t just work with numbers, but can be used to generate the possible combinations for a set of letters or any other logical grouping. For our sudoku puzzle, however, we are interested in combinations of numbers and making sure that the generated combination results in a valid puzzle, so the next step is to incorporate the combinations into the generation of the puzzles.