Click here to Skip to main content
Click here to Skip to main content

Windows Phone 7 Calcoolation

, 16 May 2011
Rate this:
Please Sign up or sign in to vote.
Math-based, sudoku-like game for Windows Phone 7

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:

    • 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.

    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:

    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:

    Random Cage Formation

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

      

    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:

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

    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:

    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:

    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

    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.

    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)

    Share

    About the Author

    Marcelo Ricardo de Oliveira
    Software Developer
    Brazil Brazil
    Marcelo Ricardo de Oliveira is a senior software developer who lives with his lovely wife Luciana and his little buddy and stepson Kauê in Guarulhos, Brazil, is co-founder of the Brazilian TV Guide TV Map and currently works for ILang Educação.
     
    He is often working with serious, enterprise projects, although in spare time he's trying to write fun Code Project articles involving WPF, Silverlight, XNA, HTML5 canvas, Windows Phone app development, game development and music.
     
    Published Windows Phone apps:
     
     
    Awards:
     
    CodeProject MVP 2012
    CodeProject MVP 2011
     
    Best Web Dev article of March 2013
    Best Web Dev article of August 2012
    Best Web Dev article of May 2012
    Best Mobile article of January 2012
    Best Mobile article of December 2011
    Best Mobile article of October 2011
    Best Web Dev article of September 2011
    Best Web Dev article of August 2011
    HTML5 / CSS3 Competition - Second Prize
    Best ASP.NET article of June 2011
    Best ASP.NET article of May 2011
    Best ASP.NET article of April 2011
    Best C# article of November 2010
    Best overall article of November 2010
    Best C# article of October 2010
    Best C# article of September 2010
    Best overall article of September 2010
    Best overall article of February 2010
    Best C# article of November 2009

    Comments and Discussions

     
    GeneralMy vote of 5 PinmemberMonjurul Habib17-Jun-11 10:38 
    GeneralRe: My vote of 5 PinmvpMarcelo Ricardo de Oliveira17-Jun-11 12:30 

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

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

    | Advertise | Privacy | Mobile
    Web03 | 2.8.140821.2 | Last Updated 16 May 2011
    Article Copyright 2011 by Marcelo Ricardo de Oliveira
    Everything else Copyright © CodeProject, 1999-2014
    Terms of Service
    Layout: fixed | fluid