 |
Mini-Sudoku program description |  |
 |
download program. download Delphi project.For a description of the mini-sodoku puzzle look [here].
This Delphi-7 project has 3 units:
| unit1 | Events, drawing, control |
| game_unit | Game functions and procedures for hints and warnings |
| io_unit | functions and procedures for loading en saving games |
Drawing
Numbering of cells, rows, columns and groups: |
 |
To avoid annoying flickering, painting is done on a bitmap called map
and individual cells or the complete map are copied to the paintbox.
Functions and procedures that assist is drawing are (see unit1) :
procedure Cell2XY(var x,y: smallInt; cell : byte); //returns left-top coordinates of a cell
function XY2Cell(x,y : smallInt) : byte; //returns cell of mouse X,Y coordinates
function GetCellRect(cell : byte) : Trect; //returns rectangle of cell
procedure cellToBox(cell : byte); //copies cell in map to the paintbox
procedure paintedges(ctrl : Tcontrol; col1,col2 : longword; w : byte);
//on the form canvas, paint frame around the paintbox or other control using colors col1,col2 with width of w.
procedure paintGrid; //paint the cell and group bounderies on the map
procedure paintcell(cell : byte); //paints a cell
Data formats
type TNtype = (ntEmpty,ntOrg, ntPlay,ntHint);//cell type
Tgamestate = (gsNew,gsPlay);
TGame = record
ntype : TNtype;
nr : byte; //number in cell
options : byte; //bit n set for option n
red : byte; //bit set if redundant option
green : byte; //bit set for valid option
col : byte; //the column of the cell
row : byte; //the row of the cell
group : byte; //the group of the cell
end;
var game : array[1..36] of Tgame;
gamestate : Tgamestate = gsNew;
The col, row, group fields of Tgame are set once.These values are supplied by (see game_unit)
function GetColumn(cell : byte) : byte;
function GetRow(cell : byte) : byte;
function GetGroup(cell : byte) : byte;
The rectangles of the option numbers in a cell are preset (relative to the cell) in
const optionrect (unit1).
Hints
Much code is involved in hint processing.Pressing the hint image (lamp) calls procedure searchHints ; (unit1).
If variable Hintresult is set as result of a previous hint search,
then procedure procHints is called to apply the earlier found hints.
Now function Hint2 : byte; is called (game_unit).
If Hint 2 finds no hint, function Hint1 : byte; is called.
The resulting hint byte contains this information:
00xx xxxx : xxxxxx is the the number of a cell having only one option (hint1).
10aa nnnn : aa : 1 row; 2 column; 3 group; (hint2)
nnnn : row, column or group number
function Hint1 scans all cell options while calling function PopCount(n : byte) : byte;which returns the number of 1 bits in the option field.
If just 1 option is present, this number may be entered in the cell.
The option is placed in a green rectangle by setting the same bit in the green field of the cell.
function Hint2 requires more code and consists of 4 loops.
Flowchart:
To select all combinations of cells per row, column or group a counter
called rnk counts from 0 to maxrank -1.
Maxrank is the number of combinations possible when a choice is made of k cells from 6.
In math, a combination is a choice of some (k) elements from N where
-
1. each element may be choosen just once and
2. the sequence of the choice is not important.
Combcount(6,1) = 6 rank 0 = 00000010 rank 5 = 01000000 (select 1 cell from 6) Combcount(6,2) = 15 rank 0 = 00000110 rank 14 = 01100000 (select 2 cells of 6) Combcount(6,3) = 20 rank 0 = 00001110 rank 19 = 01110000 (select 3 cells of 6)Note: combcount(6,4) = combcount(6,2) and combcount(6,5) = combcount(6,1)
(select 0s instead of 1s)
The combination, given the number of choices (k) and the rank, is calculated by
function Combination(k,rank : byte) : byte;
The result byte is a bit vector: a bit (1..6) is set if the cell(1..6) is choosen.
Example
Above picture shows hints in row 5.
Columns 1,3,4 have options 2,5,6 so these options cannot be present in column 6.
Lets see how the program finds this. (function Hint2 in game_unit)
crg = 1 (row is selected)
n = 5 (row 5 is selected)
array a[1..5] is loaded with row 5 cells: (25,26,27,28,29,30)
k = 3 ( 3 cells are selected)
rnk = 4 (rank 4 of 3 choices out of 6)
comb = 0 0 0 1 1 0 1 0 (bits 1, 3, 4 are set, which selects
cells 25, 27, 28 from array a )
options sum = 2 or 5 or 6 = 1 1 0 0 0 1 0 0
Popcount (11000100) = 3 = k
...hit.
Warnings: Checking for solutions and errors
This is done by procedure analyseGame(var ar : word); The results are displayed if the warnings checkbox is activated. Format of variable ar (analyse result)
0000 0000 0000 0000 OK
0100 0000 00xx xxxx missing options in cell xxxxxx
10aa 0nnn xxxx xxxx aa=1: row; 2:column; 3 group; missing options
nnn: number of row, column or group
xxxxxx (bit set if missing option)
1100 xxxx xxxx xxxx Solution found, xxxx xxxx xxxx: hint count
All cells are scanned and for each column, row or group the options are summed (or ed)Then a Popcount is performed on all sums.
Also the number of cells with a digit are counted.
A count of 36 indicates a solution.
Save and load
For saving, the contents of Game[ ] are compressed in a buffer : array[0..42] of word.This s done by procedure fillbuffer;
Format:
buffer - - - - - - - - - - - - - - - - [ 0] i m [ 1] i n [ 2] u s [ 3] o d [ 4] u k [ 5] options type nr cell 1 [40] options type nr cell36 [41] 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 end of fileThe transfer is made by a Blockwrite operations.
When opening a file, the buffer is filled by a Blockread and the contents are
unpacked and stored in game[ ].
This is done by function Emptybuffer : byte;
The result = 0 for a successfull load operation.
This concludes the Mini-Sudoku solver program description.
Please refer to the source code for details.
