Click here to Skip to main content
15,867,308 members
Articles / Mobile Apps / Windows Phone 7

Windows Phone 7 Calcoolation

Rate me:
Please Sign up or sign in to vote.
4.96/5 (46 votes)
16 May 2011CPOL7 min read 93.4K   1.2K   51   42
Math-based, sudoku-like game for Windows Phone 7

Image 1

Table of Contents

Introduction

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.

System Requirements

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
  • Latin Squares

    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:

    NNumber of latin squares
    11
    22
    312
    4576
    5161280
    6812851200

    The Concept of Cages

    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:

    Image 2

    • 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

    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.

    Image 3

    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.

    Random Number Picking

    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:

    C#
    private void GenerateNumbers()
    {
        ResetBoard();
        Random rnd = new Random();
        string number = "0";
        int minSize = size;
        int maxSize = 0;
        bool someSolved = true;
    
        while (someSolved)
        {
            someSolved = false;
            //Search for naked pairs in rows
            if (!someSolved)
            {
               //code removed for better visibility
            }
    
            //Search for naked pairs in columns
            if (!someSolved)
            {
               //code removed for better visibility
            }
    
            //Search for naked triplets in rows
            for (int row = 0; row < size; row++)
            {
               //code removed for better visibility
            }
    
            //Search for cells with a unique solution possible
            for (int row = 0; row < size; row++)
            {
               //code removed for better visibility
            }
    
            //Random selection
            if (!someSolved)
            {
               //code removed for better visibility
            }
        }
    }

    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:

    Image 4

    Random Cage Formation

    The next important step is to randomly create the cages, and here is the GenerateCages method:

    C#
    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: // W
                                c2 = c - 1;
                                r2 = r;
                                break;
                            case 2: // E
                                c2 = c + 1;
                                r2 = r;
                                break;
                            case 3: // N
                                c2 = c;
                                r2 = r - 1;
                                break;
                            case 4: // S
                                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:

    Image 5  Image 6

    After that, the PickOperation() method chooses a possible random operation (picked among +, -, x, and ÷) using the numbers inside the cage.

    C#
    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:

    Image 7

    The Naked Pairs

    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]:

    Image 8

    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:

    Image 9

    Showing Correct Answers

    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:

    Image 10

    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:

    C#
    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

    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):

    Image 11

    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.

    Image 12

    Final Considerations

    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.

    History

    • 2011-05-15: Initial version.

    License

    This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


    Written By
    Instructor / Trainer Alura Cursos Online
    Brazil Brazil

    Comments and Discussions

     
    QuestionSuper! Pin
    AndySolo8-Sep-14 7:05
    AndySolo8-Sep-14 7:05 
    QuestionVery nice Pin
    Mike Hankey25-May-13 11:16
    mveMike Hankey25-May-13 11:16 
    AnswerRe: Very nice Pin
    Marcelo Ricardo de Oliveira27-May-13 13:29
    mvaMarcelo Ricardo de Oliveira27-May-13 13:29 
    Thank you very much, Mike!
    There's no free lunch. Let's wait for the dinner.

    Take a look at Social News here in The Code Project.

    GeneralMy vote of 5 Pin
    Wendelius16-Dec-11 8:56
    mentorWendelius16-Dec-11 8:56 
    GeneralMy vote of 5 Pin
    Don Jomar Hombrebueno29-Jun-11 22:37
    Don Jomar Hombrebueno29-Jun-11 22:37 
    GeneralRe: My vote of 5 Pin
    Marcelo Ricardo de Oliveira5-Jul-11 6:41
    mvaMarcelo Ricardo de Oliveira5-Jul-11 6:41 
    GeneralMy vote of 5 Pin
    Monjurul Habib17-Jun-11 10:38
    professionalMonjurul Habib17-Jun-11 10:38 
    GeneralRe: My vote of 5 Pin
    Marcelo Ricardo de Oliveira17-Jun-11 12:30
    mvaMarcelo Ricardo de Oliveira17-Jun-11 12:30 
    GeneralMy vote of 5 Pin
    Rhuros15-Jun-11 2:27
    professionalRhuros15-Jun-11 2:27 
    GeneralRe: My vote of 5 Pin
    Marcelo Ricardo de Oliveira16-Jun-11 4:19
    mvaMarcelo Ricardo de Oliveira16-Jun-11 4:19 
    GeneralMy Vote of 5 Pin
    RaviRanjanKr27-May-11 0:18
    professionalRaviRanjanKr27-May-11 0:18 
    GeneralRe: My Vote of 5 Pin
    Marcelo Ricardo de Oliveira27-May-11 6:01
    mvaMarcelo Ricardo de Oliveira27-May-11 6:01 
    GeneralNeat Pin
    AspDotNetDev26-May-11 11:20
    protectorAspDotNetDev26-May-11 11:20 
    GeneralRe: Neat Pin
    Marcelo Ricardo de Oliveira27-May-11 6:00
    mvaMarcelo Ricardo de Oliveira27-May-11 6:00 
    GeneralMy vote of 5 Pin
    Filip D'haene23-May-11 0:48
    Filip D'haene23-May-11 0:48 
    GeneralRe: My vote of 5 Pin
    Marcelo Ricardo de Oliveira23-May-11 3:37
    mvaMarcelo Ricardo de Oliveira23-May-11 3:37 
    GeneralMy vote of 5 Pin
    HimanshuJoshi19-May-11 3:50
    HimanshuJoshi19-May-11 3:50 
    GeneralRe: My vote of 5 Pin
    Marcelo Ricardo de Oliveira19-May-11 6:28
    mvaMarcelo Ricardo de Oliveira19-May-11 6:28 
    GeneralNice one! Pin
    Meshack Musundi18-May-11 1:07
    professionalMeshack Musundi18-May-11 1:07 
    GeneralRe: Nice one! Pin
    Marcelo Ricardo de Oliveira18-May-11 4:52
    mvaMarcelo Ricardo de Oliveira18-May-11 4:52 
    GeneralGreat article Pin
    Patrick Kalkman17-May-11 10:58
    Patrick Kalkman17-May-11 10:58 
    GeneralRe: Great article Pin
    Marcelo Ricardo de Oliveira17-May-11 11:21
    mvaMarcelo Ricardo de Oliveira17-May-11 11:21 
    GeneralAnother nice one my friend Pin
    Sacha Barber17-May-11 6:31
    Sacha Barber17-May-11 6:31 
    GeneralRe: Another nice one my friend Pin
    Marcelo Ricardo de Oliveira17-May-11 6:52
    mvaMarcelo Ricardo de Oliveira17-May-11 6:52 
    GeneralRe: Another nice one my friend Pin
    Kunal Chowdhury «IN»18-May-11 1:00
    professionalKunal Chowdhury «IN»18-May-11 1:00 

    General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

    Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.