DDTe2 hours 14 to 15 Fine Tuning

This is the second to last article for my series on the creation of Dozen Days of Tiles episode 2: Sudoku Generator. Earlier posts covered the creation and hiding of the puzzle. The final game is on Blazing Games and is located at http://blazinggames.com/table/dozenDays/tiles/sudokuGen.php.

To support multiple puzzles with the Sudoku Player, the URL has a data parameter that contains 81 characters that represent the puzzle data. The .php page has code that converts the letters into the initial board data statements that the player uses. This coding uses letters to represent the numbers with the letters being in a random order to make it really difficult for a human to look at the URL and figure out the solution to the puzzle. To generate this encoding, I wrote a simple function to convert the grid into a 81 character encoded string.

SudokuGen.ENCODE = "JBLAKIRNEFPSMCOGDTQH";
SudokuGen.Model.prototype.getEncoded = function()
{
   var encode = "";
   var value, cntrRow, cntrCol;

   for (cntrRow = 1; cntrRow < 10; ++cntrRow)
       for (cntrCol = 1; cntrCol < 10; ++cntrCol) {
           value = this.tileGrid[cntrRow][cntrCol];
           if (this.lockGrid[cntrRow][cntrCol] == true)
               value += 10;
           encode += SudokuGen.ENCODE.substr(value, 1);
       }
      
   return encode;
}

Just being able to use the player isn’t quite enough. I also want to make the puzzles printable so that they can be printed out on paper to be solved.  As the puzzle really is just nested tables, this can be done entirely with the HTML table tags. This requires working with the awful DOM classes, but really is fairly simple. Essentially, the puzzle is a 3x3 table with each table in the puzzle being a 3x3 table that contains the group data.

function writePuzzle(model)
{
   var puzzle = document.getElementById('puzzle');
   var cntrRow, cntrCol, cntrGroup, cntrSec;
   var groupTable, temp, grow, gcell;
  
   // top three groups
   for (cntrSec = 0; cntrSec < 3; ++cntrSec) {
       prow = puzzle.insertRow(cntrSec);
       for (cntrGroup = 0; cntrGroup < 3; ++cntrGroup) {
           pcell = prow.insertCell(cntrGroup);
           groupTable = document.createElement("table");
           groupTable.border = "1";
           groupTable.cellPadding = "5";
           for (var cntrRow = 0; cntrRow < 3; ++cntrRow) {
               grow = groupTable.insertRow(cntrRow);
               for (var cntrCol = 0; cntrCol < 3; ++cntrCol) {
                   gcell = grow.insertCell(cntrCol);
                   temp = model.getPuzzleValue(cntrRow+cntrSec*3+1, cntrCol+cntrGroup*3+1);
                   if (temp > 10)
                       gcell.innerHTML = "" + (temp - 10);
                   else
                       gcell.innerHTML += " ";
               }
           }
          
           pcell.appendChild(groupTable);           
       }
   }
  
   var msg = document.getElementById('waitText');
    msg.innerHTML = ""+ playerMessage + "";

}

As generating the puzzle can take some time, my final touch was a please wait message which is animated as the generation passes happen. When the generation is done, this gets replaced by the Sudoku Player URL.

Of course, this is the point when I discover a game-stopper bug. It seems that occasionally the puzzle generation locks up. If you have been following along with this series of articles, you already know that the problem was my next phase being prematurely set allowing an occasional invalid game to be treated as a valid puzzle. This was a very easy bug to fix but a bit harder to figure out. In fact, I had a working fix in a matter of minutes but it took me a couple of hours to actually figure out what the real problem was. That story will be told next week.

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.

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.

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.

DDTe2 hours 4 to 6 - Hiding Tiles

This is a continuation of my series of articles on the creation of Dozen Days of Tiles Episode 2: Sudoku Generator. There is a sneak preview of the game on BlazingGames.com for those who are interested. The final version of the game is scheduled for release on May 20th.


Taking an existing sudoku solution and turning it into a puzzle may at first glance sound like it would be something tricky, it actually is very simple. When I was creating a puzzle by hand, the method that immediately came to mind was to start with a near blank puzzle and add bits of the final solution to it. Try to solve until the puzzle is solved or until you reach a point where all remaining tiles have more than one possibility. At this point, reveal one of the unsolved tiles and continue solving.

When working with a lot of data manipulation, it is nice to be able to see what is going on. Using a debugger could work but it is much more efficient to dump the data to a log file. While FireBug supports a console, I figured it would be easier and more compatible to create my own console. This is simply done by using a text area.

function dumpPuzzle(data)
{
   var log = document.getElementById('log');
   log.value ="Puzzle:\n";

   var temp;
   for (var cntrRow = 1; cntrRow < 10; ++cntrRow) {
       for (var cntrCol = 1; cntrCol < 10; ++cntrCol) {
           temp = data.getPuzzleValue(cntrRow, cntrCol);
           if (temp > 10)
               log.value = log.value + (temp - 10);
           else
               log.value += "-";
       }
       log.value += " ===> ";
       for (var cntrCol = 1; cntrCol < 10; ++cntrCol) {
           temp = data.getValue(cntrRow, cntrCol);
               log.value = log.value + temp;
       }
       log.value += '\n';
   }
}


With the ability to dump the puzzle as it is being generated solved, the next issue is revealing tiles in random order. While this could be done purely randomly, every time the randomly chosen tile is already revealed you will need to choose another tile. As the board nears completion you will have the problem that you are going to have a lot of filled-tile hits causing you to be stuck in potentially long random selection loops. My solution is to simply create a row and a column array, shuffle those arrays, then simply use that random order when trying to find the next tile to reveal.

The method I use for trying to solve the puzzle is to simply look at what possible numbers can be placed in the tile. This is done the same way  the hint feature was created in the Sudoku player. If there is only one possibility, we treat that tile as known. When all tiles have been uncovered or marked as known then we are done.

Next, we get to the hard part. Creating potential sudoku solutions.