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.
Here are the main features of
- 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
is implemented as a
-derived class. Because of all the files that are associated with the
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:
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,
- 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)
or (.sdk format)
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
XSudokuWnd into your app, you first need to add
CXSudokuWnd member variable to your dialog (or view) header file, and include XSudokuWnd.h:
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
CWnd *pWnd = GetDlgItem(IDC_STATIC_RECT);
CSize size = m_SudokuWnd.GetWindowSize();
rect.right = rect.left + size.cx;
rect.bottom = rect.top + size.cy;
and then create
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
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.
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:
Here are the functions available with
|Copy window bitmap to clipboard|
|Get 3x3 gridline color|
|Get cell background color|
|Get current cell border color|
|Get color for given values|
|Get given values|
|Get highlight number|
|Get highlight color|
|Get hint values|
|Get label color|
|Get pencil marks color|
|Get show state of pencil marks|
|Get show state of solution|
|Get solution color|
|Get solution values|
|Display Sudoku entry dialog|
|Get enable state of undo facility|
|Get user entry values|
|Get user entry color|
|Get window background color|
|Get minimum size of XSudokuWnd window|
|Returns TRUE if Sudoku is valid (exactly 1 solution)|
|Load Sudoku from clipboard|
|Load Sudoku from file|
|Load Sudoku from string|
|Print window bitmap|
|Set 3x3 gridline color|
|Set cell background color|
|Set current cell border color|
|Set color for given values|
|Set highlight number|
|Set highlight color|
|Set label color|
|Set hwnd for message callbacks|
|Set pencil marks color|
|Set show state of pencil marks|
|Set show state of solution values|
|Set solution color|
|Set enable state of undo facility|
|Set user entry color|
|Set window background color|
|Show color prefs dialog|
Version 1.2 - 2006 January 17
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.