Click here to Skip to main content
Click here to Skip to main content

XSudokuWnd - a control that implements the Sudoku puzzle

, 19 Mar 2007 CPOL
Rate this:
Please Sign up or sign in to vote.
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:

screenshot

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:

screenshot

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

screenshot

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

screenshot

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:

screenshot

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:

screenshot

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:

    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:

    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:

    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:

screenshot

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

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)

Share

About the Author

Hans Dietrich
Software Developer (Senior) Hans Dietrich Software
United States 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.






Comments and Discussions

 
QuestionxSudokuwnd Pinmember654321ROD4-Feb-12 22:56 
QuestionPorting to VS 2008 Pinmember654321ROD27-Aug-11 20:41 
QuestionDoes enyone have ported this to VS2005 or later? Pinmembersisira23-Aug-10 16:14 
AnswerRe: Does enyone have ported this to VS2005 or later? PinmentorHans Dietrich23-Aug-10 17:10 
GeneralRe: Does enyone have ported this to VS2005 or later? Pinmembersisira23-Aug-10 21:36 
GeneralRe: Does enyone have ported this to VS2005 or later? Pinmember654321ROD4-Feb-12 22:41 
GeneralRe: Does enyone have ported this to VS2005 or later? PinmemberWhats in a name1-Apr-13 21:30 
GeneralUser should be alowed to remove individual hints PinmemberChip0226509-Dec-07 5:41 
GeneralRe: User should be alowed to remove individual hints PinmemberGraham Shanks16-Sep-08 11:56 
GeneralAlso please include code for generating puzzle..! Pinmemberana_v1234-Sep-07 20:14 
GeneralExcellent! PinmemberMircea Puiu2-Jan-07 22:16 
GeneralVery quick, beats our solution. PinmemberADarkGerm21-Dec-06 0:42 
Generalsmall error Pinmemberfool6-Sep-06 2:31 
GeneralRe: small error PinmemberGraham Shanks31-Jan-09 7:33 
Generalsmall error Pinmemberfool6-Sep-06 2:31 
GeneralFantastic Article and Solution - Question [modified] PinmemberRandy Friend8-Jul-06 10:57 
GeneralSudoku input format PinmemberNigel Greenwood13-May-06 6:09 
GeneralXSudoku lister plugin for Total Commander [modified] Pinmembertbeu10-May-06 10:31 
GeneralLarge Fonts PinmemberJerry Jeremiah5-May-06 13:55 
GeneralGreat Solution Pinmember69 Bay27-Feb-06 12:29 
GeneralRe: Great Solution PinmemberGraham Shanks19-Mar-06 11:59 
GeneralRe: Great Solution Pinmember69 Bay20-Mar-06 1:12 
GeneralRe: Great Solution PinmemberHans Dietrich24-Apr-06 7:08 
GeneralRe: Great Solution PinmemberGraham Shanks26-Apr-06 14:23 
GeneralRe: Great Solution PinmemberOLEDB_Novice29-Jun-06 1:37 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150123.1 | Last Updated 19 Mar 2007
Article Copyright 2006 by Hans Dietrich
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid