Category : Files from Magazines
Archive   : ITP9004.ZIP
Filename : QUEEN3.PAS

{************************************************
* QUEEN3 - the third attempt at solving the *
* queens problem. *
* *
* INP: c - the column # to place a queen in *
* n - the maximum column (& row) number *
* USES: Soln - updates this solution counter *
* whenever a queen is successfully placed *
* in the n'th column. *
************************************************}

UNIT Queen3;

INTERFACE

CONST
MaxBrd = 25;

VAR
{Chess brd}
Board : ARRAY[0..MaxBrd+1,0..MaxBrd+1] OF Integer;
Solns : Integer;

PROCEDURE InitBoard;
PROCEDURE Queens(C,N: Integer);


IMPLEMENTATION


PROCEDURE InitBoard;
BEGIN
FillChar(Board,SizeOf(Board),#0);
Solns := 0
END;


PROCEDURE Queens;

VAR
I,J,K : Integer;
Legal : Boolean;

BEGIN
{Have we found a solution?}

IF C=N THEN
Inc(Solns)
ELSE

{Check each spot in the column}


BEGIN
FOR I:= 0 TO N-1 DO
BEGIN
{ Is square attacked by other queen?}
IF (Board[I,C] = 0) THEN
BEGIN
{ No: take this square, and mark }
{ all attacked squares to the right}
Board[I,C] := -1;
K := 1;
FOR J := C+1 TO N-1 DO
BEGIN
Inc(Board[I,J]); { On same row }
IF (I+K < N) THEN { On + diagonal}
Inc(Board[I+K,J]);
IF (I-K>=0) THEN { On - diagonal}
Inc(Board[I-K,J]);
Inc(K)
END;

{ Now, compute rest of solution }

Queens(C+1,N);

{ Unmark this square, & all squares}
{ attacked by this queen }
Board[I,C] := 0;
K := 1;
FOR J := C+1 TO N-1 DO
BEGIN
Dec(Board[I,J]); {On same row}
IF (I+K < N) THEN {On + diagonal}
Dec(Board[I+K,J]);
IF (I-K >= 0) THEN { On - diagonal}
Dec(Board[I-K][J]);
Inc(K)
END;
END;
END;
END;
END;


END.