Sudoku, a complete MFC application.  Part 11

AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT
Published:

Introduction:

Dialogs (2) modeless dialog and a worker thread.  Handling data shared between threads.  Recursive functions.

Continuing from the tenth article about sudoku.  

Last article we worked with a modal dialog to help maintain information in the database.  This time we will be working with a modeless dialog to help ‘solve’ a game of Sudoku.  That assistance is provided in a worker thread.

From the resource editor add a new dialog and change the caption to ‘Solve’ (properties menu of the dialog) and the ID to ID_DLG_SOLVE.  A modeless dialog needs the default OK and Cancel behaviours to be stopped. The default behaviour calls EndDialog which is not what should happen, the dialog should be dismissed with a call to DestroyWindow.  From the resource editor, on this new dialog, double click on the OK button.  The add new class wizard should start, enter CDlgSolve as the name and leave other options as defaults.  Click finish and the .h and .cpp files are created for us.  You might notice that no OnOK handler was created – so go back to the resource editor and double click the OK button again.  Now we have a function OnBnClickedOk() (earlier versions of Visual Studio created an OnOK function) which has one line of code – OnOK();  We need to comment this line out.  Repeat for the Cancel button so we have the following:

void CDlgSolve::OnBnClickedOk()
                      {
                          // modeless dialog - do not call OnOK
                          //OnOK();
                      }
                      
                      void CDlgSolve::OnBnClickedCancel()
                      {
                          // modeless dialog - do not call OnCancel
                          //OnCancel();
                      }

Open in new window


Now we can go back to the resource editor, select the OK and Cancel buttons and delete them.

Let us now use this to demonstrate some behaviour about dialogs.  From the resource editor open the main menu for the app, then the edit sub menu, select the ‘Solve’ menu point and add handlers for both the COMMAND ad UPDATE_COMMAND_UI events, they should be in the CSudokuView.  This solve function should be available for a game, if there is no game then the Info variable of the document is an empty string.

void CSudokuView::OnUpdateEditSolve(CCmdUI *pCmdUI)
                      {
                          pCmdUI->Enable(!GetDocument()->GetInfo().IsEmpty());    //Game being played - available to be solved
                      }

Open in new window


Now just for example purposes:

void CSudokuView::OnEditSolve()
                      {
                          CDlgSolve dlg;
                          dlg.DoModal();
                      }

Open in new window


Don’t forget to add the #include for the header or else we get an error on compilation.  Now press F5 key to compile and run.  Open a random game and click the ‘solve’ button.  We now get the dialog displayed.  Try to click the main application window – you can’t can you?  This is how a modal dialog behaves, it disables the other windows in the application – forces you to respond to this window and dismiss it before you can continue.  So now we can close this window, press the enter key (nothing), esc key (nothing) click on the little red ‘x’ at the top right of the window – aaargh nothing.  Don’t panic, go back to the IDE and press shift + F5 keys – this stops debugging and closes the app.

What is going on?  On a dialog if you press the enter key the default behaviour is to act as if the OK button was pressed – and we have disabled that.  Pressing the esc key has the default behaviour of the cancel button and we have stopped that.  The little red ‘x’ ?  Well that is the same as the cancel button.

Let’s fix the problem (that we can’t close the window) and at the same time also start the dialog as a modeless dialog.  We will enable the dismissal of the dialog by the esc key and the red ‘x’.  We need to modify the OnCancel routine to call DestroyWindow:

void CDlgSolve::OnBnClickedCancel()
                      {
                          // modeless dialog - do not call OnOK
                          //OnCancel();
                          DestroyWindow();
                      }

Open in new window


Now should you try the dialog again it will disappear with the esc key press but it also crashes – because this is now how you dismiss a modeless dialog NOT a modal dialog.

Back to the OnEditSolve function – next attempt.

void CSudokuView::OnEditSolve()
                      {
                          CDlgSolve dlg;
                          dlg.Create(CDlgSolve::IDD);
                          dlg.ShowWindow(SW_SHOW);
                      }

Open in new window


Try it again and you briefly see the dialog appear then disappear.  This is another mistake that people make with a modeless dialog – the code runs, the dialog is created then the code continues running (unlike a modal dialog – test it, put a breakpoint on DoModal and single step, it only continues after the DoModal finishes when the dialog is dismissed).  So in this case the code runs and the variable dlg goes out of scope and is destroyed.  <This is actually a common problem, especially with numbers of UI objects (fonts, brushes…) which one sees as created locally then selected into a window or DC, then the programmer wonders why the UI doesn’t use the new resource.>   The solution for our dialog is simple (well there are two ways, the other having the CDlgSolve variable a member of the class – declare in the .h file) in that we use the new keyword to create a new block of memory:

void CSudokuView::OnEditSolve()
                      {
                          CDlgSolve* pDlg = new CDlgSolve;
                          pDlg->Create(CDlgSolve::IDD);
                          pDlg->ShowWindow(SW_SHOW);
                      }

Open in new window


Great – or is it?  If you run the app, show the dialog then close the app you will see in the output window of the IDE the message – ‘Detected memory leaks!’.  

We can’t just delete the newly assigned memory before the function exits, fortunately the destruction of a window takes a route so that a virtual function called PostNcDestroy is called.  From the class view we select the properties of the class CDlgSolve, then click the button for overrides and add a handler for PostNcDestroy. At this point the window components are released, now we can release the memory:

void CDlgSolve::PostNcDestroy()
                      {
                      	CDialog::PostNcDestroy();
                      	delete this;	//modelesss dialog, release memory assigned with new
                      }

Open in new window


For those of you that don’t like the ‘new’ and ‘delete’ operations belonging to different classes the  ‘delete this’ in the PostNcDestroy is found in the MFC samples supplied by Microsoft.

Now we have a functional modeless dialog without any memory leaks.  A lot of work to display a dialog – so what not use a modal one as before?  Simple, display a modal dialog such as the Maintenance dialog and the main app is locked to mouse and keyboard.  Now display the solve dialog – the main app can still be interacted with.

Now we want to ‘solve’ the game.  Now I could run the code in the modeless dialog because the main app can still respond to user input but doing some computationally intensive work is a good place for using a worker thread.  (It also allows me to show you how to interact between threads with MFC based code).

We need the details of the game to be solved, so we will modify the constructor of the solve dialog and pass the details in as it is created.  The solve dialog also requires member variables to store the details and some code to display the game – very similar to the modal dialog displaying the current game.  I’ll just post the code here and won’t explain further.

void CSudokuView::OnEditSolve()
                      {
                          char arGame[82];
                          ZeroMemory(arGame, 82);
                          for(int i = 0; i < 81; i++)
                              arGame[i] = '0' + m_arWndButtons[i].GetValue();
                      
                          CDlgSolve* pDlg = new CDlgSolve(m_arGame);
                          pDlg->Create(CDlgSolve::IDD);
                          pDlg->ShowWindow(SW_SHOW);
                      }
                      class CDlgSolve : public CDialog
                      {
                          DECLARE_DYNAMIC(CDlgSolve)
                      
                      public:
                          CDlgSolve(LPCTSTR cpszGame, CWnd* pParent = NULL);   // custom constructor
                          virtual ~CDlgSolve();
                      
                      // Dialog Data
                          enum { IDD = IDD_DLG_SOLVE };
                      
                      protected:
                          virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
                      
                          DECLARE_MESSAGE_MAP()
                      public:
                          afx_msg void OnBnClickedOk();
                          afx_msg void OnBnClickedCancel();
                      protected:
                          virtual void PostNcDestroy();
                      private:
                          CString m_szGame;
                      public:
                          afx_msg void OnPaint();
                      };
                      #include "stdafx.h"
                      #include "Sudoku.h"
                      #include "DlgSolve.h"
                      #include "SudokuDCPainter.h"
                      
                      
                      // CDlgSolve dialog
                      
                      IMPLEMENT_DYNAMIC(CDlgSolve, CDialog)
                      
                      CDlgSolve::CDlgSolve(LPCTSTR cpszGame, CWnd* pParent /*=NULL*/)
                          : CDialog(CDlgSolve::IDD, pParent)
                          , m_szGame(cpszGame)
                      {
                      
                      }
                      
                      CDlgSolve::~CDlgSolve()
                      {
                      }
                      
                      void CDlgSolve::DoDataExchange(CDataExchange* pDX)
                      {
                          CDialog::DoDataExchange(pDX);
                      }
                      
                      
                      BEGIN_MESSAGE_MAP(CDlgSolve, CDialog)
                          ON_BN_CLICKED(IDOK, &CDlgSolve::OnBnClickedOk)
                          ON_BN_CLICKED(IDCANCEL, &CDlgSolve::OnBnClickedCancel)
                          ON_WM_PAINT()
                      END_MESSAGE_MAP()
                      
                      
                      // CDlgSolve message handlers
                      
                      void CDlgSolve::OnBnClickedOk()
                      {
                          // modeless dialog - do not call OnOK
                          //OnOK();
                      }
                      
                      void CDlgSolve::OnBnClickedCancel()
                      {
                          // modeless dialog - do not call OnCancel
                          //OnCancel();
                          DestroyWindow();
                      }
                      
                      void CDlgSolve::PostNcDestroy()
                      {
                          CDialog::PostNcDestroy();
                          delete this;    //modelesss dialog, release memory assigned with new
                      }
                      
                      void CDlgSolve::OnPaint()
                      {
                          CPaintDC dc(this); // device context for painting
                          // TODO: Add your message handler code here
                          // Do not call CDialog::OnPaint() for painting messages
                      
                          CSudokuDCPainter painter;
                          painter.Paint(this, &dc, IDC_STATIC_BOUNDARY, m_szGame);
                      }

Open in new window


You can now compile, load a random game and click the ‘solve’ option – you should see the dialog appear with the game plus any modifications you have made to it.  Leave the solve dialog alone and select another random game and click on ‘solve’ again.  A second dialog appears with this second game.  If you close the main app then both the ‘solve’ dialogs also close and in the IDE there is no warning about memory leaks.

Now for the worker thread.  

Add a handler for the OnInitDialog function of the CDlgSolve – properties of the class…  Here we will start the thread.  We need to pass some information to the thread, the game to be solved and the window handle of the solve dialog for receiving information back.  Note a very important point.  MFC is NOT thread safe and passing MFC objects such as CWnd pointers between threads is dangerous.  Sometimes it might work, other times one runs into thread specific information in the MFC object which for the other thread is NULL and boom!!  Your app crashes.  Unfortunately, even here at EE, one sees experts suggesting passing MFC objects between threads is OK.

struct stSolveInfo
                      {
                          HWND hWndParent;
                          char szGame[82];
                          char szGameInProgress[82];
                          bool bSuccess;
                          unsigned long ulCounter;
                          CCriticalSection csAccessControl;
                          CEvent ceCloseThread;
                          CEvent ceThreadIsFinished;
                      };

Open in new window


Above are the details of the information package to be shared (passed) to the thread.  The HWND is for passing messages from the thread to the dialog via the window handle (which is NOT an MFC object, it is a native windows variable).  The character array containing the original game and also one for a game being processed in the thread.  A Boolean flag to determine if the game is solved and an unsigned long to give an indication of how many attempts have been made to find a solution.  Next comes a CriticalSection – this will force one thread to wait if the other thread is performing some action inside the critical section.  This is typically reading/writing into a common variable.  Finally two CEvent objects, these allow an interthread communication.  An event can be raised (set to ‘true’ or ‘false’) in one thread and checked in the other thread.  The checking mechanism is rather neat, one can specify a wait time.  For the use here one event will instruct the thread is has to stop working – the event is checked each time the thread goes through a loop or periodic action.  The other is set when the thread actually finishes so the dialog ‘knows’ the thread is ended.  This is required should the user close the ‘solve’ dialog whilst the thread is running.  One can see that implemented in the OnDestroy function of the CSolveDialog.  I also pass a custom message from the thread to the dialog to indicate the thread is working.  The dialog uses the critical section to prevent writing to the character array by the thread whilst the dialog is reading and displaying that.

The thread function to solve the game:

I’m going to use two methods.  The first is a monte carlo method (random numbers).  This is totally unsuitable for this operation in reality.  It will find a solution.  Maybe in one second, maybe the universe has expired first.  Consider – 81 cells.  Say that 3 in each block of 9 have a number assigned to them so that leaves 54 cells.  Now we put a random number 1..9 in each cell and test, and say we can do that 1000 times per second.  For simplicity let’s say that is 10 random numbers so 10 to the power 54 divided by 1000 seconds to explore each possibility PROVIDING there is no repetition in the worst case that the very last possibility is the solution.  However it does nicely show the system working and the solve dialog being responsive to user input whilst the thread is working.

The second method uses recursion and brute force.  I put a value into a cell, providing it doesn’t have a value already, and then I go to the next cell (top left start, work along row 1 then row 2 until bottom right is reached).  At each cell I check what values would be allowed (ie. Not used in any block that cell belongs to).  If there are no possible value then one, or more, of the numbers already set are false so I return from the recursive function to effectively undo the last change.  Eventually it will fill the grid and a solution is found, or all possibilities are exhausted and no solution exists.

I also use a #define to allow a quick switching between the two methods, just comment the #define out or uncomment it.  You should see the code in the editor change colour to indicate which code segments will be considered for compilation.

Here is the code for the header file

#pragma once
                      
                      // CDlgSolve dialog
                      #include "afxmt.h"        //For the CCriticalSection, CEvent classes
                      
                      struct stSolveInfo
                      {
                          HWND hWndParent;
                          char szGame[82];
                          char szGameInProgress[82];
                          bool bSuccess;
                          unsigned long ulCounter;
                          CCriticalSection csAccessControl;
                          CEvent ceCloseThread;
                          CEvent ceThreadIsFinished;
                      };
                      
                      class CDlgSolve : public CDialog
                      {
                          DECLARE_DYNAMIC(CDlgSolve)
                      
                      public:
                          CDlgSolve(LPCTSTR cpszGame, CWnd* pParent = NULL);   // custom constructor
                          virtual ~CDlgSolve();
                      
                      // Dialog Data
                          enum { IDD = IDD_DLG_SOLVE };
                      
                      protected:
                          virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
                      
                          DECLARE_MESSAGE_MAP()
                      public:
                          afx_msg void OnBnClickedOk();
                          afx_msg void OnBnClickedCancel();
                      protected:
                          virtual void PostNcDestroy();
                      private:
                          CString m_szGame;
                      public:
                          afx_msg void OnPaint();
                          virtual BOOL OnInitDialog();
                      
                      private:
                          afx_msg LRESULT OnSolveProgress(WPARAM wParam, LPARAM lParam);
                          stSolveInfo m_stSolveInfo;
                      public:
                          afx_msg void OnDestroy();
                      };

Open in new window


And for the implementation

// DlgSolve.cpp : implementation file
                      //
                      
                      #include "stdafx.h"
                      #include "Sudoku.h"
                      #include "DlgSolve.h"
                      #include "SudokuDCPainter.h"
                      #include "randomnumber.h"
                      #include "grid.h"
                      
                      //comment out the following to switch between mote carlo and brute force methodds in the thread.
                      #define __MONTE_CARLO_THREAD__
                      
                      
                      UINT SolveSudokuProc(LPVOID pParam);
                      void FillTempGame(CGrid& grid, stSolveInfo *pstSolveInfo, bool bGameSuccess);
                      
                      #ifndef __MONTE_CARLO_THREAD__
                      bool ProcessCell(CGrid& grid, int iCell, stSolveInfo *pstSolveInfo);
                      #endif
                      
                      
                      
                      // CDlgSolve dialog
                      #define SOLVE_PROGRESS (WM_USER+105)
                      
                      IMPLEMENT_DYNAMIC(CDlgSolve, CDialog)
                      
                      CDlgSolve::CDlgSolve(LPCTSTR cpszGame, CWnd* pParent /*=NULL*/)
                          : CDialog(CDlgSolve::IDD, pParent)
                          , m_szGame(cpszGame)
                      {
                      
                      }
                      
                      CDlgSolve::~CDlgSolve()
                      {
                      }
                      
                      void CDlgSolve::DoDataExchange(CDataExchange* pDX)
                      {
                          CDialog::DoDataExchange(pDX);
                      }
                      
                      
                      BEGIN_MESSAGE_MAP(CDlgSolve, CDialog)
                          ON_BN_CLICKED(IDOK, &CDlgSolve::OnBnClickedOk)
                          ON_BN_CLICKED(IDCANCEL, &CDlgSolve::OnBnClickedCancel)
                          ON_WM_PAINT()
                          ON_MESSAGE(SOLVE_PROGRESS, &CDlgSolve::OnSolveProgress)
                          ON_WM_DESTROY()
                      END_MESSAGE_MAP()
                      
                      
                      // CDlgSolve message handlers
                      
                      void CDlgSolve::OnBnClickedOk()
                      {
                          // modeless dialog - do not call OnOK
                          //OnOK();
                      }
                      
                      void CDlgSolve::OnBnClickedCancel()
                      {
                          // modeless dialog - do not call OnCancel
                          //OnCancel();
                          DestroyWindow();
                      }
                      
                      void CDlgSolve::PostNcDestroy()
                      {
                          CDialog::PostNcDestroy();
                          delete this;    //modelesss dialog, release memory assigned with new
                      }
                      
                      void CDlgSolve::OnPaint()
                      {
                          CPaintDC dc(this); // device context for painting
                          // TODO: Add your message handler code here
                          // Do not call CDialog::OnPaint() for painting messages
                      
                          CSudokuDCPainter painter;
                          painter.Paint(this, &dc, IDC_STATIC_BOUNDARY, m_szGame);
                      }
                      
                      BOOL CDlgSolve::OnInitDialog()
                      {
                          CDialog::OnInitDialog();
                      
                          m_stSolveInfo.hWndParent = GetSafeHwnd();
                          ZeroMemory(m_stSolveInfo.szGame, sizeof(m_stSolveInfo.szGame));
                          strcpy(m_stSolveInfo.szGame, m_szGame);
                          memcpy(m_stSolveInfo.szGameInProgress, m_stSolveInfo.szGame, 82);
                          m_stSolveInfo.bSuccess = false;
                          m_stSolveInfo.ulCounter = 0;
                          m_stSolveInfo.ceCloseThread.ResetEvent();
                          m_stSolveInfo.ceThreadIsFinished.ResetEvent();
                      
                          CWinThread* pThread = AfxBeginThread(SolveSudokuProc, &m_stSolveInfo, 0, 0, CREATE_SUSPENDED);
                          if(pThread  != NULL)
                          {
                              pThread->m_bAutoDelete = true;
                              pThread->ResumeThread();
                          }
                      
                          return TRUE;  // return TRUE unless you set the focus to a control
                          // EXCEPTION: OCX Property Pages should return FALSE
                      }
                      
                      LRESULT CDlgSolve::OnSolveProgress(WPARAM wParam, LPARAM lParam)
                      {
                          //Remove multiple copies of the message should there be any in the queue
                          //else this function is being called continuously and hogging the main thread of the app
                          MSG msg;
                          while(PeekMessage(&msg, NULL, SOLVE_PROGRESS, SOLVE_PROGRESS, PM_REMOVE));
                      
                          CString s;
                      
                          m_stSolveInfo.csAccessControl.Lock();
                          m_szGame = m_stSolveInfo.szGameInProgress;
                      
                          if(m_stSolveInfo.bSuccess)
                              s.LoadString(IDS_SUCCESS);
                          else
                          {
                              if(m_stSolveInfo.ulCounter == (unsigned long)-1)
                                  s.LoadString(IDS_FAIL);
                              else
                                  s.Format(IDS_TRIES, m_stSolveInfo.ulCounter);
                          }
                          m_stSolveInfo.csAccessControl.Unlock();
                      
                          SetDlgItemText(IDC_STATIC_PROGRESS, s);
                      
                          Invalidate();
                          UpdateWindow();
                      
                          return 1;
                      }
                      
                      void CDlgSolve::OnDestroy()
                      {
                          // Signal the thread to close
                          m_stSolveInfo.ceCloseThread.SetEvent();
                      
                          //Wait for it actually to be closed
                          ::WaitForSingleObject(m_stSolveInfo.ceThreadIsFinished.m_hObject, INFINITE);
                      
                          CDialog::OnDestroy();
                      }
                      
                      #ifdef __MONTE_CARLO_THREAD__
                      
                      UINT SolveSudokuProc(LPVOID pParam)
                      {
                          //The pParam needs to be cast to the actual type of object it is
                          stSolveInfo *pstSolveInfo = (stSolveInfo*)pParam;
                      
                          //Initialise the grid
                          CGrid grid;
                          int iRow, iCol, iCell, iValue;
                          for(iRow = 0; iRow < 9; iRow++)
                          {
                              for(iCol = 0; iCol < 9; iCol++)
                              {
                                  iCell = iRow * 9 + iCol;
                                  grid.AddCell(iRow, iCol, (UINT_PTR)iCell);
                              }
                          }
                      
                          CRandomNumber random;
                      
                          while(true)
                          {
                              //If the solve dialog is closing we need to stop the thread
                              if(::WaitForSingleObject(pstSolveInfo->ceCloseThread.m_hObject, 0) == WAIT_OBJECT_0)
                              {
                                  pstSolveInfo->ceThreadIsFinished.SetEvent();
                                  return 0;
                              }
                      
                              //Fill the grid
                              for(iRow = 0; iRow < 9; iRow++)
                              {
                                  for(iCol = 0; iCol < 9; iCol++)
                                  {
                                      iCell = iRow * 9 + iCol;
                                      iValue = pstSolveInfo->szGame[iCell] - '0';
                      
                                      if(iValue == 0)
                                          grid.SetValue((UINT_PTR)iCell, random.GetRandom(1, 9));
                                      else
                                          grid.SetValue((UINT_PTR)iCell, iValue);
                                  }
                              }
                      
                              //Now check if the game is valid
                              bool bGameSuccess = true;
                              for(iCell = 0; iCell < 81; iCell++)
                              {
                                  if(!grid.CheckValid((UINT_PTR)iCell))
                                  {
                                      bGameSuccess = false;
                                      break;
                                  }
                              }
                      
                              //Fill the game in progress info
                              FillTempGame(grid, pstSolveInfo, bGameSuccess);
                      
                              //Inform parent, OCCASIONALLY else the main thread is overloaded
                              if(bGameSuccess || ((++pstSolveInfo->ulCounter & 0xFF) == 0))
                              {
                                  if(bGameSuccess)
                                      pstSolveInfo->ulCounter = (unsigned long)-1;
                                  PostMessage(pstSolveInfo->hWndParent, SOLVE_PROGRESS, 0, 0);
                              }
                      
                              if(bGameSuccess)    //task finished
                                  break;    
                          }
                      
                          pstSolveInfo->ceThreadIsFinished.SetEvent();
                          return 0;
                      }
                      
                      #else
                      
                      UINT SolveSudokuProc(LPVOID pParam)
                      {
                          //The pParam needs to be cast to the actual type of object it is
                          stSolveInfo *pstSolveInfo = (stSolveInfo*)pParam;
                      
                          //Initialise the grid
                          CGrid grid;
                          int iRow, iCol, iCell, iValue;
                          for(iRow = 0; iRow < 9; iRow++)
                          {
                              for(iCol = 0; iCol < 9; iCol++)
                              {
                                  iCell = iRow * 9 + iCol;
                                  grid.AddCell(iRow, iCol, (UINT_PTR)iCell);
                      
                                  iValue = pstSolveInfo->szGame[iCell] - '0';
                                  grid.SetValue((UINT_PTR)iCell, iValue);
                              }
                          }
                      
                          unsigned long ulCounter = 0;
                          iCell = 0;
                      
                          //Start the recursive procedure
                          ProcessCell(grid, iCell, pstSolveInfo);
                      
                          //Now check if the game is valid
                          bool bGameSuccess = true;
                          for(iCell = 0; iCell < 81; iCell++)
                          {
                              if(!grid.CheckValid((UINT_PTR)iCell))
                              {
                                  bGameSuccess = false;
                                  break;
                              }
                          }
                      
                          //Fill the game in progress info
                          FillTempGame(grid, pstSolveInfo, bGameSuccess);
                          pstSolveInfo->ulCounter = (unsigned long)-1;
                      
                          PostMessage(pstSolveInfo->hWndParent, SOLVE_PROGRESS, 0, 0);
                      
                          pstSolveInfo->ceThreadIsFinished.SetEvent();
                          return 0;
                      }
                      
                      bool ProcessCell(CGrid& grid, int iCell, stSolveInfo *pstSolveInfo)
                      {
                          //If the solve dialog is closing we need to stop the thread
                          if(::WaitForSingleObject(pstSolveInfo->ceCloseThread.m_hObject, 0) == WAIT_OBJECT_0)
                          {
                              pstSolveInfo->ceThreadIsFinished.SetEvent();
                              return true;    //unwind the recursion stack
                          }
                      
                          //we work through each cell and use the possible values it could have
                          //and recurse into this function with the next cell
                          //either we get no possible values allowed or eventually the solution of the game
                          if(iCell == 81) //The cell before (81) had a possible value so the game is solved
                              return true;    //unwind the recursion stack
                      
                          //If this has a 0 then we need to find what is possible for it and start the processing OR we move to the next cell
                          bool bResult = false;
                          if(grid.GetValue(iCell) == 0)
                          {
                              bool bAllowed[9]; 
                              FillMemory(bAllowed, sizeof(bAllowed), true);    //initially all are allowed
                              grid.PrepareAllows(iCell, bAllowed);
                      
                              //Now loop through the allowed values, set to that then move to next cell via recursion
                              for(int i = 0; i < 9; i++)
                              {
                                  if(bAllowed[i])
                                  {
                                      //This is a possible, set the cell value
                                      grid.SetValue(iCell, i+1);    //zero based counting - the value is actually one greater than the index
                                      bResult = ProcessCell(grid, iCell + 1, pstSolveInfo);
                                      if(bResult == true)
                                          break;
                                  }
                              }
                              
                              if(bResult == false)
                              {
                                  //unset the value here prior to returning
                                  grid.SetValue(iCell, 0);
                              }
                          }
                          else
                              bResult = ProcessCell(grid, iCell + 1, pstSolveInfo);
                      
                      
                          //when starting to unwind we pump the attempted counter to the parent
                          //note this is really just to give a crude feedback
                          pstSolveInfo->ulCounter++;
                          if((pstSolveInfo->ulCounter & 0xFF) == 0)    //every 256 increments
                          {
                              //Fill the game in progress info
                              FillTempGame(grid, pstSolveInfo, false);
                      
                              PostMessage(pstSolveInfo->hWndParent, SOLVE_PROGRESS, 0, 0);
                          }
                      
                          return bResult;
                      }
                      
                      #endif
                      
                      void FillTempGame(CGrid& grid, stSolveInfo *pstSolveInfo, bool bGameSuccess)
                      {
                          pstSolveInfo->csAccessControl.Lock();
                          for(int iCell = 0; iCell < 81; iCell++)
                          {
                              pstSolveInfo->szGameInProgress[iCell] = '0' + grid.GetValue((UINT_PTR)iCell);
                          }
                          pstSolveInfo->bSuccess = bGameSuccess;
                          pstSolveInfo->csAccessControl.Unlock();
                      }

Open in new window


Note that I don’t use a critical section to prevent simultaneous read/write to the counter.  For our purposes here it doesn’t make any difference if the thread overwrites the counter as it is partially read.

Conclusion (1):

We have seen how to create and destroy modeless dialogs.
We have shared data between threads and communicated with MFC objects from a different thread.
We have seen recursive functions in operation.
We have seen a 'Monte Carlo' technique in operation.


Conclusion (2):

The set of articles has been about writing code, not about design.  The design (data, business, user tiers) has not been adressed.
At one point there was a bug which we had to find.  It was totally due to making COPIES of data - don't do that in the real world.  It is hard to describe just how bad that can be.
Also not making the copy as we did would actually have made some bits easier to code - but then I couldn't demonstrate a technique that I wanted to.
So, is this application good or bad?
It works and does exactly what it should do and does it well. Good.
It is not easy to make fundamental changes.  Bad (but that is due to the structure of the app).
Oh, and don't try to use it for testing if a game just designed is 'solvable' - this app just finds the [bold]first[/bold] possible solution if one exists, it doesn't check for a second or further possible solution.



This article concludes the suite of articles.  I hope it has been of interest and even educational.  I may well use this as a base for demonstrating further programming techniques and use of the Visual Studio IDE.


Click here for the source code for this article


Previous article in the series is here:  Sudoku in MFC: Part 10



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
5,694 Views
AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT

Comments (0)

Have a question about something in this article? You can receive help directly from the article author. Sign up for a free trial to get started.