Dancing Links Sudoku Solver and Explorer

Published on: March 24, 2025Download DLXSudokuSolver Source Code

Introduction

Dancing Links is an algorithm introduced by the brilliant American computer scientist Donald Knuth. This technique is well known for efficiently solving Sudoku grids and assessing their validity — including detecting unsolvable puzzles or those with multiple solutions.

The first version of the application was based on the Sudoku solver ZeroDlx written by Jim Schirle. The code was updated to be used as a C++ class and modified to use the Hungarian notation. The new release V2.0 was thouroughly re-written to use STL (ISO C++ 20) and to allow the display of the progress of the solving algorithm.

Naming Convention

This naming convention is quite classic and stems from my very first experience of C programmming the OS/2 API of Microsoft/IBM in the late eighties

• Source files .cpp and ;h: the files are named following the name of the class with the first characater 'C' removed.
  For example, the implementation and include files of the class CButtonBoard are named, respectively, ButtonBoard.cpp and ButtonBoard.h
• Functions and variables names: the first lettre of each word of classes, functions and variables are capitalized (PascalCase convention)
• Class members: the name of the class members start with m_
• Class constants: the name of the constants start with c_
• Global variables: the names of the global variables start with g_. This type of variable is avoided as much as possible.
• Variables Naming: the name of the variables follow the Hungarian notation (well, arranged to fit my needs and feelings)
  Some typical variables naming (non-exhaustive list)

  Variable Type	Starting Char.	Example
  bool	b	Class Member: m_bCovered Class Constant: c_bActive
  integer	n	Class Member: m_nLength Class Constant: c_nMaxCount
  long	l	Class Member: m_lData Function Local Var.: lLength
  unsigned long	ul	Class Member: m_ulData
  float	f	Class Member: m_fRadius
  double	d	Class Constant: m_dPi
  std::wstring	wstr	Global variable: g_wstrUserName Function Local var.: wstrName
  std::vector	vctr	Class member: m_vctrSolution Function Local var.: vctrData
  array	a	Class Array of integer: m_anMaxValue Function Local var.: anData
  pointer	p	Class Pointer to integer: m_pnValue<br>Global Pointer to array of long: g_palDataNdx
  Color	rgb	Function Local var.: rgbBkg Class member array of color: m_argbTextColor

• Pre-Processor Macros and constants: all characters are Uppercase. Note that, as recommended for modern C++, the constants are defined in the classes as constexpr
  Example: static constexpr COLORREF c_rgbCandidate = RGB(51, 153, 255);

Application Main Settings

The application is written in C++ using the Microsoft IDE Visual Studio Community Edition 2022.

The configuration is quite standard for a 64-bits application:

1. Latest Plateform Toolset (v143)
2. C++ Language Standard: ISO C++ 20

1. Use of MFC: Use MFC in a Static Library (so I don't have to worry about MFC dlls)
2. Character Set: Use Unicode Character Set

Application Classes

The application is made of the following classes:

1. CDLXSudokuSolverApp (derived from CWinApp): the main MFC application class that handles initialization, execution, and termination of the DLXSudokuSolver application.
2. CDLXSudokuSolverDlg (derived from CDialogEx): DLXSudokuSolver is a simple dialog-based application. This class manages user interaction and updates the graphical interface.
3. CDLXSolver: the base class implementing the core Dancing Links algorithm.
4. DLXNode: a foundational support class used internally by CDLXSolver.
5. DLXColumn: a companion class derived from DLXNode, used for column tracking in the Dancing Links structure.
6. CButtonBoard: a custom button class (derived from CButton) used to graphically display the Sudoku board.
7. CAboutDlg: the dialog class (derived from CDialogEx) that displays the “About” box of the application.
8. DebugTrace: a namespace providing internal tracing tools for monitoring and debugging the execution flow.

Note: the namespace DebugTrace is heavily used in DLXSodukuSolver and provides several macros (DBG_LOG, DBG_TMB, DBG_TME, ..) to trace the execution of the application. Complete explanations about this namespace is available in the C++ Section.

Process Execution

When the user click on the 'Solve' button, the function CDLXSudokuSolverDlg::OnSolve() is called by the MFC framework.

The main actions are:

• Create a new instance of the solver
• Draw the Board with the givens
• Call the Solver function that actually starts the Solver

    // Build and Initialize Solver Instance

    m_pDLXSolver = new CDLXSolver(this->GetSafeHwnd(), static_cast(str), GetDelay(), nSolverMode);

    // Update Board with Initial Sudoku Data

    m_ButtonDLXBoard.DrawBoard(m_pDLXSolver->m_nGroupSize, m_pDLXSolver->m_vctrSudoku);

    // Start Dancing Links Solver

    m_pDLXSolver->StartSolver();
	

The parameters of the Solver constructor are the following:

• HWND hWnd: Handle to Window to send messages to (WM_SOLVING_PROGRESS, WM_SOLVING_FINISH)
• const std::wstring wstr: STL string with Sudoku givens (candidates as 0 or .)
• int nDelay: Delay between processing calls in Solver Mode CDLXSover::c_nModeProgress
• int nSolverMode: Solver Mode (Simple Sudoku Solving (c_nModeSolve) or show processing (c_nModeProgress)

The Sudoku grid (second parameter) is passed as a std::wstring. This string is then converted in a vector of std::pair named m_vctrSudoku in the function CDLXSolver::ConvertStringToVector()

This vector m_vctrSudoku is used to:

• Store initial Sudoku data
• Initialize the working vector m_vctrSolution. This vector is used by the Solver to store candidates during the solving process.
• Store Sudoku solution at the end of the processing
• Differentiate givens and candidatesin in board rendering. The board drawing function uses the boolen data to draw either in black or blue according to the Sudoku cell types (givens or candidates)

The function CDLXSolver::StartSolver() simply starts the solver in a thread:

    // Start Thread to Solve Sudoku

    m_thread = std::thread(&CDLXSolver::Solve, this);
	

At that time, the actual solving process starts:

• The function CDLXSolver::Solve() first initializes the working vector named m_vctrSolution and checks if the grid is solvable. If not, it exists and ends the solving process...
• The workhorse function CDLXSolver::Search is then called. During the processing, the function will be called recursively up to the end of the solving process.
• The function CDLXSolver::GetDLXSolution() is then called to convert the working vector m_vctrSolution to the vector m_vctrSudoku used to display the board graphically.

Visually, the recursion process can be illustrated by using the macro DBG_IND_LOG with the parameters DBG_INCR and DBG_DECR at the entry and the exit points of the function CDLXSolver::Search. Complete explanations about this namespace is available in the C++ Section.

Note that non-valid Sudoku grids can generate more than one solution. These grids are not useable for human resolution but are stored for further display (if requested by the user) in the vector m_vctrSolutions. Note the s at the end of the vector name as it is used to store a potential array of strings (declared as std::vector m_vctrSolutions in the CDLXSolver include file.

Download Link