Futoshiki Program description

back to futoshiki page
terug naar futoshiki pagina
download complete Delphi-7 project

This is the description of my Delphi-7 program for solving Futoshiki puzzles.

The project has 3 units and 2 forms:
    - unit1 : menu's , event handling , game control , game painting, load and save
    - gameunit : data structures and procedures to assist in puzzle solving
    - printunit : procedures to paint and print puzzles
    - form1 : display of game , holds buttons , shows messages
    - printform : shows selected puzzles for printing , holds control buttons

The futoshiki project uses buttons of my DavArrayButton component
download Dav7Components

Data structures

A puzzle has 5 rows of 5 columns, so there are 25 fields.


type TFieldType = (mtFixed,mtPlayer,mtTrial);
     Tfield = record
               bf      : byte; //1,2,4,8,16,32
               ntype   : TFieldType;//game; player; trial
               options : byte; //bits 1..5
               opcodeR : byte; //0:none; 1 < ; 2: > than right
               opcodeB : byte; //0:none; 1 < ; 2: > than bottom
              end;
      TMove = record
               mcol : byte;
               mrow : byte;
              end;

var game : array[1..5,1..5] of Tfield;
    colOpts : array[1..5] of byte;
    rowOpts : array[1..5] of byte;
    movelist : array[1..25] of TMove;
    movecount : byte;
ntype may be
    mtFixed: field contains a preset number, not changeable by player
    mtPlayer : this field number was typed by the player, not changeable by solver procedure
    mtTrial : the solver may add moves to search for a solution
The solver initially changes all empty fields to the mtTrial mode.

bf (byte) holds the entered number in the following format:

number 0 : byte = 0000 0001 (empty field)
number 1 : byte = 0000 0010
number 2 : byte = 0000 0100
number 3 : byte = 0000 1000
number 4 : byte = 0001 0000
number 5 : byte = 0010 0000

The number is the bit set in the bf byte.
So, the next number n is (n shl 1)

Options : same as the bf field but a bit is set if the option is present.

OpCodeR:
0 : no opcode
1 : operator is <
2 : operator is >

OpCodeB: similar as above for lower operator.

ColOpts[1..5] : bit set if option is present for this column.
RowOpts[1..5] : bit set if option is present for this row

TMove:
A player move is recorded as the column (mcol) and row (mrow).
MoveList[...] is the list of player moves.
MoveCount is the number of player moves.

Calculation of Options

In an empty puzzle all options are $3e = 0011 1110 (bits)
If a number (say 3) is added in column 1, row 5 then
    - the fields bf value becomes 0000 1000 (bit 3 set).
    - colOpts[1] becomes colOpts[1] xor bf
    - rowOpts[5] becomes rowOpts[5] xor bf
A number entered in a field drops the options for that row and column.
procedure CalculateOptions takes care.

The presence of an operator further may drop options in an empty field.
It does not affect row and column options.

Things area little more complicated here.
See procedure procOperators.
This procedure repeats itself until no more changes are noticed.
Reason is, that operators may influence each other.

There are several helper routines for the reduction of options by operators:
    - procOperatorField(..)
    - HIMASK ......... bitmask excluding the lowest option in a field
    - LOMASK ........ bitmask excluding the highest option in a field
    - HIMASK2 ....... bitmask excluding the 2 lowest options ( < .. > case)
    - LOMASK2 ...... bitmask excluding the 2 highest options ( > .. < case)
The LOMASK2 and HIMASK2 functions have 1 byte as parameter input,
which is the OR'd value of the options right and left of an operator.
See puzzle description for an explanation.
See the source code for details.

Menu structure

The main menu is a TDavArrayBtn component having 1 row of 5 buttons.
One button may be down at the time.
The Menubutton variable holds the pressed button: 
type TMenuButton = (mbLoad,mbSave,mbprint,mbNew,mbHelp,mbPlay,mbOff);
...
var menubutton : TMenubutton
The value of menubutton directs events from keyboard or mouse to the right procedures.

New Game

MenuButton = mbNew.
There are two ways to enter a number in an empty field.

1. By keyboard.
Typed numbers are written in the field that is marked.
var markedRow : byte;
    markedColumn : byte;
indicate where the marker is placed.
The marker is moved by the cursor keys or the space bar.

2. By mouse
While moving the mouse pointer over the game, the area covered is recorded in variable scanfield 
type TscanType = (stNone,stOption,stOperator,stDigit);
     Tscanfield = record
                   stype : TscanType;
                   scol  : byte;
                   srow  : byte;
                   snr   : byte;
                  end;
....
var scanfield : TScanfield;
...
function getScanfield(x,y : word) : TScanField;
begin
...
end;
stype = stOption if mousepointer is over an option field.
stype = stOperator if over an operator field.
stype = stDigit if over a number.
scol is the column
srow is the row
snr is the option number or the operator field (1 right, 2 down).
Function GetScanfield gathers this information during mouse moves.

On a mouse down, the scanfield information is processed.

Generating Hints

When the Hint button is down (on) after a move the field options are searched for
    1. a single option in a field
    2. a field having the single option for it's row or column
    2. a field being out of options
procedure procHints; takes care.
function SingleBit(b : byte) : boolean; is a helper, true is returned if byte b has just one bit set.

Reducing field Options

See point 5. of the game description.

This part is somewhat more complicated.
Observe a column or row having options per field, some fields filled in with a number.
Finally, all fields are filled with numbers 1..5.
But not every number fits in a field.
Purpose is to squeeze out redundant options in each column and row.
All permutations are generated of numbers 1..5 and a permutation is compared
against the field options.
(a permutation is a sequence of elements, numbers 1..5 in this case).
If there is a match (permutation allowed in row or column) than the bits per field are OR'd.

Say a row has options (1,2) (1,2) (1,2,3,4) (1,2,3,5) (2,4,5)
Since the first 2 fields must hold numbers 1, 2 finally, these numbers cannot be options in fields 3,4,5.
Option reduction results in (1,2) (1,2) (3,4) (3,5) (4,5)

At create time a table with all 120 permutations (0..119) of numbers 1..5 is generated.
procedure makepermutations; takes care
var permutation : array[1..5,0..119] of byte;


function procPermGame : boolean; checks the game rows and columns.
It calls function procPermGroup(var grp : TGroup) : boolean; for each row and column.

Solving a puzzle

Press this button to solve a puzzle.
The added numbers are colored orange.

Press the solve button again to check if more solutions exist.
A good puzzle however has one solution only.

function SolveGame(scode : TsolveCode) : TsolveCode; does the work.
Only the row- and column options are used, the options of individual fields are not used or altered.
variable m is the trial move (2,4,8,16,32) for numbers 1,2,3,4,5.
xcol, xrow are pointing to the field.
The method used is Brute Force.
Simply all numbers are tried in a systematical way until a solution is found or all possibilities
are exhausted.
type TSolveCode = (scStart,scSolved,scEnd);
...
var solveResult : TSolveCode = scStart; //in unit1
scStart : unsolved game
scSolved : solution found (result) or search for next solution (parameter)
scEnd : no solution found;
See flowchart below with entry part of function SolveGame:



Below is the remaining flowchart for the search for a solution:



Load and Save

The save format is: 
type TA = array[1..27] of word; //load,save
The game is saved as a typed file of TA.

word
    1  |        u       |        f        |
    2  |        o       |        t        |
    3  |       bf       | x ntype   R   B | ---[1,1] field
	.......................................
   27  |       bf       | x ntype   R   B | ---[5,5] field
The filename is preceded by "fut-", there is no extension.

This concludes the program description.
Please refer to the source code for details.