Table of Contents
It seems everybody in this world knows what a Sudoku game is. It's a cool game and pretty popular.
Even though, there are some very interesting variations of the game that were invented only a few years ago.
This article presents implementation of one of this variations for Windows Phone 7, and, in order to avoid dealing with trademark issues,
I named it Calcoolation, which I consider to be a proper name for the nature of the game: Just like in Sudoku, you have to fill all cells
inside the N x N squared board with numbers from 1 to N, without repeating numbers in any row and any column. But there's more to it: you also must
satisfy the arithmetic operations for the regions to which the cells belong.
This is my first article on Windows Phone 7. I hope you enjoy the reading and the code. Besides the fun, there are some interesting
computational problems that the application deals with.
To use the Calcoolation game provided with this article, if you already have Visual Studio 2010, that's fine. If you don't, you can download the following 100% free development tool directly from Microsoft:
Visual Web Developer 2010 Express for Windows Phone
Callcoolation, as other Sudoku-like games, is based on an N x N squared grid, where each cell must be filled by numbers varying from 1 to N. Also, this
numbers must be filled in a manner so that each number must occur exactly only once in the row and exactly once in the column where that number is placed.
This peculiar layout is what is called latin squares, invented in the 18th Century by Swiss mathematician Leonhard Euler.
It's interesting to notice that the concept of latin squares doesn't apply only to numbers, but to any distinct symbols. For example, we could have a latin square based on colors, like this:
See? A given color must never occur twice in a row or in a column.
The number of different latin squares of size N vary wildly, depending on the N variable. Here are some examples:
| N | Number of latin squares |
| 1 | 1 |
| 2 | 2 |
| 3 | 12 |
| 4 | 576 |
| 5 | 161280 |
| 6 | 812851200 |
In 2004, math teacher Tetsuya Miyamoto invented a new variation of sudoku, where the cells are grouped in bold outlined regions called "cages".
Each cage has three data:
- A group of n contiguous cells
- The target number
- The basic operation (addition, subtraction, multiplication, division)
In Miyamoto's game, each cage must be filled in a way so that the cage operation can be applied to the numbers in the cage, producing exactly the target number.
It's important to notice that Calcoolation is a "clueless" game, that is, while in traditional sukoku games there are some cells already filled in, this
game has all cells initially empty, hence "clueless".
The code is divided into two layers: WP7Calcoolation.Core and WP7Calcoolation. In the WP7Calcoolation layer, we have the Silverlight presentation logic
for the Windows Phone. The interface is quite simple, and I thought it wouldn't be necessary to add sophisticated animations, which I would try in a
traditional Silverlight project.
The Core layer does most of the hard work. It's composed of classes that represent the three main entities in the game: the Board, the Cage, and the Cell.
There can be only one Board in the game (that's why I decided to use the Singleton pattern).
The default Board has the predefined dimension 4x4 (which can be changed later by the user).
Each position in the board is held by a cell (that is, cell count = size²).
Inside the board, the cells are also arranged in pieces called "Cages" (much like a traditional puzzle).
The pieces of code that I think worth mentioning are those related to random number picking, random cage formation,
and game completeness testing.
The most challenging part was to discover the correct strategy to pick the random numbers without repetitions in columns and rows.
I decided to use the Naked Pairs/Naked Triplets strategy, which I borrowed from some sites dedicated to Sudoku solving.
I'll discuss Naked Pairs later on in this article.
For random number picking, see the GenerateNumbers() method:
private void GenerateNumbers()
{
ResetBoard();
Random rnd = new Random();
string number = "0";
int minSize = size;
int maxSize = 0;
bool someSolved = true;
while (someSolved)
{
someSolved = false;
if (!someSolved)
{
}
if (!someSolved)
{
}
for (int row = 0; row < size; row++)
{
}
for (int row = 0; row < size; row++)
{
}
if (!someSolved)
{
}
}
}
Notice that, according to the code above, the naked pairs are resolved in the beginning. Then, the naked triplets, and then the cells with a unique solution, and then the random selection. This is done so to avoid backtracking.
As a result, we now have a valid board, ready to be used:
The next important step is to randomly create the cages, and here is the GenerateCages method:
private void GenerateCages()
{
cages = new List<Cage>();
bool success = false;
int orientation = 0;
int c2 = 0;
int r2 = 0;
Random rnd = new Random();
for (int r = 0; r < size; r++)
{
for (int c = 0; c < size; c++)
{
if (matrix[c, r].Cage == null)
{
success = false;
while (!success)
{
orientation = rnd.Next(1, 5);
switch (orientation)
{
case 1: c2 = c - 1;
r2 = r;
break;
case 2: c2 = c + 1;
r2 = r;
break;
case 3: c2 = c;
r2 = r - 1;
break;
case 4: c2 = c;
r2 = r + 1;
break;
}
if (c2 >= 0 && c2 < size && r2 >= 0 && r2 < size)
{
Cage cage = matrix[c2, r2].Cage;
if (cage == null)
{
cage = new Cage();
cage.CellList.Add(matrix[c2, r2]);
matrix[c2, r2].Cage = cage;
}
else
{
if (cage.CellList.Count > 3 && (c != size - 1 || r != size - 1))
{
continue;
}
}
cage.CellList.Add(matrix[c, r]);
matrix[c, r].Cage = cage;
cages.Add(cage);
success = true;
}
}
}
}
}
Starting from the {0,0} position on the board, and moving to the right and down directions, this function places pieces of two cells in random directions, and tests whether there is a conflict with an existent cage. In this case, the cages are merged; otherwise, a new cage is created:
After that, the PickOperation() method chooses a possible random operation (picked among +, -, x, and ÷) using the numbers inside the cage.
public void PickOperation(Cage cage)
{
bool success = false;
while (!success)
{
if (currentOperation == 5)
currentOperation = 1;
switch (currentOperation)
{
case 1:
cage.Operation = Operations.Plus;
int sum = 0;
foreach (Cell cell in cage.CellList)
{
sum += Convert.ToInt32(cell.CellValue);
}
cage.Result = sum;
success = true;
break;
case 2:
cage.Operation = Operations.Minus;
if (cage.CellList.Count == 2)
{
int sub = Convert.ToInt32(cage.CellList[0].CellValue) -
Convert.ToInt32(cage.CellList[1].CellValue);
if (sub > 0)
{
cage.Result = sub;
success = true;
}
else
{
sub = Convert.ToInt32(cage.CellList[1].CellValue) -
Convert.ToInt32(cage.CellList[0].CellValue);
if (sub > 0)
{
cage.Result = sub;
success = true;
}
}
}
break;
case 3:
cage.Operation = Operations.Multiply;
int mult = 1;
foreach (Cell cell in cage.CellList)
{
mult *= Convert.ToInt32(cell.CellValue);
}
cage.Result = mult;
success = true;
break;
case 4:
cage.Operation = Operations.Divide;
if (cage.CellList.Count == 2)
{
int quo = Convert.ToInt32(cage.CellList[0].CellValue) /
Convert.ToInt32(cage.CellList[1].CellValue);
int rem = Convert.ToInt32(cage.CellList[0].CellValue) - quo *
Convert.ToInt32(cage.CellList[1].CellValue);
if (rem == 0)
{
cage.Result = quo;
success = true;
}
else
{
quo = Convert.ToInt32(cage.CellList[1].CellValue) /
Convert.ToInt32(cage.CellList[0].CellValue);
rem = Convert.ToInt32(cage.CellList[1].CellValue) - quo *
Convert.ToInt32(cage.CellList[0].CellValue);
if (rem == 0)
{
cage.Result = quo;
success = true;
}
}
}
break;
}
currentOperation++;
}
}
As a result, we now have all the random cages, with their respective randoms operations and random target numbers properly assigned:
Before getting a random number for a cell, you should always look for "naked pairs". Naked pairs mean that in some row or column, there are two cells with two possible values. In the figure below, we can spot these naked pairs in the bottom left cage, with only two possible values [1,3]:
The reason for spotting naked pairs is simple: since these two cells can hold only these two digits, no other cells in that row will have "1" or "3".
Thus we can remove them from the possible digits:
You can see the correct answers by clicking the "End Game" button. By doing this, you are giving up the game and allowing the application
to (hopefully) dinamically generate an easier problem:
Important: Although each new game board is generated with a predefined result, it may be possible that the player ends up with another solution for the problem.
But that's okay, too: if you reach a solution which is different from the original one, you win. Each movement in the board will trigger a function that checks whether
a satisfactory solution was produced:
public bool TestResult()
{
bool success = false;
if (cellList.Count > 0)
{
switch (operation)
{
case Operations.Plus:
int sum = 0;
foreach (Cell cell in cellList)
{
sum += Convert.ToInt32(cell.UserValue);
}
if (sum == result)
success = true;
break;
case Operations.Minus:
int sub = 0;
sub = Convert.ToInt32(cellList[0].UserValue) - Convert.ToInt32(cellList[1].UserValue);
if (sub == result)
success = true;
else
{
sub = Convert.ToInt32(cellList[1].UserValue) - Convert.ToInt32(cellList[0].UserValue);
if (sub == result)
success = true;
}
break;
case Operations.Multiply:
int mult = 1;
foreach (Cell cell in cellList)
{
mult *= Convert.ToInt32(cell.UserValue);
}
if (mult == result)
success = true;
break;
case Operations.Divide:
int div = 0;
int rem = 0;
div = Convert.ToInt32(cellList[0].UserValue) / Convert.ToInt32(cellList[1].UserValue);
rem = Convert.ToInt32(cellList[0].UserValue) - (div * Convert.ToInt32(cellList[1].UserValue));
if (div == result && rem == 0)
success = true;
else
{
div = Convert.ToInt32(cellList[1].UserValue) / Convert.ToInt32(cellList[0].UserValue);
rem = Convert.ToInt32(cellList[1].UserValue) - (div * Convert.ToInt32(cellList[0].UserValue));
if (div == result && rem == 0)
success = true;
}
break;
}
}
return success;
}
The game UI is based on Silverlight for Windows Phone 7. Lucky us, there is a great tool called Microsoft Expression Blend 4 which was
created to facilitate development of interfaces in applications built with WPF, Silverlight and Silverligtht for Windows Phone 7. In fact, I didn't use Expression Blend
to design the game UI of Calcoolation (maybe because I'm still a masochistic stubborn who loves building user interface directly in XAML or code behind),
but I promise playing with Expression Blend 4 in the next articles.
Back to Expression Blend 4, here is the Game UI opened by this great tool (click to enlarge):
The picture above shows that most of the game is made up by native Silverlight controls, such as the grid for the game board, buttons for picking numbers and buttons that
for the New Game, End Game and Exit Game user gestures.
The only noticeable exception here is the CellBox user control, which is is used to fill the 4 x 4 game grid. This control is responsible for
controlling user gestures inside each cell (such as selecting/clearing number), displaying cage operation and target number, as well as displaying the correct number.
As you can see, article didn't cover sophisticated aspects of Silverlight development for Windows Phone 7. I think any Silverlight developer can easily understand the simple UI presented here.
I think simple is great, when your goals are achieved. I also think the algorithm gotchas makes the article much more interesting.
If you have complaints, advices or suggestions, please leave a comment at the bottom of the page. Feedbacks are great and I'd love to know what you think.
- 2011-05-15: Initial version.
