Queens puzzle program description


terug naar Nederlandse pagina
back to Queens page
download Delphi-7 project

This 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
Therefore we introduce
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.