/*
The Crowded Chessboard
Authors: Jesper Hansen, IMM, DTU.
Authors: Joachim Schimpf, IC-Parc.
You are given a chessboard together with 8 queens, 8 rooks, 14
bishops, and 21 knights. The puzzle is to arrange the 51 pieces on
the chessboard so that no queen shall attack another queen, no rook
attack another rook, no bishop attack another bishop, and no knight
attack another knight. No notice is to be taken of the intervention
of pieces of another type from that under consideration - that is,
two queens will be considered to attack one another although there
may be, say, a rook, a bishop, and a knight between them. It is not
difficult to dispose of each type of piece seperately; the
difficulty comes in when you have to find room for all the
arrangements on the board simultaneously. (Dudeney 1917)
(Other reference: http://ite.pubs.informs.org/Vol2No2/ChlondToase/)
In this version we solve the more general problem with N queens, N
rooks, 2*N-2 bishops and K knights. The number of knights are
maximised.
With N = 8, no more than 21 knights can be placed.
With N = 9, no more than 29 knights can be placed.
With N = 10, no more than 37 knights can be placed.
With N = 11, no more than 47 knights can be placed.
With N = 12, no more than 57 knights can be placed.
With N = 13, no more than 69 knights can be placed.
With N = 14, no more than 81 knights can be placed.
With N = 15, no more than 94 knights can be placed.
With N = 16, no more than 109 knights can be placed.
To compute a 21-knights solution, call
?- chess(8,21,Solution).
to compute a maximum-knights solution, call
?- chess(8,NK,Solution).
*/
:- lib(eplex).
chess(N,NK,M) :-
% lp_set(result_channel, +output),
% lp_set(log_channel, +log_output),
dim(M,[4,N,N]), % four NxN boards of booleans
M[1..4,1..N,1..N] :: 0.0..1.0,
term_variables(M,AllVars), % all are integers
integers(AllVars),
MQ is M[1], % queens constraints
term_variables(MQ,VQ),
sum(VQ) $= N,
queens(N,MQ),
MR is M[2], % rooks constraints
term_variables(MR,VR),
sum(VR) $= N,
rooks(N,MR),
MB is M[3], % bishops constraints
term_variables(MB,VB),
NBishops is 2*N-2,
sum(VB) $= NBishops,
bishops(N,MB),
bishops_extra(N,MB), % optional redundant constraint
MK is M[4], % knights constraints
term_variables(MK,VK),
sum(VK) $= NK,
knights(N,MK),
(for(I,1,N), % only one piece on every field
param(M,N) do
(for(J,1,N),
param(I,M) do
sum(M[1..4,I,J]) $=< 1
)
),
integers([NK]),
optimize(max(NK),_C), % maximise using eplex
writeln(knights=NK),
print_board(M, N).
print_board(M, N) :-
(for(I,1,N),
param(M,N) do
(for(J,1,N),
param(I,M) do
( M[1,I,J] =:= 1 -> write('Q ')
; M[2,I,J] =:= 1 -> write('R ')
; M[3,I,J] =:= 1 -> write('B ')
; M[4,I,J] =:= 1 -> write('K ')
; write(' ')
)
),
nl
).
/*
Constrain all the diagonals to have at most one bishop.
*/
bishops(N,M) :-
(for(I,1,N-1),
param(M,N) do
(for(J,1,I),
foreach(C1,Diag1),
foreach(C2,Diag2),
param(I,M,N) do
C1 is M[I-J+1,J], % south->west
C2 is M[I-J+1,N-J+1] % north->west
),
sum(Diag1) $=< 1,
sum(Diag2) $=< 1,
(for(J,1,N-I+1),
foreach(C3,Diag3),
foreach(C4,Diag4),
param(I,M,N) do
C3 is M[J+I-1,J], % south->east
C4 is M[J+I-1,N-J+1] % north->east
),
sum(Diag3) $=< 1,
sum(Diag4) $=< 1
).
/*
Placing 2*N-1 bishops requires that exactly two bishops
are placed in the corners corresponding to the two longest
diagonals. We can fix the two corners and hereby avoid
symmetries.
*/
bishops_extra(N,M) :-
M[N,N] + M[1,N] $= 2.
/*
Instead of less than or equal 1 constraints, we can use equality
constraints, since exactly one rook of N and one queen of N
are placed in each row and column.
*/
rooks(N,M) :-
(for(I,1,N),
param(M,N) do
sum(M[I,1..N]) $= 1,
sum(M[1..N,I]) $= 1
).
/*
A queen is just a rook and a bishop combined.
*/
queens(N,M) :-
rooks(N,M),
bishops(N,M).
/*
Any two fields which are a knight's move apart
can have at most one knight
*/
knights(N,M) :-
(for(I,1,N),
param(M,N) do
(for(J,1,N),
param(M,N,I) do
add_if_on_board(N,M,I,J,I+1,J+2),
add_if_on_board(N,M,I,J,I-1,J+2),
add_if_on_board(N,M,I,J,I+2,J+1),
add_if_on_board(N,M,I,J,I+2,J-1)
)
).
add_if_on_board(N,M,I1,J1,I,J) :-
(I >= 1, I =< N, J >= 1, J =< N ->
M[I,J] + M[I1,J1] $=< 1
;
true
).