Code Examples: SudokuPuzzle.h and SudokuPuzzle.cpp

My latest project, a command-line interface Sudoku solver, used the class SudokuPuzzle. Here is the source code for the header file and implementation file for SudokuPuzzle. The class will be re-used in a project that creates a GUI (graphical user interface) for the solver and adds new features, such as the ability to save and load puzzles.

SudokuPuzzle.h

#ifndef SudokuPuzzle_Header
#define SudokuPuzzle_Header

#include <vector>

using namespace std;

class SudokuPuzzle
{
public:

    //Default constructor.
    SudokuPuzzle();

    //Returns a list of candidate values for a spot at (x, y).
    void getPossibleValuesAt(int possibleSolutions[], int x, int y);

    //Returns the number of possible candidates at (x, y).
    int getNumberOfPossibleValuesAt(int x, int y);

    //Attempts to add a number to (x, y). As long as the number
    //is a valid candidate, the method returns true.
    bool addNumberAt(int addNumber, int x, int y);

    //Removes a number at (x, y)
    void removeNumberAt(int x, int y);

    //Resets the puzzle grid and solution list.
    void newPuzzle();

    //Prints the puzzle.
    void printPuzzle();

    //Returns a vector container of all the possible solutions
    //found for the current puzzle.
    void solvePuzzle();

    //Determines whether or not the current puzzle is solved.
    bool isSolved();

    //Copies the puzzle into newPuzzle with a deep copy of the
    //grid.
    void copyPuzzle(SudokuPuzzle &newPuzzle);

    //Shows a solution in the list of solutions at the
    //specified index.
    void showSolution(int index);

    //Returns a solution in the list of solutions at the
    //specified index.
    SudokuPuzzle getSolution(int index);

    //Returns the number of solutions in the list of solutions.
    int getNumberOfSolutionsFound();

private:

    //Two-dimensional grid to store the puzzle.
    int myGrid[9][9];

    //Dynamically expanding vector to store all possible solutions
    //to the puzzle. Most puzzles only have 1 solution, but poorly
    //designed puzzles may have many.
    vector<SudokuPuzzle> possibleSolutions;
};

#endif


SudokuPuzzle.cpp

#include <iostream>
#include <cmath>
#include <vector>
#include "SudokuPuzzle.h"

using namespace std;

SudokuPuzzle::SudokuPuzzle()
{
    //Default constructor. This constructor creates an empty Sudoku grid.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            myGrid[x][y] = 0;
        }
    }
}

void SudokuPuzzle::getPossibleValuesAt(int possibleSolutions[], int x, int y)
{
    //This function will use the array possibleSolutions as a hash table to
    //determine the value of all candidates for the Sudoku grid at (x, y).
    //The hash table is then used by the calling method to determine which
    //candidates are allowed for that spot.

    for (int index = 0; index < 9; index++)
    {
        possibleSolutions[index] = 1;
    }

    for (int xPos = 0; xPos < 9; xPos++)
    {
        if (xPos != x && myGrid[xPos][y] > 0) possibleSolutions[myGrid[xPos][y] - 1] = 0;
    }

    for (int yPos = 0; yPos < 9; yPos++)
    {
        if (yPos != y && myGrid[x][yPos] > 0) possibleSolutions[myGrid[x][yPos] - 1] = 0;
    }

    int xGroup = floor((double)(x / 3));
    int yGroup = floor((double)(y / 3));
   
    for (int xPos = 0 + (3 * xGroup); xPos < 3 + (3 * xGroup); xPos++)
    {
        for (int yPos = 0 + (3 * yGroup); yPos < 3 + (3 * yGroup); yPos++)
        {
            if (yPos != y && xPos != x && myGrid[xPos][yPos] > 0) possibleSolutions[myGrid[xPos][yPos] - 1] = 0;
        }
    }

    return;
}

int SudokuPuzzle::getNumberOfPossibleValuesAt(int x, int y)
{
    //This function will return the number of candidates available
    //for the Sudoku grid at (x, y).

    if (myGrid[x][y] != 0) return 0;

    int possibleSolutions[9];

    getPossibleValuesAt(possibleSolutions, x, y);

    int candidateCount = 0;

    for (int x = 0; x < 9; x++)
    {
        if (possibleSolutions[x] == 1) candidateCount++;
    }

    return candidateCount;
}

bool SudokuPuzzle::addNumberAt(int addNumber, int x, int y)
{
    //This function will put in addNumber in the grid at (x, y) as long
    //as addNumber is a valid candidate for that spot. A boolean is returned
    //so the caller knows whether or not the number was successfully added.

    if (addNumber == 0) return true;

    if (myGrid[x][y] != 0)
    {
        cout << "The spot at (" << x << "," << y << ") is currently occupied.\n\n";
        system("PAUSE");
        return false;
    }

    int possibleSolutions[9];

    getPossibleValuesAt(possibleSolutions, x, y);

    if (possibleSolutions[addNumber - 1] == 0)
    {
        cout << addNumber << " is not a valid candidate for (" << x << "," << y << ").\n\n";
        system("PAUSE");
        return false;
    }

    myGrid[x][y] = addNumber;
    return true;
}

void SudokuPuzzle::removeNumberAt(int x, int y)
{
    //Remove one number.

    myGrid[x][y] = 0;
}

void SudokuPuzzle::newPuzzle()
{
    //Clears the grid.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            myGrid[x][y] = 0;
        }
    }
}

void SudokuPuzzle::printPuzzle()
{
    //Display the puzzle for implementation
    //in a command-line environment.

    cout << "\t0 1 2  3 4 5  6 7 8\n\n";

    for (int y = 0; y < 9; y++)
    {
        cout << y << "\t";

        for (int x = 0; x < 9; x++)
        {
            cout << myGrid[x][y] << " ";
            if (x == 2 || x == 5) cout << " ";
        }

        if (y == 2 || y == 5 || y == 8) cout << "\n\n";
        else cout << "\n";
    }
}

bool SudokuPuzzle::isSolved()
{
    //Determine if all spots are filled with valid candidates.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (myGrid[x][y] == 0) return false;
        }
    }

    return true;
}

void SudokuPuzzle::solvePuzzle()
{
    //The puzzle solving algorithm. The algorithm scans each spot
    //and starts with the spot that has the lowest number of
    //possible candidates. Each candidate is tried one at a time
    //and the rest of the spots are filled in the same manner.
    //If a spot is found that is not yet filled, but there are no
    //valid candidates, then the puzzle is unsolvable and a new
    //candidate is tried in a previous spot.

    int candidateX, candidateY, candidateNumber = 100, tempCandidate;
    int candidateList[9];

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (myGrid[x][y] == 0)
            {
                tempCandidate = getNumberOfPossibleValuesAt(x, y);

                if (tempCandidate < candidateNumber)
                {
                    candidateNumber = tempCandidate;
                    candidateX = x;
                    candidateY = y;
                    getPossibleValuesAt(candidateList, x, y);
                }
            }
        }
    }

    //All candidates have been determine for (candidateX, candidateY) where
    //that spot has the least amount of candidates. Loop through those candidates
    //and attempt to solve the next resulting puzzle.

    for (int index = 0; index < 9; index++)
    {
        if (candidateList[index] == 1)
        {
            addNumberAt(index + 1, candidateX, candidateY);

            if (isSolved())
            {
                SudokuPuzzle tempPuzzle;
                copyPuzzle(tempPuzzle);
                possibleSolutions.push_back(tempPuzzle);
            }
            else solvePuzzle();
           
            removeNumberAt(candidateX, candidateY);
        }
    }
}

void SudokuPuzzle::copyPuzzle(SudokuPuzzle &newPuzzle)
{
    //Deep copy the grid into newPuzzle.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            newPuzzle.addNumberAt(myGrid[x][y], x, y);
        }
    }
}

void SudokuPuzzle::showSolution(int index)
{
    //Show the solution in possibleSolutions at the specified index.
   
    if (index < 0 || index >= possibleSolutions.size()) return;

    possibleSolutions[index].printPuzzle();
}

SudokuPuzzle SudokuPuzzle::getSolution(int index)
{
    //Return the solution in possibleSolutions at the specified index.

    if (index < 0 || index >= possibleSolutions.size())
    {
        SudokuPuzzle newPuzzle;
        return newPuzzle;
    }
       
    return possibleSolutions[index];
}

int SudokuPuzzle::getNumberOfSolutionsFound()
{
    //Return the number of solutions in possibleSolutions.

    return possibleSolutions.size();
}

Project Examples: A Sudoku Solver Implementation

While on vacation in Florida, I got a bit restless during some downtime and broke out Visual Studio in order to see if there was anything I wanted to try and program. One of the ideas that came up was a Sudoku solver.

The project took a day or so to code. The goals of this implementation were, to establish a proof-of-concept:

1. Store a Sudoku puzzle in computer memory.

2. Access the Sudoku puzzle and display it on the screen.

3. Create and implement an algorithm to solve a Sudoku puzzle that a user inputs.

These goals were all met with the project. The implementation was written in C++ and uses a command-line interface to interact with the user.

In order to show off what this implementation can do, I took some screenshots. The puzzle used in this example is located here: http://www.sudoku.ws/extreme-20.htm

Here is what the user sees when the program is started. There is a blank Sudoku grid and a menu of options. The user can input a puzzle either 1 number at a time, or iterate through each spot and input the entire puzzle. I prefer option 1 to enter my puzzles.

When option 1 is selected, you are prompted to enter a value for each spot at (x, y) on the coordinate system. At any time, the user may stop entering new numbers, which will take him back to the main menu.

Here is my screen after I finished entering the puzzle. The puzzle values are displayed along with the main menu. From here, if we were trying to solve the puzzle manually, we can use option 4 to view a list of candidate numbers for a certain spot.

In this screen, I elected to view the candidate list for spot (1,1) on the Sudoku grid. The program calculates the valid candidates and returns the list for display. This information is helpful for those trying to manually solve the puzzle.

Finally, the option that is the backbone of the entire project, is the automated solver. I selected the automated solver and it returned 1 solution. This solution matches exactly with the posted solution on the web-site that provided the test puzzles. If there were more than 1 solution, the user has the option of viewing them 1 at a time in a slide-show format. At any time, the user may select the solution he wishes to do more work with  and that puzzle is then brought back to the main menu. This feature should be of help to Sudoku puzzle designers as they can see how removing numbers from the puzzle impacts the candidate lists for each spot.

The command line implementation utilizes a greedy algorithm and recursion to solve the puzzle. The first thing the solver does is scan the grid to determine which spot has the least amount of valid candidate numbers. From here, the solver simply inputs the first candidate and then repeats the process. When a puzzle becomes unsolvable, where an empty spot has no valid candidates, control is simply returned to a previous spot, and the next valid candidate is attempted. The algorithm has O(n ^ 2) time complexity due to the nested loops within each recursive call, but there is an upper limit since each Sudoku puzzle has, at maximum, 81 empty slots.

If you would like to try out the solver, I have uploaded it to Google Drive. Simply download the Sudoku solver and run it on your PC.

The next stage of this project is to implement the SudokuPuzzle class in a Windows form application that will allow us to create a GUI (graphical user interface) in order to allow easier puzzle input. I would also like the option to save and load puzzles for the application.

If you would like to see the source code for the SudokuPuzzle class, it is available here. The class contains the solver method.

Code Examples: MessageBoxManager Class

This example code for Actionscript 3.0 is the class I wrote titled MessageBoxManager. The description for this example is in this post: Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer .

If you would like to see this class used in a small project, go here:  Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

package  {
  
    import flash.display.*;
    import flash.text.*;
    import flash.events.*;
  
  
    public class MessageBoxManager extends MovieClip {
      
        //This variable keeps track of how long the message is displayed.
        private var displayTimer: int;
        //This variable keeps track of how long since the message was created.
        private var timeSinceCreated: int;
        //A text field container to hold the messages.
        private var thisTextField:TextField;
        //A TextFormat object to alter the appearance of the text as needed.
        private var thisTextFormat:TextFormat;
        //A Boolean variable to notate if the message should not dissapear in a few seconds.
        private var permaDisplay: Boolean;
      
        public function MessageBoxManager() {
          
            //Constructor function to initialize the variables.
            thisTextField = new TextField();
            thisTextFormat = new TextFormat();
            permaDisplay = false;
            thisTextField.border = true;
            thisTextField.borderColor = 0x00FF00;
            thisTextField.width = 630;
            thisTextField.height = 100;
            thisTextField.alpha = 0;
            thisTextField.textColor = 0x00FF00;
            thisTextField.embedFonts = true;
            displayTimer = 0;
            thisTextField.x = 5;
            thisTextField.y = 10;
            thisTextField.alpha = 0;
          
            //When this object is added to the stage by the parent class, call the function
            //that draws the text box on the screen.
            this.addEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);
          
        }
      
        public function DrawMessageBox(event:Event){
          
            //This object has been added to the stage by the parent.
          
            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);
          
            //Draw the message box on the stage.
            parent.addChild(thisTextField);
        }
      
        public function addNewMessage(myMessage:String, size:int, font:String, seconds:int, alignment:String, permaDisplay:Boolean) {
          
            //Add a new message to the text box.
          
            //Set the display timer for the number of frames to show the message.
            this.displayTimer = 60 * seconds;
            this.timeSinceCreated = 0;
          
            //Determine which alignment to use. The parent class uses string constants to pass this
            //information quickly and easily.
            switch (alignment) {
                case "center": thisTextFormat.align = TextFormatAlign.CENTER; break;
                case "left": thisTextFormat.align = TextFormatAlign.LEFT; break;
                case "right": thisTextFormat.align = TextFormatAlign.RIGHT; break;
                case "justify": thisTextFormat.align = TextFormatAlign.JUSTIFY; break;
            }
          
            //Set the permanent display option if the message needs to stay on the screen.
            this.permaDisplay = permaDisplay;
          
            //Set the font. The parent class uses string constants to pass in the embedded font
            //quickly and easily.
            thisTextFormat.font = font;
          
            //Set the size.
            thisTextFormat.size = size;
          
            //Set the format properties to the text.
            thisTextField.defaultTextFormat = thisTextFormat;
          
            //Add the text to the text box and end the line with a newline character.
            thisTextField.appendText(myMessage + "\n");
        }
      
        public function clearMessages() {
            //Clear the text box.
            thisTextField.text = "";
            this.permaDisplay = false;
        }
      
        public function updateMessages() {
          
            //This function is called every frame.
          
            //Decrement the displayTimer variable.
            displayTimer--;
            timeSinceCreated++;
          
            //Set the limits for each timer variable.
            if (displayTimer < 0) {displayTimer = 0;}
            if (timeSinceCreated > 60) {timeSinceCreated = 60;}
          
            //If permaDisplay is true, give 1 second of life.
            if (permaDisplay == true) {displayTimer = 60;}
          
            //Determine the visibility of the text box. If the text box has less than 1 second
            //to live, gradully fade it out.
            if (timeSinceCreated < 60) {thisTextField.alpha = timeSinceCreated / 60;}
            else {thisTextField.alpha = displayTimer / 60;}
        }
    }
  
}

Code Examples: Starfield and Star Classes

 This code example contains the full Actionscript 3.0 code for the Starfield and Star classes discussed in this post: Flash Game Programming: Adding objects to the main stage from a child object.

If you would like to see these classes used in a small project, go here: Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

The Starfield class:

package
{

    import flash.display.*;
    import flash.events.*;

    public class Starfield extends MovieClip
    {
        //This class manages all of the Star objects displayed on the game screen.
       
        //Array to hold the Star objects.
        private var myStarfield:Array = new Array;
        //Integer to notate the number of Star objects to create.
        private var numberOfStars:int;
       
        public function Starfield(numberOfStars: int)
        {
            //Constructor initializes the class and waits for the object to be drawn on the main stage.
            this.numberOfStars = numberOfStars;
            this.addEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
        }
       
        public function DrawStarfield(myEvent: Event): void
        {
            //The Starfield object has been added to the stage by its parent. We now create and draw
            //the Star objects.
           
            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
           
            //Temporary variables to create and display the Star objects.
            var thisIndex:int;
            var thisStar:Star;

            //Loop to iterate the creation and display of each Star object.
            for (thisIndex = 0; thisIndex < numberOfStars; thisIndex++)
            {
                //Create a new Star object.
                thisStar = new Star(Math.random() * 640,Math.random() * 480, Math.random() * 3 + 1);
               
                //Add the Star object to the parent's stage.
                parent.addChild(thisStar);
               
                //Add the Star object to the reference array for the Starfield object.
                myStarfield.push(thisStar);
            }
        }
       
        public function UpdateStarField(cameraX:int, cameraY:int) {
           
            //Update all stars being managed by the object based on the change in game camera position.
           
            //Temporary variables to point to each Star object and update it.
            var thisIndex:int;
            var thisStar:Star;
           
            //Loop to access each Star object in the reference array.
            for (thisIndex = 0; thisIndex < myStarfield.length; thisIndex++)
            {
                //Point to the Star object in the reference array indicated by thisIndex.
                thisStar = myStarfield[thisIndex];
               
                //Update the Star object's position based on the change in the game camera and the Star object's layer.
                thisStar.x = thisStar.x - (cameraX / thisStar.getZDistance);
                thisStar.y = thisStar.y - (cameraY / thisStar.getZDistance);
               
                //If the Star object goes off screen, recycle it by wrapping it on the screen.
                if (thisStar.x > 640) {thisStar.x = 0;}
                if (thisStar.x < 0) {thisStar.x = 640;}
                if (thisStar.y > 480) {thisStar.y = 0;}
                if (thisStar.y < 0) {thisStar.y = 480;}
            }
        }
    }

}


The Star class:

package
{

    import flash.display.*;

    public class Star extends MovieClip
    {
        //This class defines the properties of a Star object used to make the scrolling background
        //on the main stage.
       
        //Integer to determine which layer of the background the Star object is in.
        private var zDistance:int;
       
        public function Star(xPos: int, yPos: int, zDistance: int)
        {
            //Constructor to initialize the Star object.
           
            this.x = xPos;
            this.y = yPos;
            this.alpha = .25 * (4 - zDistance);
            this.zDistance = zDistance;
        }
       
        public function get getZDistance():int {
           
            //This get function returns the integer variable zDistance. We use it to determine
            //which layer the Star object is in. The layer determines the brightness of the star
            //and how fast it will scroll as the game camera changes positions.
           
            return this.zDistance;
        }
    }

}