! N Queens problem.
On an N by N chessboard place N Queens
so that there is at most one queen in
each row, each column, and each diagonal.
This version solves it using the optimizer.
There are direct methods of solution that
take time proportional to N;
! Keywords: Chess, Queens problem, N Queens problem, Puzzles;
SETS:
SIDE;
SXS(SIDE,SIDE): Y;
ENDSETS DATA:
SIDE = 1..8;
ENDDATA
! Variables:
Y(i,j) = 1 if there is a queen in row i,
column j of the board;
N = @SIZE(SIDE);
! Exactly one in each row;
@FOR( SIDE(i):
@SUM( SIDE(j): Y(i,j)) = 1;
);
! Exactly one in each column;
@FOR( SIDE(j):
@SUM( SIDE(i): Y(i,j)) = 1;
);
@FOR( SIDE(k):
! At most one in each lower left to upper right diagonal;
! Below main diagonal;
@SUM( SXS( i,j)| i-j #EQ# k-1: Y(i,j)) <= 1;
! Above main diagonal;
@SUM( SXS( i,j)| j-i #EQ# k-1: Y(i,j)) <= 1;
! At most one in each upper left to lower right diagonal;
! Below main diagonal;
@SUM( SXS( i,j)| i+j #EQ# k+1: Y(i,j)) <= 1;
! Above main diagonal;
@SUM( SXS( i,j)| i+j #EQ# k+N: Y(i,j)) <= 1;
);
! The Y's can be only 0 or 1;
@FOR( SXS: @BIN(Y));
!Display the chessboard(for N <= 20);
DATA:
@TEXT() = @WRITE( ' The chessboard:', @NEWLINE( 1), ' ');
!The @IF's insert an extra space for single digit numbers;
@TEXT() = @WRITEFOR( SIDE(i):' ', @if(i #LT# 10,' ',''),SIDE(i));
@TEXT() = @WRITE( @NEWLINE( 1));
@TEXT() = @WRITEFOR( SIDE( I): @IF(I#LT#10,' ',' '), SIDE( I),
@WRITEFOR( SIDE( J): ' ', @IF( Y( I, J) #GT# .5, 'Q', '.')),
@NEWLINE( 1)
);
@TEXT() = @WRITE( @NEWLINE( 1));
ENDDATA
|