|
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
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:
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:
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
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.
| You must Sign In to use this message board. |
|
| | Msgs 1 to 25 of 47 (Total in Forum: 47) (Refresh) | FirstPrevNext |
|
 |
|
|
Very nice. Solving these manualy includes the process of elimination - the ability to eliminate individual candidates that are actualy not possible even if they are currently valid. For example, if a 9x9 box has candidates of 2's in only one row (or column), then the solution must have a 2 in that row (or column) of that box. So any 2's in the same row (or column) outside that box can be ruled out. The user should be allowed to remove it/them.
lforster@wowway.com
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nice job very fast proof.
The best i have seen on the web.
Best Regards,
Mark Edgar
Software Engineer
interconnect
www.onedollarsudoku.com
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
There's a small error in the gui:
When I use the shortcuts for highlighting cells and press Ctrl+ the is printed into the active cell.
None the less a great article!
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
There's a small error in the gui:
When I use the shortcuts for highlighting cells and press Ctrl+ eg. the is printed into the active cell.
None the less a great article!
|
| Sign In·View Thread·PermaLink | 3.00/5 (1 vote) |
|
|
|
|
|
|
Thank you for the great article. I am very new to programming and have found Code Project a great resource. With your solution, have you though of adding the ability to define the 3 x 3 grid to allow for Jigsaw Sudoku puzzles like the ones at www.sudoku.org.uk/jigsaw.asp.
There is a HTA application at http://groups.yahoo.com/group/sudoku-tutor that uses vbscript to do this, but I don't know enough to get it working in C++ (or .net) as yet.
thanks again for the article and information. Rated 5 all the way.
-- modified at 15:57 Saturday 8th July, 2006
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Have you thought of adding an abbreviated input format? For example, the example you give is:
7.8 ... 3..
... 2.1 ...
5.. ... ...
.4. ... .26
3.. .8. ...
... 1.. .9.
.9. 6.. ..4
... .7. 5..
... ... ...
This could be input as follows:
708//300
/201
500
40//26
300/80
/100/90
90/600/4
/70/500
//
Others may be able to devise an even more economical format.
Nigel
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
|
|
|
Great Solution - it makes solving Sudoku too easy.
I have found when solving a puzzle that it can you can see that certain numbers cannot be in certain locations. I have extended the application slightly by allowing the user to rub out numbers from the grid, or add them back in again (Right Click on box, and the select Rub Out, or Pencil In as required). Would you be interested in this - if so, how do you go about posting it?
Thanks for the app.
Mike
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
Hi
I havnt been able to work out how to post an attachment, so I have included XSudokuWnd.cpp within this reply - sorry if this isnt the right way to go about this!
The changes that I have made are :
1 Added m_nUnPencil[9][9] to XSudokuWnd.h
2 Defined new popuup menu items ID_POPUP_UNPENCIL_1 - 9 & ID_POPUP_PENCIL_1 - 9, and added in the relevant ON_COMMAND_RANGE to the Message Map
3 Added additional functions OnPopupUnPencil(), OnPopupPencil(), GetUnPenciledCandidates()
4 Altered ShowPopup() function to display Rub Out [x], or Pencil In [X] options.
Again I apologise if I havnt posted this properly - this is my first time!
Mike
// XSudokuWnd.cpp Version 1.2
//
// Author: Hans Dietrich
// hdietrich@gmail.com
//
// Description:
// XSudokuWnd implements CXSudokuWnd, a class that displays a Sudoku puzzle.
//
// History
// Version 1.2 - 2006 January 17
// - Initial public release
//
// Public APIs:
// NAME DESCRIPTION
// --------------------- -----------------------------------------
// 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
//
// License:
// 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.
//
// 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.
//
///////////////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "resource.h"
#include "XSudokuWnd.h"
#include "FontSize.h"
#include "dance.h"
#include "memdc.h"
#include "clipboard.h"
#include "GDIUtil.h"
#include "DllInstanceSwitcher.h"
#include "SudokuEntryDlg.h"
#include "ColorPrefDlg.h"
#include "About.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
IMPLEMENT_DYNAMIC(CXSudokuWnd,CWnd)
UINT WM_XSUDOKU = ::RegisterWindowMessage(_T("WM_XSUDOKU"));
static int g_nGridLineOffset[9] = { 0, 0, 0, 1, 1, 1, 2, 2, 2 };
static TCHAR * g_szDigits = _T("0123456789");
#define SetBit(x,y) ( =(1<<(y)))
#define ClearBit(x,y) (x&=~(1<<(y)))
#define TestBit(x,y) (x&(1<<(y)))
///////////////////////////////////////////////////////////////////////////////
//
// undo / redo
//
#define UNDO_ARRAY_GROW_BY_SIZE 20
#pragma pack(push,1)
struct UNDO_BLOCK
{
UNDO_BLOCK()
{
TRACE(_T("in UNDO_BLOCK()\n"));
action_code = 0;
action_value = 0;
row = col = 0;
};
BYTE action_code;
#define ACTION_CODE_USER_ENTRY 1 // action_value = 0 to remove user entry
#define ACTION_CODE_USER_ENTRY_REMOVE_ALL 2
#define ACTION_CODE_HINT 3 // action_value: 0 = hide hint; else 1-9
#define ACTION_CODE_HINT_REMOVE_ALL 4
BYTE action_value;
BYTE row, col; // current row & column
BYTE hints[9][9];
BYTE user_entries[9][9];
};
#pragma pack(pop)
///////////////////////////////////////////////////////////////////////////////
// Popup menu items
#define ID_POPUP_HIGHLIGHT_0 50000
#define ID_POPUP_HIGHLIGHT_1 50001
#define ID_POPUP_HIGHLIGHT_2 50002
#define ID_POPUP_HIGHLIGHT_3 50003
#define ID_POPUP_HIGHLIGHT_4 50004
#define ID_POPUP_HIGHLIGHT_5 50005
#define ID_POPUP_HIGHLIGHT_6 50006
#define ID_POPUP_HIGHLIGHT_7 50007
#define ID_POPUP_HIGHLIGHT_8 50008
#define ID_POPUP_HIGHLIGHT_9 50009
#define ID_POPUP_SET_1 50011
#define ID_POPUP_SET_2 50012
#define ID_POPUP_SET_3 50013
#define ID_POPUP_SET_4 50014
#define ID_POPUP_SET_5 50015
#define ID_POPUP_SET_6 50016
#define ID_POPUP_SET_7 50017
#define ID_POPUP_SET_8 50018
#define ID_POPUP_SET_9 50019
#define ID_POPUP_UNPENCIL_1 50021
#define ID_POPUP_UNPENCIL_2 50022
#define ID_POPUP_UNPENCIL_3 50023
#define ID_POPUP_UNPENCIL_4 50024
#define ID_POPUP_UNPENCIL_5 50025
#define ID_POPUP_UNPENCIL_6 50026
#define ID_POPUP_UNPENCIL_7 50027
#define ID_POPUP_UNPENCIL_8 50028
#define ID_POPUP_UNPENCIL_9 50029
#define ID_POPUP_PENCIL_1 50051
#define ID_POPUP_PENCIL_2 50052
#define ID_POPUP_PENCIL_3 50053
#define ID_POPUP_PENCIL_4 50054
#define ID_POPUP_PENCIL_5 50055
#define ID_POPUP_PENCIL_6 50056
#define ID_POPUP_PENCIL_7 50057
#define ID_POPUP_PENCIL_8 50058
#define ID_POPUP_PENCIL_9 50059
#define ID_POPUP_SHOW_HINT 50030
#define ID_POPUP_REMOVE_ALL_HINTS 50031
#define ID_POPUP_SHOW_SOLUTION 50032
#define ID_POPUP_SHOW_PENCIL_MARKS 50033
#define ID_POPUP_RESET 50034
#define ID_POPUP_REMOVE_USER_ENTRY 50035
#define ID_POPUP_REMOVE_ALL_USER_ENTRIES 50036
#define ID_POPUP_CHECK_USER_ENTRIES 50037
#define ID_POPUP_PRINT 50038
#define ID_POPUP_COPY 50039
#define ID_POPUP_UNDO 50040
#define ID_POPUP_REDO 50041
///////////////////////////////////////////////////////////////////////////////
// CXSudokuWnd Message Map
BEGIN_MESSAGE_MAP(CXSudokuWnd, CWnd)
//{{AFX_MSG_MAP(CXSudokuWnd)
ON_WM_ERASEBKGND()
ON_WM_PAINT()
ON_WM_LBUTTONDOWN()
ON_WM_RBUTTONUP()
ON_WM_LBUTTONDBLCLK()
ON_WM_GETDLGCODE()
ON_WM_RBUTTONDOWN()
ON_COMMAND(ID_RIGHT_CLICK, OnRightClick)
ON_COMMAND(ID_COLOR_PREFS, OnColorPrefs)
ON_COMMAND(ID_LOAD_SAMPLE, OnLoadSample)
ON_COMMAND(ID_SHOW_HINT, OnShowHint)
ON_COMMAND(ID_SHOW_SOLUTION, OnShowSolution)
ON_COMMAND(ID_SHOW_PENCIL_MARKS, OnShowPencilMarks)
ON_COMMAND(ID_EDIT_UNDO, OnEditUndo)
ON_COMMAND(ID_EDIT_REDO, OnEditRedo)
ON_COMMAND(ID_EDIT_COPY, OnCopyWindow)
ON_COMMAND(ID_FILE_PRINT, OnPrintWindow)
ON_COMMAND(ID_APP_ABOUT, OnAppAbout)
//}}AFX_MSG_MAP
ON_COMMAND(ID_POPUP_UNDO, OnEditUndo)
ON_COMMAND(ID_POPUP_REDO, OnEditRedo)
ON_COMMAND(ID_POPUP_SHOW_HINT, OnPopupShowHint)
ON_COMMAND(ID_POPUP_REMOVE_ALL_HINTS, OnRemoveAllHints)
ON_COMMAND(ID_POPUP_SHOW_SOLUTION, OnShowSolution)
ON_COMMAND(ID_POPUP_SHOW_PENCIL_MARKS, OnShowPencilMarks)
ON_COMMAND(ID_POPUP_RESET, OnReset)
ON_COMMAND(ID_POPUP_PRINT, OnPrintWindow)
ON_COMMAND(ID_POPUP_COPY, OnCopyWindow)
ON_COMMAND(ID_POPUP_REMOVE_USER_ENTRY, OnRemoveUserEntry)
ON_COMMAND(ID_POPUP_REMOVE_ALL_USER_ENTRIES, OnRemoveAllUserEntries)
ON_COMMAND(ID_POPUP_CHECK_USER_ENTRIES, OnCheckUserEntries)
ON_COMMAND_RANGE(ID_POPUP_SET_1, ID_POPUP_SET_9, OnPopupSet)
ON_COMMAND_RANGE(ID_POPUP_UNPENCIL_1, ID_POPUP_UNPENCIL_9, OnPopupUnPencil)
ON_COMMAND_RANGE(ID_POPUP_PENCIL_1, ID_POPUP_PENCIL_9, OnPopupPencil)
ON_COMMAND_RANGE(ID_POPUP_HIGHLIGHT_1, ID_POPUP_HIGHLIGHT_9, OnPopupHighlight)
ON_COMMAND_RANGE(ID_HIGHLIGHT_0, ID_HIGHLIGHT_9, OnHighlight)
END_MESSAGE_MAP()
///////////////////////////////////////////////////////////////////////////////
//
// CXSudokuWnd()
//
// Purpose: Construct CXSudokuWnd object
//
// Parameters: None
//
// Returns: None
//
// Notes: Construction is a two-step process. First, construct the
// CXSudokuWnd object. Second, call CXSudokuWnd::Create to create
// the CXSudokuWnd window.
//
CXSudokuWnd::CXSudokuWnd()
{
m_bIsValid = FALSE;
m_hWndMessage = NULL;
m_hAccel = NULL;
m_bPencilMarks = FALSE;
m_bHaveGivens = FALSE;
m_bShowSolution = FALSE;
m_rgbWindowBackground = RGB(220,20,60);
m_rgbCellBackground = RGB(192,192,192);
m_rgbLabels = RGB(255,255,255);
m_rgbGivens = RGB(220,20,60);
m_rgbSolution = RGB(0, 0, 255);
m_rgbUserEntry = RGB(0, 0, 0);
m_rgbPencilMarks = RGB(0, 0, 128);
m_rgbHighlightNumber = RGB(135, 206, 250);
m_rgbCurCellBorder = RGB(255, 255, 0);
m_rgb3x3Gridline = RGB(0,0,0);
m_strLabelFont = _T("Verdana");
m_nXOffset = 20;
m_nYOffset = 20;
m_nCellWidth = 45;
m_nCellHeight = 44;
m_nHighlightNumber = 0;
m_nCurRow = m_nCurCol = -1;
m_pointPopup = CPoint(-1,-1);
m_strFile = _T("");
// initialize undo facility
m_bEnableUndo = TRUE;
m_nUndoIndex = 0;
m_nUndoLastEntry = 0;
m_nUndoSize = UNDO_ARRAY_GROW_BY_SIZE;
m_Undo.SetSize(m_nUndoSize);
for (int k = 0; k < m_nUndoSize; k++)
{
UNDO_BLOCK * pUB = new UNDO_BLOCK;
ASSERT(pUB);
m_Undo[k] = pUB;
}
// initialize all arrays
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
m_nGivens[i][j] = 0;
m_nSolution[i][j] = 0;
m_nHints[i][j] = 0;
m_nUserEntries[i][j] = 0;
}
}
}
///////////////////////////////////////////////////////////////////////////////
//
// ~CXSudokuWnd()
//
// Purpose: Destroy CXSudokuWnd object.
//
// Parameters: None
//
// Returns: None
//
CXSudokuWnd::~CXSudokuWnd()
{
if (m_fontLabels.GetSafeHandle())
m_fontLabels.DeleteObject();
if (m_fontValues.GetSafeHandle())
m_fontValues.DeleteObject();
if (m_fontPencilMarks.GetSafeHandle())
m_fontPencilMarks.DeleteObject();
if (m_fontPrint.GetSafeHandle())
m_fontPrint.DeleteObject();
for (int j = 0; j < m_nUndoSize; j++)
{
UNDO_BLOCK * pUB = (UNDO_BLOCK *) m_Undo[j];
ASSERT(pUB);
if (pUB)
{
#ifdef _DEBUG
CString str = ActionCodeToString(pUB->action_code);
if (!str.IsEmpty())
{
TRACE(_T("deleting undo action '%s'\n"), str);
}
#endif
delete pUB;
}
}
}
///////////////////////////////////////////////////////////////////////////////
//
// OnGetDlgCode()
//
// Purpose: The WM_GETDLGCODE message is sent to the window procedure
// associated with a control. By default, the system handles all
// keyboard input to the control; the system interprets certain
// types of keyboard input as dialog box navigation keys. To
// override this default behavior, the control can respond to the
// WM_GETDLGCODE message to indicate the types of input it wants
// to process itself.
//
// Parameters: None
//
// Returns: UINT - always DLGC_WANTALLKEYS
//
UINT CXSudokuWnd::OnGetDlgCode()
{
return DLGC_WANTALLKEYS;
}
///////////////////////////////////////////////////////////////////////////////
//
// OnEraseBkgnd()
//
// Purpose: The framework calls this member function when the CWnd object
// background needs erasing.
//
// Parameters: pDC - pointer to device context object
//
// Returns: BOOL - TRUE = background was erased; otherwise FALSE
//
BOOL CXSudokuWnd::OnEraseBkgnd(CDC* pDC)
{
EraseBkgnd(pDC);
return CWnd::OnEraseBkgnd(pDC);
}
///////////////////////////////////////////////////////////////////////////////
//
// EraseBkgnd()
//
// Purpose: Erase background by filling client rect with control's window
// background color.
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::EraseBkgnd(CDC* pDC)
{
CRect rect;
GetClientRect(&rect);
pDC->FillSolidRect(rect, m_rgbWindowBackground);
}
///////////////////////////////////////////////////////////////////////////////
//
// OnPaint()
//
// Purpose: The framework calls this member function when Windows or an
// application makes a request to repaint a portion of the
// control's window.
//
// Parameters: None
//
// Returns: None
//
// Notes: OnPaint() always first fills the entire client background with
// the control's background color, so there is never a need to call
// Invalidate() with TRUE.
//
void CXSudokuWnd::OnPaint()
{
CPaintDC dc(this); // device context for painting
CMemDC memDC(&dc);
EraseBkgnd(&memDC);
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
PaintCell(&memDC, i, j);
}
}
Paint3x3Gridlines(&memDC);
PaintLabels(&memDC);
if (m_bHaveGivens)
{
PaintValues(&memDC);
if (m_bPencilMarks)
PaintPencilMarks(&memDC);
}
PaintCurCell(&memDC);
DefWindowProc(WM_PAINT, (WPARAM)memDC->m_hDC, (LPARAM)0);
// Do not call CWnd::OnPaint() for painting messages
}
///////////////////////////////////////////////////////////////////////////////
//
// GetWindowSize()
//
// Purpose: Get size needed for XSudokuWnd client rect.
//
// Parameters: None
//
// Returns: CSize - size in pixels of client rect, including margins and
// grid lines.
//
CSize CXSudokuWnd::GetWindowSize()
{
CSize size(0, 0);
size.cx = 2 * m_nXOffset + 9 * (m_nCellWidth+1) + 2;
size.cy = 2 * m_nYOffset + 9 * (m_nCellHeight+1) + 2;
return size;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetCellBackgroundColor()
//
// Purpose: Get current background color of a cell
//
// Parameters: row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: COLORREF - current background color for cell; this will
// depend on whether the cell is highlighted.
//
COLORREF CXSudokuWnd::GetCellBackgroundColor(int row, int col)
{
COLORREF rgb = m_rgbCellBackground;
if (m_bHaveGivens && (m_nHighlightNumber != 0))
{
WORD wCandidates = GetCandidates(row, col) & GetUnPenciledCandidates(row, col);//get the possible candidates, less the rubbed out values
int nGiven = m_nGivens[row][col];
int nSolution = m_nSolution[row][col];
int nHint = m_nHints[row][col];
int nUserEntry = m_nUserEntries[row][col];
if (nGiven)
{
if (nGiven == m_nHighlightNumber)
rgb = m_rgbHighlightNumber;
}
else if (nHint)
{
if (nHint == m_nHighlightNumber)
rgb = m_rgbHighlightNumber;
}
else if (nUserEntry)
{
if (nUserEntry == m_nHighlightNumber)
rgb = m_rgbHighlightNumber;
}
else if (nSolution && m_bShowSolution)
{
if (nSolution == m_nHighlightNumber)
rgb = m_rgbHighlightNumber;
}
else if (TestBit(wCandidates, m_nHighlightNumber))
{
rgb = m_rgbHighlightNumber;
}
}
return rgb;
}
///////////////////////////////////////////////////////////////////////////////
//
// PaintCell()
//
// Purpose: Fill cell with correct background color
//
// Parameters: pDC - pointer to device context object
// row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: None
//
void CXSudokuWnd::PaintCell(CDC * pDC, int row, int col)
{
CRect rectCell = GetCellRect(row, col);
pDC->FillSolidRect(&rectCell, GetCellBackgroundColor(row, col));
}
///////////////////////////////////////////////////////////////////////////////
//
// Paint3x3Gridlines()
//
// Purpose: Draw 3x3 grid lines
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::Paint3x3Gridlines(CDC * pDC)
{
CPen pen(PS_SOLID, 1, m_rgb3x3Gridline);
CPen *pOldPen = pDC->SelectObject(&pen);
CRect rectWnd, rectLine;
GetClientRect(&rectWnd);
rectLine.top = rectWnd.top + m_nYOffset;
rectLine.bottom = rectLine.top + 9 * m_nCellHeight + 8 + 2;
// vertical lines
rectLine.left = rectWnd.left + m_nXOffset + 3 * m_nCellWidth + 2;
pDC->MoveTo(rectLine.left, rectLine.top);
pDC->LineTo(rectLine.left, rectLine.bottom);
pDC->MoveTo(rectLine.left+1, rectLine.top);
pDC->LineTo(rectLine.left+1, rectLine.bottom);
rectLine.left += 2 + 3 * m_nCellWidth + 2;
pDC->MoveTo(rectLine.left, rectLine.top);
pDC->LineTo(rectLine.left, rectLine.bottom);
pDC->MoveTo(rectLine.left+1, rectLine.top);
pDC->LineTo(rectLine.left+1, rectLine.bottom);
// horizontal lines
rectLine.left = rectWnd.left + m_nXOffset;
rectLine.right = rectLine.left + 9 * m_nCellWidth + 8 + 2;
rectLine.top += 3 * m_nCellHeight + 2;
pDC->MoveTo(rectLine.left, rectLine.top);
pDC->LineTo(rectLine.right, rectLine.top);
pDC->MoveTo(rectLine.left, rectLine.top+1);
pDC->LineTo(rectLine.right, rectLine.top+1);
rectLine.top += 3 * m_nCellHeight + 2 + 2;
pDC->MoveTo(rectLine.left, rectLine.top);
pDC->LineTo(rectLine.right, rectLine.top);
pDC->MoveTo(rectLine.left, rectLine.top+1);
pDC->LineTo(rectLine.right, rectLine.top+1);
pDC->SelectObject(pOldPen);
}
///////////////////////////////////////////////////////////////////////////////
//
// PaintLabels()
//
// Purpose: Draw row and column labels
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::PaintLabels(CDC * pDC)
{
CFont *pOldFont = pDC->SelectObject(&m_fontLabels);
pDC->SetBkColor(m_rgbWindowBackground);
pDC->SetTextColor(m_rgbLabels);
CRect rectWnd, rectLabel;
GetClientRect(&rectWnd);
rectLabel.top = rectWnd.top + m_nYOffset - m_nLabelHeight - 2;
rectLabel.bottom = rectLabel.top + m_nLabelHeight + 2;
rectLabel.left = rectWnd.left + m_nXOffset + m_nCellWidth/2 - 3;
rectLabel.right = rectLabel.left + m_nLabelHeight;
static TCHAR * szXLabel = _T("ABCDEFGHI");
int i = 0;
for (i = 0; i < 9; i++)
{
rectLabel.left += g_nGridLineOffset[i];
rectLabel.right = rectLabel.left + m_nLabelHeight;
pDC->ExtTextOut(rectLabel.left, rectLabel.top,
ETO_CLIPPED|ETO_OPAQUE,
&rectLabel,
&szXLabel[i], 1,
NULL);
rectLabel.left += m_nCellWidth;
}
rectLabel.top = rectWnd.top + m_nYOffset + m_nCellHeight/2 - 5;
rectLabel.bottom = rectLabel.top + m_nLabelHeight + 2;
rectLabel.left = rectWnd.left + m_nXOffset - m_nLabelHeight - 2;
rectLabel.right = rectLabel.left + m_nLabelHeight;
for (i = 0; i < 9; i++)
{
rectLabel.top += g_nGridLineOffset[i];
rectLabel.bottom = rectLabel.top + m_nLabelHeight + 1;
pDC->ExtTextOut(rectLabel.left, rectLabel.top,
ETO_CLIPPED|ETO_OPAQUE,
&rectLabel,
&g_szDigits[i+1], 1,
NULL);
rectLabel.top += m_nCellHeight;
}
pDC->SelectObject(pOldFont);
}
///////////////////////////////////////////////////////////////////////////////
//
// PaintValues()
//
// Purpose: Draw values in cells
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::PaintValues(CDC * pDC)
{
CFont *pOldFont = pDC->SelectObject(&m_fontValues);
CSize sizeValue = pDC->GetTextExtent(_T("0"));
int x_offset = m_nCellWidth/2 - sizeValue.cx/2 + 1;
int y_offset = m_nCellHeight/2 - sizeValue.cy/2 + 1;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
CRect rectCell = GetCellRect(i, j);
CRect rectValue;
rectValue.top = rectCell.top + y_offset;
rectValue.bottom = rectValue.top + m_nValueHeight;
rectValue.left = rectCell.left + x_offset;
rectValue.right = rectValue.left + sizeValue.cx;
pDC->SetBkColor(GetCellBackgroundColor(i, j));
int nGiven = m_nGivens[i][j];
int nSolution = m_nSolution[i][j];
int nHint = m_nHints[i][j];
int nUserEntry = m_nUserEntries[i][j];
COLORREF rgbValue;
int nValue;
if (nGiven)
{
rgbValue = m_rgbGivens;
nValue = nGiven;
}
else if (nHint)
{
rgbValue = m_rgbSolution;
nValue = nHint;
}
else if (nUserEntry)
{
rgbValue = m_rgbUserEntry;
nValue = nUserEntry;
}
else if (nSolution && m_bShowSolution)
{
rgbValue = m_rgbSolution;
nValue = nSolution;
}
else
{
// no value in this cell
continue;
}
pDC->SetTextColor(rgbValue);
pDC->ExtTextOut(rectValue.left, rectValue.top,
ETO_CLIPPED|ETO_OPAQUE,
&rectValue,
&g_szDigits[nValue], 1,
NULL);
}
}
pDC->SelectObject(pOldFont);
}
///////////////////////////////////////////////////////////////////////////////
//
// GetRowCandidates()
//
// Purpose: Get candidates for a row
//
// Parameters: row - row number (0 - 8)
//
// Returns: WORD - lower 8 bits represent the candidate values that are
// possible for a cell (bit 0 is never set). A value is
// possible if no other cell in the row contains the value
// (a given, a user entered value, or a hint).
//
WORD CXSudokuWnd::GetRowCandidates(int row)
{
WORD wBitFlags = 0x3FE;
for (int col = 0; col < 9; col++)
{
int nGiven = m_nGivens[row][col];
int nHint = m_nHints[row][col];
int nUserEntry = m_nUserEntries[row][col];
if (nGiven)
{
ClearBit(wBitFlags, nGiven);
}
else if (nHint)
{
ClearBit(wBitFlags, nHint);
}
else if (nUserEntry)
{
ClearBit(wBitFlags, nUserEntry);
}
}
return wBitFlags;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetColCandidates()
//
// Purpose: Get candidates for a column
//
// Parameters: col - column number (0 - 8)
//
// Returns: WORD - lower 8 bits represent the candidate values that are
// possible for a cell (bit 0 is never set). A value is
// possible if no other cell in the column contains the
// value (a given, a user entered value, or a hint).
//
WORD CXSudokuWnd::GetColCandidates(int col)
{
WORD wBitFlags = 0x3FE;
for (int row = 0; row < 9; row++)
{
int nGiven = m_nGivens[row][col];
int nHint = m_nHints[row][col];
int nUserEntry = m_nUserEntries[row][col];
if (nGiven)
{
ClearBit(wBitFlags, nGiven);
}
else if (nHint)
{
ClearBit(wBitFlags, nHint);
}
else if (nUserEntry)
{
ClearBit(wBitFlags, nUserEntry);
}
}
return wBitFlags;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetRegionCandidates()
//
// Purpose: Get candidates for a 3x3 region
//
// Parameters: row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: WORD - lower 8 bits represent the candidate values that are
// possible for a cell (bit 0 is never set). A value is
// possible if no other cell in the region contains the
// value (a given, a user entered value, or a hint).
//
WORD CXSudokuWnd::GetRegionCandidates(int row, int col)
{
WORD wBitFlags = 0x3FE;
int nStartRow = (row / 3) * 3;
int nStartCol = (col / 3) * 3;
for (int i = nStartRow; i < (nStartRow + 3); i++)
{
for (int j = nStartCol; j < (nStartCol + 3); j++)
{
int nGiven = m_nGivens[i][j];
int nHint = m_nHints[i][j];
int nUserEntry = m_nUserEntries[i][j];
if (nGiven)
{
ClearBit(wBitFlags, nGiven);
}
else if (nHint)
{
ClearBit(wBitFlags, nHint);
}
else if (nUserEntry)
{
ClearBit(wBitFlags, nUserEntry);
}
}
}
return wBitFlags;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetUnPenciledCandidates()
//
// Purpose: Get candidates that have been previously rubbed out
//
// Parameters: row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: WORD - Inverted bits 1 - 10 (bit 0 is never set)
// representing the candidates that have previously
// been rubbed out.
WORD CXSudokuWnd::GetUnPenciledCandidates(int row, int col)
{
return (~m_nUnPencil[row][col])&0x3FE;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetCandidates()
//
// Purpose: Get candidates for a row, column, and 3x3 region
//
// Parameters: row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: WORD - lower 8 bits represent the candidate values that are
// possible for a cell (bit 0 is never set). A value is
// possible if no other cell in the row, column, or region
// contains the value (a given, a user entered value, or
// a hint).
//
WORD CXSudokuWnd::GetCandidates(int row, int col)
{
WORD wRowCandidates = GetRowCandidates(row);
WORD wColCandidates = GetColCandidates(col);
WORD wRegionCandidates = GetRegionCandidates(row, col);
WORD wBitFlags = (WORD) (wRowCandidates & wColCandidates & wRegionCandidates);// & wUnPenciledCandidates);
TRACE(_T("Candidates for %d,%d: 0x%X\n"), row, col, wBitFlags);
return wBitFlags;
}
///////////////////////////////////////////////////////////////////////////////
//
// GetCellRect()
//
// Purpose: Get rect for a cell
//
// Parameters: row - row number (0 - 8)
// col - column number (0 - 8)
//
// Returns: CRect - rect of the cell
//
CRect CXSudokuWnd::GetCellRect(int row, int col)
{
CRect rectCell, rectWnd;
GetClientRect(&rectWnd);
rectCell.left = rectWnd.left + m_nXOffset + col * (m_nCellWidth + 1);
rectCell.left += g_nGridLineOffset[col];
rectCell.right = rectCell.left + m_nCellWidth;
rectCell.top = rectWnd.top + m_nYOffset + row * (m_nCellHeight + 1);
rectCell.top += g_nGridLineOffset[row];
rectCell.bottom = rectCell.top + m_nCellHeight;// - 1;
return rectCell;
}
///////////////////////////////////////////////////////////////////////////////
//
// PaintPencilMarks()
//
// Purpose: Draw pencil marks (aka candidate values) for a cell
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::PaintPencilMarks(CDC * pDC)
{
CFont *pOldFont = pDC->SelectObject(&m_fontPencilMarks);
pDC->SetTextColor(m_rgbPencilMarks);
int nXOffset = ((m_nCellWidth - (3 * m_nLabelHeight)) / 2) + 2;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
pDC->SetBkColor(GetCellBackgroundColor(i, j));
int nGiven = m_nGivens[i][j];
int nSolution = m_nSolution[i][j];
int nHint = m_nHints[i][j];
int nUserEntry = m_nUserEntries[i][j];
if (nGiven || nUserEntry || nHint || (nSolution && m_bShowSolution))
continue;
// find all possible candidates for this cell
WORD wCandidates = GetCandidates(i, j) & GetUnPenciledCandidates(i, j);
CRect rectCell = GetCellRect(i, j);
CRect rectPencilMarks;
rectPencilMarks.left = rectCell.left + nXOffset;
rectPencilMarks.right = rectPencilMarks.left + m_nLabelHeight + 2;
for (int nCandidate = 1; nCandidate <= 9; nCandidate++)
{
rectPencilMarks.top = rectCell.top + 3 + ((nCandidate-1)/3) * (m_nLabelHeight+1);
rectPencilMarks.bottom = rectPencilMarks.top + m_nLabelHeight + 2;
if (TestBit(wCandidates, nCandidate))
{
pDC->ExtTextOut(rectPencilMarks.left, rectPencilMarks.top,
ETO_CLIPPED|ETO_OPAQUE,
&rectPencilMarks,
&g_szDigits[nCandidate], 1,
NULL);
}
if (nCandidate == 3 || nCandidate == 6)
rectPencilMarks.left = rectCell.left + nXOffset;
else
rectPencilMarks.left += m_nLabelHeight;
rectPencilMarks.right = rectPencilMarks.left + m_nLabelHeight + 2;
}
}
}
pDC->SelectObject(pOldFont);
}
///////////////////////////////////////////////////////////////////////////////
//
// PaintCurCell()
//
// Purpose: Paint cell at m_nCurRow, m_nCurCol
//
// Parameters: pDC - pointer to device context object
//
// Returns: None
//
void CXSudokuWnd::PaintCurCell(CDC * pDC)
{
if ((m_nCurRow != -1) && (m_nCurCol != -1))
{
CRect rectCell = GetCellRect(m_nCurRow, m_nCurCol);
CPen pen(PS_SOLID, 1, m_rgbCurCellBorder);
CPen *pOldPen = pDC->SelectObject(&pen);
pDC->MoveTo(rectCell.left, rectCell.top);
pDC->LineTo(rectCell.right, rectCell.top);
pDC->MoveTo(rectCell.left, rectCell.top+1);
pDC->LineTo(rectCell.right, rectCell.top+1);
pDC->MoveTo(rectCell.left, rectCell.top+2);
pDC->LineTo(rectCell.right, rectCell.top+2);
pDC->MoveTo(rectCell.left, rectCell.bottom-3);
pDC->LineTo(rectCell.right, rectCell.bottom-3);
pDC->MoveTo(rectCell.left, rectCell.bottom-2);
pDC->LineTo(rectCell.right, rectCell.bottom-2);
pDC->MoveTo(rectCell.left, rectCell.bottom-1);
pDC->LineTo(rectCell.right, rectCell.bottom-1);
pDC->MoveTo(rectCell.left, rectCell.top);
pDC->LineTo(rectCell.left, rectCell.bottom);
pDC->MoveTo(rectCell.left+1, rectCell.top);
pDC->LineTo(rectCell.left+1, rectCell.bottom);
pDC->MoveTo(rectCell.left+2, rectCell.top);
pDC->LineTo(rectCell.left+2, rectCell.bottom);
pDC->MoveTo(rectCell.right-1, rectCell.top);
pDC->LineTo(rectCell.right-1, rectCell.bottom);
pDC->MoveTo(rectCell.right-2, rectCell.top);
pDC->LineTo(rectCell.right-2, rectCell.bottom);
pDC->MoveTo(rectCell.right-3, rectCell.top);
pDC->LineTo(rectCell.right-3, rectCell.bottom);
pDC->SelectObject(pOldPen);
}
}
///////////////////////////////////////////////////////////////////////////////
//
// CellFromPoint()
//
// Purpose: Get cell row, column for a point
//
// Parameters: point - point that lies within a cell
// row - returned row number (0 - 8)
// col - returned column numb | | | | | |
