SudokuSolver v1.08

Welcome to SudokuSolver, a set of C++ classes which implement support for the classic 9*9 Sudoku puzzle as well as a simple MFC Dialog based app which generates and solves Sudoku puzzles.

Features

• Provides a simple C++ Header only module and class to represent a Sudoku grid. The class in this header is called CSudokuGrid and provides most of the reusable functionality.
• The sample app provides a simple VC 2017 dialog based Sudoku puzzle generator and solver. If you click the "Generate" button in the sample app, it will generate a solvable puzzle with the specified number of cells left empty (as taken from the empty cells edit box). The algorithm to generate a puzzle is based on the information from http://blog.forret.com/2006/08/a-sudoku-challenge-generator/.
• The solving code demonstrates how to integrate MFC multithreading into a algorithm in a manner such that it is cancellable and provides UI feedback while running without the need to provide a blocking modal dialog UI. The logic for this is spread across the methods of the CSudokuSolverDlg class. The solving code is based on a subset of the information from http://norvig.com/sudoku.html.
• As the solving code runs it will set the background colour of the cell which it is operating on in red and indicate the depth of the algorithm using "[]" in the cell. The code to do this is executing from a worker thread but to update the UI the main thread must do the actual work. To avoid overloading the main thread with update requests, the worker thread implements logic to only update the UI every 100 ms. To review this code, please take a look at the CSudokuSolverDlg::Solve method.
• When the solving code finds a solution it will set the background colour of any updated cells to green.
• The background colouring of the edit boxes is done with a very simple CColorEdit MFC class which is derived from the standard CEdit control class. This class demonstrates how to implement background colors in an edit box using MFC using the standard WM_CTLCOLOR message handling mechanism.
• Please note that as the solving algorithm is currently implemented it will not guarantee that there is only one solution to the provided puzzle and instead will just pick the first solution found.
• The code demonstrates the various pieces of code required to implement MFC multithreading for a long running algorithm while keeping the UI responsive. This includes:
  • Construction and clean destruction of worker threads
  • Correct use of Thread priorities
  • Using asynchronous UI notification using Windows messaging using PostMessage
  • Implementing a cancellable thread using WaitForSingleObject and MFC Win32 events
  • Status reporting from the worker thread using windows message, critical sections and MFC message maps
  • Implementing worker threads in MFC using non static class methods via the LPVOID parameter to the AfxBeginThread API
  • Implementing worker threads in MFC which are awaitable from their creation thread
  • Avoiding choking the UI thread with too many notifications from the worker thread
• All told the multithreading logic is spread across custom WM_* messages, the MFC message map, the UI thread, class member variables, static and non static methods. I plan to re-implement the solving algorithm in a future version of the code using the PPL (Parallel Patterns Library) to be able to compare the custom MFC implementation currently in the code with the hopefully cleaner implementation using PPL and lambdas. This should also allow me to tweak the algorithm to take advantage of today's multi-core processors with relative ease without the need to write a custom thread pool implementation.

Usage

• To use the CSudokuGrid class in your project simply #include "Sudoku.h" from the test application in your application.
• The classes are only supported on VC 2017 or later but the CSudokuGrid module should be compilable on earlier VC versions.
• Included in the download is a VC 2017 dialog based application which demonstrates most of the functionality as well as a simple Sudoku puzzle generator and solver.

Copyright

• You are allowed to include the source code in any product (commercial, shareware, freeware or otherwise) when your product is released in binary form.
• You are allowed to modify the source code in any way you want except you cannot modify the copyright details at the top of each module.
• If you want to distribute source code with your application, then you are only allowed to distribute versions released by the author. This is to maintain a single distribution point for the source code.

History

v1.08 (8 May 2022)

• Updated copyright details.
• Updated the code to use C++ uniform initialization for all variable declarations.

v1.07 (5 April 2020)

• Updated copyright details.
• Fixed more Clang-Tidy static code analysis warnings in the code.

v1.06 (28 September 2019)

• Fixed a number of compiler warnings when the code is compiled with VS 2019 Preview

v1.05 (3 June 2019)

• Updated copyright details.
• Updated the code to clean compile on VC 2019

v1.04 (30 December 2018)

• Updated copyright details.
• Fixed a number of C++ core guidelines compiler warnings. These changes mean that the code will now only compile on VC 2017 or later.

v1.03 (17 May 2016)

• Updated copyright details.
• Updated the sample app to compile cleanly using /analyze
• Updated the code to compile cleanly on VC 2015

v1.02 (9 November 2013)

• Fixed a bug in the Hint algorithm. In v1.01 it would put values in cells which were the first possible value for a cell which had multiple choices. Now the code determines if it has run out of definite cells to fill as you repeatedly hit the "Hint" button and prompts the user to allow the program to solve the puzzle so that it can provide the next hint.
• General cleanup to the code in SudokuSolverDlg.cpp

v1.01 (5 November 2013)

• App now includes support for a Hint feature where it will fill in the next appropriate cell but not do a complete solve of the puzzle.

v1.0 (3 November 2013)

• Initial Public release

Contacting the Author

PJ Naughter
Email: pjna@naughter.com
Web: http://www.naughter.com
8 May 2022