XSudokuWnd - a control that implements the Sudoku puzzle

Hans Dietrich

Rate me:

4.96/5 (75 votes)

19 Mar 2007CPOL9 min read

207.7K

1.7K

XSudokuWnd is an MFC control that implements a solver for the popular Sudoku puzzle, based on D.E. Knuth's Dancing Links algorithm. Example projects show how to use XSudokuWnd in dialog and SDI applications.

Download demo project - 182 Kb

Introduction

There seems little need to introduce Sudoku, since it is now one of the most popular puzzles in the world. Typically, people find Sudoku puzzles in newspapers such as the LA Times or online - a google search for Sudoku produces millions of hits. Sudoku rules are very simple: in each cell of a 9x9 Sudoku board, a digit (1 thru 9) may be placed. Each digit may appear only once in each row and each column. There is a further restriction that the board is divided into 9 3x3 subgrids called regions, and each digit may appear only once in each region. Finally, every valid Sudoku puzzle (or proper puzzle) has a single unique solution. More information on Sudoku can be found on Wikipedia.

I was surprised to find that Sudoku has even infiltrated CodeProject - a search brings up five articles. And there is also a Sudoku Programming Forum, where people can discuss techniques for solving Sudoku puzzles by computer. What was most interesting to me was how elaborate the manual solving techniques have become. The more famous of the manual techniques have been given suggestive names such as Naked Single, X-Wing, and Swordfish. To solve a "hard" Sudoku manually, it may be necessary to utilize several techniques in turn. In general, Sudoku solver programs (such as Sudo Cue) try to emulate the manual solving techniques.

Since most of the manual solving techniques seem to be very intricate and somewhat ad-hoc, I never really considered trying to program a Sudoku solver until I discovered that D.E. Knuth has published an algorithm he calls Dancing Links that may be applied directly to solving Sudoku puzzles. In addition to being very fast, Knuth's algorithm also has the benefit that it is guaranteed to find the solution if the puzzle is valid.

XSudokuWnd Features

Here are the main features of XSudokuWnd:

Implemented as an MFC extension DLL
Complete API allows access to all features, colors, cell values, etc.
Extremely fast, even hardest Sudoku solved in less than a second
Able to import Sudoku puzzles from files, clipboard, or via an entry dialog
Understands most file formats used by other Sudoku software
Optional message callback allows parent window to receive status messages
Supports unlimited number of undo/redo actions
User can customize all colors
User can show/hide pencil marks
User can show/hide hint for a single cell, or show solution for entire puzzle
Built-in facility to allow user to check entered values
User can highlight all cells containing a particular value, hint, or pencil mark
User can print bitmap of puzzle
User can copy bitmap of puzzle to clipboard

XSudokuWnd Implementation

XSudokuWnd is implemented as a CWnd-derived class. Because of all the files that are associated with the XSudokuWnd implementation, I decided to package it as an MFC extension DLL. The download contains the XSudokuWnd DLL as well as a sample dialog app and a sample SDI app.

Here is what the dialog app looks like:

Some Terminology

When a Sudoku puzzle is loaded, the given values are displayed in red, as in the above screenshot. Given values are used by XSudokuWnd to solve the puzzle values for other cells; the given values cannot be changed by the user.

Pencil marks are displayed as small numbers within each cell. A pencil mark refers to one of the 9 possible values (sometimes called candidate values) of a cell, that meet all the rules for solving a Sudoku. The user may enter one of the indicated pencil marks by selecting one of the cells and hitting a number key, or by selecting a value from the right-click menu:

Another user assistance feature is to highlight all the possible cells for a candidate value. Here all the cells for '2' are highlighted:

The right-click menu also allows the user to get a hint for the selected cell, or to show the entire solution, as below:

XSudokuWnd Input Formats

There are many sources of sample Sudoku puzzles on the web, including syndicated newspaper puzzles, and web sites that have large puzzle archives, with puzzles graded according to difficulty. The sample dialog app is able to read puzzles from a file, from the clipboard, or directly from puzzle entry dialog:

Nearly all online Sudoku puzzles are available in one of two basic formats:

81-character text string - for example,

708000300000201000500000000040000026300080000000100090090600004000070500000000000.

9x9 grid - for example, the puzzle in (1) above could also be entered as

or with extra formatting as

7.8 ... 3..
... 2.1 ...
5.. ... ...

.4. ... .26
3.. .8. ...
... 1.. .9.

.9. 6.. ..4
... .7. 5..
... ... ...

or (.ss format)

*-----------*
|7.8|...|3..|
|...|2.1|...|
|5..|...|...|
|---+---+---|
|.4.|...|.26|
|3..|.8.|...|
|...|1..|.9.|
|---+---+---|
|.9.|6..|..4|
|...|.7.|5..|
|...|...|...|
*-----------*

or (.sdk format)

[Puzzle]
7.8...3..
...2.1...
5........
.4.....26
3...8....
...1...9.
.9.6....4
....7.5..
.........

Note that a period or zero may be used to indicate an unknown value, which the user must supply to solve the puzzle.

XSudokuWnd can read any of the above formats - from file, from clipboard, or by using puzzle entry dialog:

Any character other than a digit or a period is ignored, and a total of 81 digits (including periods) is necessary for a valid puzzle.

How To Use XSudokuWnd

To integrate XSudokuWnd into your app, you first need to add CXSudokuWnd member variable to your dialog (or view) header file, and include XSudokuWnd.h:

C++

CXSudokuWnd  m_SudokuWnd;

You will need to add the XSudokuWndDll directory to your project's list of "Additional include directories".

Next, use resource editor to add static placeholder control to your dialog, in the position where you want XSudokuWnd window:

C++

CWnd *pWnd = GetDlgItem(IDC_STATIC_RECT);
ASSERT(pWnd);

CRect rect;
pWnd->GetWindowRect(&rect);
ScreenToClient(&rect);

CSize size = m_SudokuWnd.GetWindowSize();

rect.right  = rect.left + size.cx;
rect.bottom = rect.top + size.cy;

pWnd->ShowWindow(SW_HIDE);

and then create XSudokuWnd window:

C++

m_SudokuWnd.Create(NULL, NULL, WS_CLIPSIBLINGS | WS_CHILD | WS_VISIBLE | WS_BORDER,
    rect, this, 9999);

See XSudokuDlg.cpp for examples of how to enter a sudoku puzzle into XSudokuWnd.

Next, edit the "Additional library path" in the project settings to include the XSudokuWndD.lib or XSudokuWndR.lib directory path.

Finally, make sure the XSudokuWndD.dll or XSudokuWndR.dll is in the same directory as your app's exe.

XSudokuWnd User Interface

Navigation

The user may navigate by using the arrow keys, Page Up and Page Down keys, and Home and End keys.

Entering a Value

To enter a value in a cell, select that cell, and then press a digit key (1 - 9). To remove a user entry in a cell, you can select Remove User Entry from the right-click menu, or simply press the 0 (zero) key when the cell is selected.

You may also get a hint for a cell; this will insert the value from the Sudoku solution into the cell. To get a hint, you can select Show Hint from the right-click menu, or press F2.

When you enter (or remove) values and hints, the action is recorded in an undo list. You can use the standard Ctrl+Z and Ctrl+Y to undo/redo actions; or you can select Undo or Redo from the right-click menu.

Right-Click (Context) Menu

The right-click menu is shown above. It can be displayed by using a right click, left double click, enter key, and Shift+F10.

Undo - undo last user entry or hint action; Ctrl+Z may also be used.
Redo - repeat last user entry or hint action; Ctrl+Y may also be used.
"Set to" items - set the selected cell to the value
Show Hint - show/hide hint for the selected cell; F2 may also be used.
Remove All Hints - remove all hints
Remove User Entry - remove user entry for the selected cell
Remove All User Entries - remove all user entries
Check User Entries - check all user values
Show Solution - show/hide solution for all cells; F3 may also be used.
Show Pencil Marks - show/hide pencil marks; F4 may also be used.
Reset - reset puzzle to initial state
Print Window - print window bitmap; Ctrl+P may also be used.
Copy Window to Clipboard - copy window bitmap to clipboard; Ctrl+C may also be used.
Highlight N - highlight all cells with the same user value, hint, or candidate value as N; the keyboard shortcuts Ctrl+1, Ctrl+2, etc., may also be used. Selecting the same menu entry (or pressing the same keyboard shortcut) has the effect of removing the highlighting. The keyboard shortcut Ctrl+0 can also be used to remove any highlighting.

Displaying Color Preferences Dialog

You can change any of the XSudokuWnd colors with the color preferences dialog. which is displayed when you click on Alt+Enter:

XSudokuWnd Functions

Here are the functions available with CXSudokuWnd:

`CaptureBitmap()`	Copy window bitmap to clipboard
`Get3x3Gridline()`	Get 3x3 gridline color
`GetCellBackground()`	Get cell background color
`GetCurCellBorder()`	Get current cell border color
`GetGivens()`	Get color for given values
`GetGivenValues()`	Get given values
`GetHighlightNumber()`	Get highlight number
`GetHighlightNumberColor()`	Get highlight color
`GetHints()`	Get hint values
`GetLabels()`	Get label color
`GetPencilMarks()`	Get pencil marks color
`GetShowPencilMarks()`	Get show state of pencil marks
`GetShowSolution()`	Get show state of solution
`GetSolution()`	Get solution color
`GetSolutionValues()`	Get solution values
`GetSudoku()`	Display Sudoku entry dialog
`GetUndoEnable()`	Get enable state of undo facility
`GetUserEntries()`	Get user entry values
`GetUserEntry()`	Get user entry color
`GetWindowBackground()`	Get window background color
`GetWindowSize()`	Get minimum size of XSudokuWnd window
`IsValid()`	Returns TRUE if Sudoku is valid (exactly 1 solution)
`LoadFromClipboard()`	Load Sudoku from clipboard
`LoadFromFile()`	Load Sudoku from file
`LoadFromString()`	Load Sudoku from string
`PrintBitmap()`	Print window bitmap
`Set3x3Gridline()`	Set 3x3 gridline color
`SetCellBackground()`	Set cell background color
`SetCurCellBorder()`	Set current cell border color
`SetGivens()`	Set color for given values
`SetHighlightNumber()`	Set highlight number
`SetHighlightNumberColor()`	Set highlight color
`SetLabels()`	Set label color
`SetMessageHwnd()`	Set hwnd for message callbacks
`SetPencilMarks()`	Set pencil marks color
`SetShowPencilMarks()`	Set show state of pencil marks
`SetShowSolution()`	Set show state of solution values
`SetSolution()`	Set solution color
`SetUndoEnable()`	Set enable state of undo facility
`SetUserEntry()`	Set user entry color
`SetWindowBackground()`	Set window background color
`ShowColorPrefsDlg()`	Show color prefs dialog

Acknowledgments

The implementation of XSudokuWnd is based on D.E.Knuth's Dancing Links algorithm, using C code written by Arthur O'Dwyer.
DllInstanceSwitcher class for switching to MFC Extension DLL resources by Peredelsky Alexey.
Print a bitmap full page by Niek Albers.
How to print CFormView by Tao Hu.
Screen Capture to the Clipboard by Joseph M. Newcomer.
XTrace is based on an article by Paul Mclachlan, "Getting around the need for a vararg #define just to automatically use __FILE__ and __LINE__ in a TRACE macro".

Revision History

Version 1.2 - 2006 January 17

Initial public release

Usage

This software is released into the public domain. You are free to use it in any way you like, except that you may not sell this source code. If you modify it or extend it, please consider posting new code here for everyone to share. This software is provided "as is" with no expressed or implied warranty. I accept no liability for any damage or loss of business that this software may cause.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Hans Dietrich

Software Developer (Senior) Hans Dietrich Software

United States

I attended St. Michael's College of the University of Toronto, with the intention of becoming a priest. A friend in the University's Computer Science Department got me interested in programming, and I have been hooked ever since.

Recently, I have moved to Los Angeles where I am doing consulting and development work.

For consulting and custom software development, please see www.hdsoft.org.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.