15,998,142 members
Articles / Desktop Programming / MFC
Article

# XSudokuWnd - a control that implements the Sudoku puzzle

Rate me:
19 Mar 2007CPOL9 min read 212.3K   1.7K   92   56
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.

## 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:

1. 81-character text string - for example,
`708000300000201000500000000040000026300080000000100090090600004000070500000000000. `
2. 9x9 grid - for example, the puzzle in (1) above could also be entered as
```708000300
000201000
500000000
040000026
300080000
000100090
090600004
000070500
000000000```

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;
```

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

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.

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

## 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.

Written By
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.

 First PrevNext
 xSudokuwnd 654321ROD4-Feb-12 21:56 654321ROD 4-Feb-12 21:56
 Porting to VS 2008 654321ROD27-Aug-11 19:41 654321ROD 27-Aug-11 19:41
 Does enyone have ported this to VS2005 or later? sisira23-Aug-10 15:14 sisira 23-Aug-10 15:14
 Re: Does enyone have ported this to VS2005 or later? Hans Dietrich23-Aug-10 16:10 Hans Dietrich 23-Aug-10 16:10
 Re: Does enyone have ported this to VS2005 or later? sisira23-Aug-10 20:36 sisira 23-Aug-10 20:36
 Re: Does enyone have ported this to VS2005 or later? 654321ROD4-Feb-12 21:41 654321ROD 4-Feb-12 21:41
 Re: Does enyone have ported this to VS2005 or later? Whats in a name1-Apr-13 20:30 Whats in a name 1-Apr-13 20:30
 User should be alowed to remove individual hints Chip0226509-Dec-07 4:41 Chip022650 9-Dec-07 4:41
 Re: User should be alowed to remove individual hints Graham Shanks16-Sep-08 10:56 Graham Shanks 16-Sep-08 10:56
 Also please include code for generating puzzle..! ana_v1234-Sep-07 19:14 ana_v123 4-Sep-07 19:14
 Excellent! Mircea Puiu2-Jan-07 21:16 Mircea Puiu 2-Jan-07 21:16
 small error fool6-Sep-06 1:31 fool 6-Sep-06 1:31
 Re: small error Graham Shanks31-Jan-09 6:33 Graham Shanks 31-Jan-09 6:33
 small error fool6-Sep-06 1:31 fool 6-Sep-06 1:31
 Fantastic Article and Solution - Question [modified] Randy Friend8-Jul-06 9:57 Randy Friend 8-Jul-06 9:57
 Sudoku input format Nigel Greenwood13-May-06 5:09 Nigel Greenwood 13-May-06 5:09
 XSudoku lister plugin for Total Commander [modified] tbeu10-May-06 9:31 tbeu 10-May-06 9:31
 Large Fonts Jerry Jeremiah5-May-06 12:55 Jerry Jeremiah 5-May-06 12:55
 Great Solution 69 Bay27-Feb-06 11:29 69 Bay 27-Feb-06 11:29
 Re: Great Solution Graham Shanks19-Mar-06 10:59 Graham Shanks 19-Mar-06 10:59
 Re: Great Solution 69 Bay20-Mar-06 0:12 69 Bay 20-Mar-06 0:12
 Re: Great Solution Hans Dietrich24-Apr-06 6:08 Hans Dietrich 24-Apr-06 6:08
 Re: Great Solution Graham Shanks26-Apr-06 13:23 Graham Shanks 26-Apr-06 13:23
 Re: Great Solution OLEDB_Novice29-Jun-06 0:37 OLEDB_Novice 29-Jun-06 0:37
 Last Visit: 31-Dec-99 18:00     Last Update: 15-Sep-24 19:41 Refresh 123 Next ᐅ