 |
Queens puzzle program description |  |
 |
terug naar Nederlandse pagina
back to Queens page
download Delphi-7 projectThis is a description of the Queens puzzle Delphi program.
How many queens are needed minimally to cover all fields of a chessboard?
This Delphi program helps finding the answer.
Before writing any program the objectives must be clear.
We want to:
-
1. have the user search for solutions by adding/removing queens
2. have the program search for solutions
4. select the number of queens allowed
User / program mode
Two SpeedButtons are placed on form1, named SolveBtn and TryBtn.Their groupIndex is 1, only one button may be UP the the time.
The buttons share the OnClick event:
procedure TForm1.tryBtnClick(Sender: TObject); begin playermode := tryBtn.Down; …........ end;Variable playermode is true for allowing the player to modify the board.
If the program searches for a solution, there are some states:
-
1. a new search starts
2. a search ends with no solution found
3. a search ends with a solution found
4. a search is temporarily pauzed to keep contact with the Windows system
Variable playermode is true for allowing the player to modify the board.
-
If the program searches for a solution, there are some states:
1. a new search starts
2. a search ends with no solution found
3. a search ends with a solution found
4. a search is temporarily pauzed to keep contact with the Windows system
type TsearchResult = (srStart,srSolved,srNoSolution,srTimeout); .....and the call:
procedure GoSolve(var sr : TsearchResult);variable sr defines the start condition and also reports the exit condition.
After a while, the GoSolve procedure exits with sr=srTimeout
just to allow the processing of messages by the operating system.
A call with sr=srTimeout will resume the search process.
The main tasks during the search is adding/removing queens to/from a field.
Coding the board
A chessboard has 8 * 8 fields (colums * rows).
The board is painted in paintbox1 on form1.
A field counts 60 * 60 pixels.
The queen is a bitmap of 50*50 pixels and is painted by the canvas.draw method.
type TField = record
Q : byte; //0: empty 1:queen
lines : byte;//1:-- 2:| 4:/ 8:\
end;
Tpos = record
x,y : byte;
end;
var Qlist : array[1..8] of Tpos; //place of queen on board
Qcount : byte;
board : array[1..8,1..8] of TField;
playermode : boolean = false;
Tfield.Q = 1 if it holds a queen, else it is 0
Tfield.lines uses bits 0..3 A bit is set if it holds a line indicating coverage by a queen on another field.
Board[1..8,1..8] is a 2 dimensional array holding all the fields.
Qlist[1..8] is a list of queens by board position.
Qcount is the number of queens on the board, so the number of valid entries in Qlist[1..8]
Add / Delete queens
To add a queen in field at column i and row j:procedure addqueen(i,j : byte); begin inc(Qcount); board[i,j].Q := 1; paintfield(i,j); fixlines(i,j); Qlist[Qcount].x := i; Qlist[Qcount].y := j; end;
Paintfield(i,j) paints the field, see the source code for details.
Fixlines(i,j) adds horizontal, vertical and diagonal lines to all fields that are covered by the new queen.
Also for each covered field the corresponding bit in Tfield.lines is set.
Deleting a queen is very similar, see the source code.
The Fixlines( ) procedure needs some explanation.
Fixlines(i,j)
Say we add a queen at field(3,4)
Then we cover a row from (1,4) …. (8,4) and a column from (3,1) … (3,8).
The diagonal lines are a problem and in mind we extend the board left and right.
Now we cover by line / : (-1,8) … (6,1) and by line \ : (0,1) … (7,8).
These are 8 fields each, but of course we only paint fields in the range from 1..8
In general, adding a queen in field (i,j) affects fields:
for / starting at (i+j-8 , 1) and next 7 fields diagonally up.
for \ starting at (i-j+1 , 1) and next 7 fields diagonally down.
Solving the puzzle
The method used is basically of the type “brute force”.This means that simply all possibilities are tried until,
by accident, a solution is found.
However, there is a time saving measure.
We do not place a queen on a covered field which is
simply done by avoiding fields which have .Q > 0 or .lines > 0.
Also we must try all possibilities in a systematical way not to forget solutions.
Array Qlist[1..8] of Txy holds the (x,y) positions of the queens
and this array is regarded a counter.
[1] is the upper- and [8] is the lower element.
A (x,y) field counts x from 1 ..8 and on overflow y is incremented by 1.
So the first (lowest) count is (1,1) and to upper count is (8,8).
The GoSolve procedure does the work.
It is small but rather tricky and requires concentration to understand.
Below is the flowchart:
Qcount holds the number of queens on the chessboard.
Adding a queen increments Qcount and adds the (i,j) values to Qlist[Qcount].
Deleting a queen decrements Qcount.
All actions (addqueen,deletequeen,next free field) apply to field[i,j].
Only nextfreefield modifies i and j , indicating the next free field.
At the start, i and j are set to 1, Qcount = 0.
(1,1) is the next free field and here the first queen is placed.
The next queens are placed in the next free fields
until the selected queencount is reached.
Next the last queen is deleted at (i,j) and the next free field after (i,j) is selected.
If no free field is found and the board is empty, the no-solution exit is taken.
Reloading i,j from Qlist[Qcount] selects the position
of the previous element if a queen was deleted before which decremented Qcount.
If the maximual number of queens is 4, which are all placed then number 4 is deleted,
but i,j unchanged.
Then a new free field is selected to place queen number 4.
If no free field is found, then i,j is loaded from queen 3
which is deleted and a next free field is searched for.
Below is the complete Gosolve procedure:
procedure GoSolve(var sr : TsearchResult);
//try solve puzzle for Qcount number of queens
//maxQueen has been set
var i,j : byte;
fnext : boolean; //solution check flag
timeout : word;
begin
timeout := 0;
case sr of
srStart : begin
i := 0; j := 0;
end;
srSolved : begin
i := Qlist[Qcount].x;
j := Qlist[Qcount].y;
end;
srNosolution : exit;
srTimeout : begin
i := saveI;
j := saveJ;
end;
end;
//
repeat
inc(timeout);
if timeout = 100 then
begin
saveI := i;
saveJ := j;
searchresult := srTimeout;
exit;
end;
if (Qcount = MaxQueen) then deleteQueen(i,j);
if nextFreeField(i,j) then
begin
fnext := true;
addQueen(i,j);
end
else
begin
fnext := false;
if Qcount > 0 then
begin
i := Qlist[Qcount].x;
j := Qlist[Qcount].y;
deleteQueen(i,j);
end
else begin
sr := srNoSolution;
exit;
end;
end;//else
until fnext and checksolution;
sr := srSolved;
end;
A tric is the last line: until fnext and checksolution;
In the menu: project/options/compiler, full boolean evaluation must not be checked.
The expression is false if fnext is false and the checksolution procedure will not be called.
Keeping control
In most cases, the search will terminate after a very short time.However if it takes longer we want to be able to terminate the process prematurily.
This requires that Windows is granted some time to process any pending messages.
The tric here is a timeout variable, called TimeOut.
At the start it is set to zero and it is incremente
each time the repeat loop is executed.
If a value of 100 is reached, the local variables i,j
are stored in saveI,saveJ and the search procedure is exited with the srTimeOut search result.
Upon reentry i,j are reloaded and the search continues.
Let's look who calls the GoSolve procedure:
procedure TForm1.GoBtnClick(Sender: TObject);
begin
if searchbusy then exit;
searchbusy := true;
case searchresult of
srStart : begin
clearPuzzle;
paintBoard;
GoProc;
end;
srNoSolution : msg(11);
srSolved : GoProc;
end;//case
searchbusy := false;
end;
The search result will be stStart after a RESET or after clearing the board.
In the case of a solved puzzle, a new search is started to find another solution.
What does GoProc
procedure GoProc;
begin
repeat
msg(10);
GoSolve(searchresult);
application.processmessages;
until (searchresult <> srTimeOut) or resetRequest;
if resetRequest then
begin
ProcReset;
msg(13);
end
else
case searchresult of
srSolved : msg(9);
srNoSolution : msg(12);
end;//case
end;
GoSolve is repeated until there is no timout (so a yes/no solution).Also the application.processmessages lets Windows process pending messages,
which allows the RESET button to be pressed.
Boolean variable resetRequest is set if the RESET button is pressed while searching is in progress.
For details please refer to the source code listing.
