<

Sudoku, a complete MFC application.  Part 7

Published on
11,058 Points
2,958 Views
1 Endorsement
Last Modified:

Introduction:

Hints for the grid button.  Nested classes, templated collections.  Squash that darned bug!

Continuing from the sixth article about sudoku.  

Open the project in visual studio.

First we will finish with the SUD_SETVALUE message as this enables the validity checking (a tiny bit missing from the owner draw in the last article – the code in the owner draw was in place) and provides the base for the hinting mechanism.

Sudoku requires that the numbers 1..9 be placed in a block of nine positions, each digit can only appear once.  The classic version we deal with here has each row as one of these blocks, each column and the 9x9 grid split into 9 3x3 grids, each of which also constitutes a block.  All of this we will be wrapping inside a Grid which will contain all 81 individual cells.  One cell can appear in many blocks.

(Specially shaped blocks and diagonals are not covered with this version of the application – maybe a later version would allow user to define their own area.)  Each of these ‘blocks’ should have the information about the nine positions internally and expose functionality to determine which numbers are or are not used within the block.  They can also return information about the validity of numbers entered – eg. 7 is used twice in a block, which is not a valid solution to sudoku.

We therefore need two new classes, a CGrid and a  CBlock – which contains information about the nine positions.  Inside each cell in the grid we need to keep information to identify uniquely the nine positions such as the CWnd* pointer.  Theoretically one could store a CGridButton* pointer and call the object directly to find the contents but that strongly binds the classes together.  It would be nice to be able to solve a sudoku game automatically in the background (multithreading whooo!!) and that doesn’t necessarily require the usage of a CGridButton.  So we are also going to store the value alongside the ID of the position.

We could use two arrays, so the array index ‘n’ in both arrays would be the ID and the associated value.  That doesn’t make me happy: it is an easy place to make a coding error and get the two arrays out of synchronisation.  It makes more sense to have a structure (or class) that contains all of this information and then in the CGrid a collection of these – no possibility of the ID and the corresponding value becoming detached from one another.  This pairing is of no use to another class so we will make it a nested structure.  By that I mean it will be declared inside the class declaration of the CGrid, we will also use a templated array collection to keep these object in.  Using a templated collection allows the compiler to check if it should be stored and when accessed to determine it is the correct sort of object being returned.  Further to this nesting the information about a block could be internal to the Grid – that is to be responsible for organising the data.

Now we need to add a new class to the project, the CGrid class.  This is just a normal C++ class, no base class.  We have done this before but for simplicity – solution explorer, right click on project Sudoku, choose Add> class.  From the wizard select C++ in the tree view, then C++ Class from the list at the top right.  Click on Add button, enter CGrid as the class name then click Finish.  Let’s prepare the view first.

To the SudokuView.h file we need to add a #include for the grid.h file and add a new function for a custom message.

#pragma once
#include "grid.h"
….
private:
    CGrid m_Grid;
protected:
    afx_msg LRESULT OnSetValue(WPARAM wParam, LPARAM lParam);

Open in new window


In the OnInitialUpdate we need to assign the buttons to the blocks

    if(!m_bInitialised)
    {
        …CURRENT CODE IS HERE…

        //Now create the data structure contents
        for(int iRow = 0; iRow < 9; iRow++)
        {
            for(int iCol = 0; iCol < 9; iCol++)
            {
                //The return value ought to be checked, this just assumes it works
                m_Grid.AddCell(iRow, iCol, (UINT_PTR)&m_arWndButtons[iRow * 9 + iCol]);
            }
        }
    }

Open in new window


Note the CWnd* is cast to a UINT_PTR value otherwise there will be a compiler error.  For brevity we are not checking if the AddCell has succeeded but please remember that assuming things is poor practice.  This now links the display to the data.

To handle the custom message we need to add an entry into the MESSAGE_MAP – this allows the compiler to provide code linking the message to a function in the application.

BEGIN_MESSAGE_MAP(CSudokuView, CFormView)
    ON_MESSAGE(SUD_SETVALUE, &CSudokuView::OnSetValue)
END_MESSAGE_MAP()

Open in new window


And we need the body of the function also

LRESULT CSudokuView::OnSetValue(WPARAM wParam, LPARAM lParam)
{
    //Update the grid, note casting the WPARAM and LPARAM into the type of values expected by the function
    m_Grid.SetValue((UINT_PTR)wParam, (int)lParam);

    //Now flag each cell as having a valid entry
    for(int i = 0; i < 81; i++)
        m_arWndButtons[i].SetValid(true);

    //Set a flag that the window should be repainted - WHEN NOT BUSY
    Invalidate();
    
    //If there is any cell with a zero then the game is not yet finished, no further validity checking required
    for(int i = 0; i < 81; i++)
    {
        if(m_arWndButtons[i].GetValue() == 0)
            return 1;
    }

    //All the cells contain a non zero value, is the game correctly finished?
    //We must check each button and set the internal flag
    for(int i = 0; i < 81; i++)
    {
        if(!m_Grid.CheckValid((UINT_PTR)&m_arWndButtons[i])
            m_arWndButtons[i].SetValid(false);
    }

    return 1;
}

Open in new window


Now for the coding of the grid and the internal data structures it contains.

class CGrid
{
public:
    CGrid(void) {};
    ~CGrid(void);
    bool AddCell(int iRow, int iCol, UINT_PTR uiID);
    void SetValue(UINT_PTR uiID, int iValue);
    bool CheckValid(UINT_PTR uiID);

    void PrepareAllows(UINT_PTR uiID, bool* pbAllowed);

//Internal data structure declarations
private:
    struct stInfo        //Structure nested within the CGrid class - contains all 81 cells in the grid
    {
        stInfo() : m_uiID(0), m_iValue(0) {};    //Initialise variables
        UINT_PTR m_uiID;
        int m_iValue;
    };
    CArray<stInfo*, stInfo*>m_arCells;

    class CBlock        //class nested within the CGrid class
    {
    public:
        CBlock(void) {};
        ~CBlock(void) {};

        bool AddCell(stInfo* pCell);
        bool Contains(UINT_PTR uiID, int& iValue);
        bool CheckValue(int iValue);
        bool PrepareAllowedValues(UINT_PTR uiID, bool* pbAllowed);

        UINT_PTR GetID(int iIndex) { return m_arCells[iIndex]->m_uiID; } ;
        int GetValue(int iIndex) { return m_arCells[iIndex]->m_iValue; } ;
    private:
        CArray<stInfo*, stInfo*>m_arCells;        //POINTERS to the cells from the CGrid class
    };


//Actual data structures
    CBlock m_Row[9];
    CBlock m_Col[9];
    CBlock m_Square[9];

    bool CheckBlock(CBlock* pBlock, UINT_PTR uiID);
    void ProcessAllowsBlock(CBlock* pBlock, UINT_PTR uiID, bool* pbAllowed);
};

Open in new window


And for the .cpp file:

CGrid::~CGrid(void)
{
    //Release any memory assigned with new - prevent memory leaks
    for(int i = 0; i < m_arCells.GetCount(); i++)
        delete m_arCells[i];
    m_arCells.RemoveAll();
}

bool CGrid::AddCell(int iRow, int iCol, UINT_PTR uiID)
{
    stInfo* pCell = new stInfo;

    //Sanity - check the ID for uniqueness
    for(int i = 0; i < m_arCells.GetCount(); i++)
    {
        ASSERT(m_arCells[i]->m_uiID != uiID);
    }

    pCell->m_uiID = uiID;    //set the identifier
    m_arCells.Add(pCell);
    ASSERT(m_arCells.GetCount() <= 81);        //Max 81 cells in the array

    //Assign cells into blocks
    if(!m_Row[iRow].AddCell(pCell))
        return false;
    if(!m_Col[iCol].AddCell(pCell))
        return false;

    int iSquare = (3 * (iRow / 3)) + (iCol / 3);    //Work out which square this row/col combination belongs to
    if(!m_Square[iSquare].AddCell(pCell))
        return false;

    return true;
}

void CGrid::SetValue(UINT_PTR uiID, int iValue)
{
    //Loop through all the cells, et the value of the cell with that ID
    for(int i = 0; i < m_arCells.GetCount(); i++)
    {
        if(m_arCells[i]->m_uiID == uiID)
        {
            m_arCells[i]->m_iValue = iValue;
            return;
        }
    }
    ASSERT(FALSE);    //Cell not found for some reason
}




bool CGrid::CheckValid(UINT_PTR uiID)
{
    //Perform a validity check, each digit should only appear once in a block
    //This needs to be done for all the blocks
    //Note each block is an array so the variable itself is a POINTER to the first member of the array
    if(!CheckBlock(m_Row, uiID))    return false;
    if(!CheckBlock(m_Col, uiID))    return false;
    if(!CheckBlock(m_Square, uiID))    return false;
    return true;
}

bool CGrid::CheckBlock(CBlock* pBlock, UINT_PTR uiID)
{
    //There are nine individual blocks inside each array of blocks, check each if the cell with this ID is part of it 
    int iValue;
    for(int i = 0; i < 9; i++)
    {
        if(pBlock[i].Contains(uiID, iValue))    //is it in this block?  If yes then what value does it contain
        {
            return pBlock[i].CheckValue(iValue);
        }
    }
    return true;
}

void CGrid::PrepareAllows(UINT_PTR uiID, bool* pbAllowed)
{
    ProcessAllowsBlock(m_Row, uiID, pbAllowed);
    ProcessAllowsBlock(m_Col, uiID, pbAllowed);
    ProcessAllowsBlock(m_Square, uiID, pbAllowed);
}

void CGrid::ProcessAllowsBlock(CBlock* pBlock, UINT_PTR uiID, bool* pbAllowed)
{
    //Each array of blocks has nine entries
    for(int i = 0; i < 9; i++)
    {
        //delegate to the block to check
        //A cell can only belong to one row, one col and one square - a return of true meant 
        //the uiID belonged to a cell in this block
        if(pBlock[i].PrepareAllowedValues(uiID, pbAllowed))
            return;
    }
}


//Internal CBlock class

bool CGrid::CBlock::AddCell(stInfo* pCell)
{
    //Only can have 9 cells at most
    if(m_arCells.GetCount() > 9)
    {
        ASSERT(FALSE);
        return false;
    }

    m_arCells.Add(pCell);
    return true;
}


bool CGrid::CBlock::Contains(UINT_PTR uiID, int& iValue)
{
    iValue = 0;
    for(int i = 0; i < m_arCells.GetCount(); i++)
    {
        if(GetID(i) == uiID)
        {
            iValue = GetValue(i);
            return true;
        }
    }
    return false;
}

bool CGrid::CBlock::CheckValue(int iValue)
{
    //Value should appear at most once in the block
    int iCount = 0;    //initially no instances of this value found
    
    //Loop through all cells, increment the number of times we find the value being used
    for(int i = 0; i < m_arCells.GetCount(); i++)
    {
        if(GetValue(i) == iValue)
            iCount++;
    }
    //used once or less and the value is OK for this block
    return (iCount <= 1);
}

bool CGrid::CBlock::PrepareAllowedValues(UINT_PTR uiID, bool* pbAllowed)
{
    //returns true if the uiID matches with a member cell of this block
    //Check if the cell is in fact in this block, process if it is
    int iValue;  
    if(Contains(uiID, iValue))
    {
        //See which digits are used elsewhere in the block
        //the lParam passed in the message is the adress of the bool array 
        //cast it to a bool pointer fo accessing it
        //remember the array is zero based - so if digit 2 is in use we want the array member 1
        for(int i = 0; i < 9; i++)
        {
            int iValue = GetValue(i);
            
            //If the value is non zero (used) then set the allowed flag to false
            //A cell can be in other blocks, we can only turn it off - do NOT set to true
            if(iValue > 0)
                pbAllowed[iValue - 1] = false;
        }

        return true;
    }
    //cell not found in block
    return false;
}

Open in new window


Most of the code above is fairly straightforward.  A point of interest is the CheckValid and CheckBlock functions of the grid class.  Particularly the passing of arrays via pointers.  You can write some pretty neat (or dangerous or even just extremely difficult to read/understand/maintain) code using pointers.

Now let’s try it, compile and run it with the F5 key.  In the attached files is a presaved game called partial.  Load this – there is only one cell left to enter a value.  Enter the required digit (hint: 4) and see everything stay blue to indicate a good result.  Hmmm, they don’t do they, things have gone red.  Where is the bug?

Finding the bug.


In the CheckValue function of the CBlock we add an extra line then use a breakpoint (F9 key) so we have the following:

Code block
Run the application, load up this invalid game, enter 1 in the cell that is empty and the debugger should stop at the line with a red dot at the left.  Press F5 again – this runs the program until the line of code is run again.

Watch (autos) window
If you have a look at one of the debugger information windows – in this case the ‘auto’ window – you should see the current values held within pInfo.  (I have added the line concerning pInfo because the debugger doesn’t cope with the MFC collection classes very well – this simplifies our checking of the contents of the variables.)  The m_uiID is the ID of the cell and the m_iValue is the copy of the value in the cell.  m_iValue=0  Wrong.  It should be non zero but why is it zero.  We have loaded up a saved game, this sets the value in the GridButton – aaah, the view only receives the custom message to update the CBlock from a keyboard entry of the value.

Change the following:

void CGridButton::SetValue(int i) 
{ 
    m_iValue = i; 
    if(GetValue() > 0)
    {
        CString s((char)(GetValue() + '0')); 
        SetWindowText(s); 
    }
    else
        SetWindowText(""); 
}

Open in new window


To this:

void CGridButton::SetValue(int i) 
{ 
    m_iValue = i; 
    if(GetValue() > 0)
    {
        CString s((char)(GetValue() + '0')); 
        SetWindowText(s); 
    }
    else
        SetWindowText(""); 
    GetParent()->SendMessage(SUD_SETVALUE, (WPARAM)this, (LPARAM)GetValue());
}

Open in new window


Now try compiling and testing the invalid solution – bug squashed!

An aside:

There is a lot of functionality built into the Visual Studio development environment to help you track down and correct any bugs in your code.  Often a simple thing like a breakpoint and looking at the value in a variable can be enough to sort out the problem.  The breakpoint key (F9) puts a breakpoint onto a line of code, the debugger halts execution when that line of code is reached.  Now look at the debug menu – things like step into, step over and step out can help you move through the execution of your code, there are windows you can use to monitor the values of variables.  More advanced stuff includes the possibility to put optional arguments onto a breakpoint – instead of stopping everytime and checking if a variable has a value under 17 only stop when it is NOT under 17 for instance.

Now we can concentrate on the hints.  You might have noticed that in the DrawItem routine of the CGridButton there was an else statement that would be run should the button not have a value.  Here we will provide a visual feedback for the user about what numbers could be the required one.

This is the code we require (GridButton.cpp file, DrawItem function):

    else
    {
        //Draw hint
        CString s;
        CRect rc;
        GetClientRect(&rc);
        int iWidth = rc.Width() / 3;
        int iHeight = rc.Height() / 3;

        dc.SetTextColor(RGB(128,128,0));

        bool bAllow[9];
        //Set the flags all to be true
        memset(bAllow, true, sizeof(bAllow));
        GetParent()->SendMessage(SUD_PREPAREALLOWS, (WPARAM)this, (LPARAM)&bAllow);

        CRect rcClient;
        for(int row = 0; row < 3; row++)
        {
            for(int col = 0; col < 3; col++)
            {
                if(bAllow[row*3 + col])
                {
                    rcClient.top = row * iHeight;    rcClient.bottom = rcClient.top + iHeight;
                    rcClient.left = col * iWidth;    rcClient.right = rcClient.left + iWidth;

                    s.Format(_T("%d"), row*3 + col + 1);    //Zero based array but contents start at one
                    dc.DrawText(s, s.GetLength(), &rcClient, DT_SINGLELINE|DT_VCENTER|DT_CENTER);
                }
            }
        }
    }

Open in new window


Note we are using a local variable bAllow – the array of bool’s.  The address of this is being passed through the SendMessage function after being cast to an LPARAM.  

SendMessage vs PostMessage.

I’ve not said anything about this so far but there are two windows API functions for passing messages between windows.  SendMessage and PostMessage.  Both take the same parameters.  The important difference is that SendMessage waits for the recipient to process it (or windows to throw it away if no window has a handler for it) wheras PostMessage just adds the message to the recipient windows message queue then returns.  There are two very different things to bear in mind here.  SendMessage can lead to a deadlock (eg. A sends to B and as part of the processing B send to A).  PostMessage continues so you don’t know when the recipient will actually use the message, passing an address of a local variable (as here) will almost certainly lead to errors if not crashes in your app.

We also need to define the message we are passing – in the header of the GridButton class, next to the currently existing custom message

#define SUD_SETVALUE (WM_USER+101)
#define SUD_PREPAREALLOWS (WM_USER+102)

Open in new window


In the SudokuView we now should add the code for the handlers of this message.  In the header file we need a declaration for that function and another function it will use:

    afx_msg LRESULT OnPrepareAllows(WPARAM wParam, LPARAM lParam);

Open in new window


In the SudokuView.cpp file add the following line to the BEGIN_MESSAGE_MAP

    ON_MESSAGE(SUD_PREPAREALLOWS, &CSudokuView::OnPrepareAllows)

Open in new window


Then to the SudokuView.cpp file we add

LRESULT CSudokuView::OnPrepareAllows(WPARAM wParam, LPARAM lParam)
{
    m_Grid.PrepareAllows((UINT_PTR)wParam, (bool*)lParam);
    return 1;
}

Open in new window


Now we need to add some more code to the CGrid class for supporting the preparation of what is an allowed value.  In Grid.h we need a public function:

    void PrepareAllows(UINT_PTR uiID, bool* pbAllowed);

Open in new window


and a private function

    void ProcessAllowsBlock(CBlock* pBlock, UINT_PTR uiID, bool* pbAllowed);

Open in new window


in the .cpp file

void CGrid::PrepareAllows(UINT_PTR uiID, bool* pbAllowed)
{
    ProcessAllowsBlock(m_Row, uiID, pbAllowed);
    ProcessAllowsBlock(m_Col, uiID, pbAllowed);
    ProcessAllowsBlock(m_Square, uiID, pbAllowed);
}


void CGrid::ProcessAllowsBlock(CBlock* pBlock, UINT_PTR uiID, bool* pbAllowed)
{
    //Each array of blocks has nine entries
    for(int i = 0; i < 9; i++)
    {
        //delegate to the block to check
        //A cell can only belong to one row, one col and one square - a return of true meant 
        //the uiID belonged to a cell in this block
        if(pBlock[i].PrepareAllowedValues(uiID, pbAllowed))
            return;
    }
}

Open in new window


Now in the internal CBlock class we declare a public function:

        bool PrepareAllowedValues(UINT_PTR uiID, bool* pbAllowed);

Open in new window


And implement it thus:

bool CGrid::CBlock::PrepareAllowedValues(UINT_PTR uiID, bool* pbAllowed)
{
    //returns true if the uiID matches with a member cell of this block
    //Check if the cell is in fact in this block, process if it is
    int iValue;  
    if(Contains(uiID, iValue))
    {
        //See which digits are used elsewhere in the block
        //the lParam passed in the message is the adress of the bool array 
        //cast it to a bool pointer for accessing it
        //remember the array is zero based - so if digit 2 is in use we want the array member 1
        for(int i = 0; i < 9; i++)
        {
            int iValue = GetValue(i);
            
            //If the value is non zero (used) then set the allowed flag to false
            //A cell can be in other blocks, we can only turn it off - do NOT set to true
            if(iValue > 0)
                pbAllowed[iValue - 1] = false;
        }

        return true;
    }
    //cell not found in block
    return false;
}

Open in new window


Now compile and run the application.  You should see every cell displaying a small grid of 1..9.  Now load the test game and you should see something like:

 A game in progress
This is now displaying a hint to the user as to what is available, type in a five into the cell in the second row, first column – you should see the number five disappear as a hint from row 2, column 1 and the top left square of the grid.

Does this make it too simple?  Lets just show the hints for the button the mouse is over.  For this we need to look at mouse move events.

Make a small change to the CSudokuView::PreTranslateMessage function

    if(pMsg->message == WM_KEYDOWN)

Open in new window


becomes

    if(pMsg->message == WM_MOUSEMOVE)
        ProcessMouseMove(pMsg->pt);    //screen co-ordinates
    else if(pMsg->message == WM_KEYDOWN)

Open in new window


Now add a new private function - .h file

    void ProcessMouseMove(CPoint pt);

Open in new window


and .cpp file

void CSudokuView::ProcessMouseMove(CPoint pt)
{
    ScreenToClient(&pt);

    static CWnd* spLastWindow = NULL;    //reduce flickering when mouse moving on a button

    CWnd* pChild = ChildWindowFromPoint(pt);
    if((pChild != spLastWindow) && (pChild != this))
    {
        if(spLastWindow != NULL)
        {
            //Unset - mouse moving away from this window
            static_cast<CGridButton*>(spLastWindow)->ShowHints(false);
            spLastWindow->Invalidate();
            spLastWindow = NULL;
        }
        if(pChild != NULL)
        {
            //Find which button, if any, it is
            for(int i = 0; i < 81; i++)
            {
                if(&m_arWndButtons[i] == pChild)
                {
                    m_arWndButtons[i].ShowHints(true);
                    m_arWndButtons[i].Invalidate();
                    spLastWindow = &m_arWndButtons[i];
                }
            }
        }
    }
}

Open in new window


And in the CGridButton we need a couple of lines in the .h file to support this temporary display of the hints:

public:
    void ShowHints(bool bFlag) {m_bShowHint = bFlag; };
private:
    bool m_bShowHint;

Open in new window


and in the DrawItem we need a minor change to the hint drawing routine, the following is changed from:

    else
    {
        //Draw hint

Open in new window


to:

    else if(m_bShowHint)
    {
        //Draw hint

Open in new window


The m_bShowHint is set to false in the constructor’s initialisation list

,    m_bValid(true)
,    m_bShowHint(false)

Open in new window


Rebuild and run (F5 key), load the saved game and move the mouse around.  The hints should only appear when the mouse is over a button on the game.

Design – having a copy of the value in the gridbutton (m_iValue) is a really poor design, it should have a pointer to the structure containing the data for instance, at least something that doesn't duplicate data.  It would even simplify matters when entering a value from the keyboard.  However it meant I couldn’t demonstrate some techniques as I did do.

Conclusion:

We have extended our ownerdrawing to provide 'on the fly' visual hints.
We have nested classes to hide internal structures and used a templated collection for in memory data storage with the extra security the template brings.
We have had an introduction to debugging with breakpoints and watch windows.


Click here for the source code for this article


Previous article in the series is here:  Sudoku in MFC: Part 6
There we implemented a sinlgeton class and coded owner drawing of the button.

Next article in the series is here:  Sudoku in MFC: Part 8
Here we will be looking at working with a database to store and retrieve data in tables.  We will also find how to locate the exe file on the disc, generating random numbers for playing games randomly selected from storage and some simple error trapping.


Two points to bear in mind.
You may use the code but you are not allowed to distribute the resulting application either for free or for a reward (monetary or otherwise).  At least not without my express permission.
I will perform some things to demonstrate a point – it is not to be taken as that meaning it is a ‘best’ practice, in fact an alternative might be simpler and suitable.  Some points in the code would even be called poor design and a possible source of errors.
1
Comment
Author:AndyAinscow
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
0 Comments

Featured Post

Survive A High-Traffic Event with Percona

Your application or website rely on your database to deliver information about products and services to your customers. You can’t afford to have your database lose performance, lose availability or become unresponsive – even for just a few minutes.

Join & Write a Comment

This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
This tutorial will teach you the special effect of super speed similar to the fictional character Wally West aka "The Flash" After Shake : http://www.videocopilot.net/presets/after_shake/ All lightning effects with instructions : http://www.mediaf…
Suggested Courses

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month