QUEENS : N = 11
Updated : 23 May 2022 @ 12:10:07
list_range
solve_queens_2
:- encoding(utf8).
% le code
/*
start
DESCRIPTION OF THE PROBLEM
Problem of N independant queens
question
solve (N)
--> should print correctly all solutions
difficulties
il faut trouver sur un échiquier carré de taille N coment positionner N dames sans prise mutuelle
DIFFICULTIES
2COLUMNS
model the solving process
print a solution
example
MODEL OF THE PROBLEM
if Ln = [1, 2, ..., N]
a queen in row i is in row Ln [i]
find a permutation of Ln such that queens can not catch each other.
constraints
not same line
from the model in Ln
not same column
from the model in Ln
all different numbers
not same diagonal
should check 2 directions
solve by trying first 2, 3, ... N queens
while respecting constraints
USER'S MANUAL
queries
q1 ( N )
find first solution for N
qf (N)
Find all solutions for N
ql(N)
finds a solution for N if N is prime
examples of solutions
BOLD
2COLUMNS
N = 29
algorithm in linear time for K not multiple of 2 nor 3
structure
solve_queens
list_range
solve_queens_2
member_reste
diagonal_ok
display_board
display_line
display_queen_1
Code in prolog
BR
PRE
CODE
*insert
cf : QUEENS.pl
*/
:- use_module(library(pce)).
% utilitaires
:- encoding(utf8).
% macros utiles PROLOG
% >>> ================================== iteritems =============================================
iteritems(L, X, N) :-
iteritems_1(L, 1, X, N).
% >>> ------------------------------------------ iteritems_1 ( +Liste, +Max , -Elt, -Rang)---------------------------
% DOC
% prédicat iteritems_1 ( +Liste, +Max , -Elt, -Rang)
/*
for a list [a, b, c], will produce :
(a,1), (b, 2), etc
Syntax
iteritems (+L, -X, -N)
*/
% .
% X .. L , K
% X, K
iteritems_1([X | L], K, X, K).
iteritems_1([X | L], K, X1, K1) :-
K2 is K + 1,
iteritems_1(L, K2, X1, K1).
% <<<------------------------------------------ iteritems_1 ( +Liste, +Max , -Elt, -Rang) ---------------------------
% <<< ================================== iteritems =============================================
% >>> ================================== member_num (+X, +L, -N) =============================================
% trouve l'indice N de X dans L, sinion fail
% démarre à 1
member_num(X, L, N) :-
member_num_1(X, L, N, 1).
member_num_1(X,[X | L], K, K) :-
!.
member_num_1(X,[Y | L], K, K1) :-
K2 is K1 + 1,
member_num_1(X, L, K, K2).
% <<< ================================== member_num (+X, +L, -N) =============================================
% >>> ================================== ECRITURES SUR LE TERMINAL =============================================
/*
Pour imprimer une liste avec write
exemples
write_item ([a, b , nl, foo(1, 2), [1, 2, 3] ] )
?- L = [1, 2, nl, 4, 5, foo(x,y), [r, e, "dfghjk"] ], write_item(L).
12
45foo(x,y)[r,e,dfghjk]
L = [1, 2, nl, 4, 5, foo(x, y), [r, e|...]].
?- L = [1, 2, nl, 4, 5, foo(x,y), [r, e, "dfghjk"] ], write_item(L, " ").
1 2
4 5 foo(x,y) [r,e,dfghjk]
L = [1, 2, nl, 4, 5, foo(x, y), [r, e|...]].
?- L = [1, 2, nl, 4, 5, foo(x,y), [r, e, "dfghjk"] ], write_item(L, ",").
1,2,
4,5,foo(x,y),[r,e,dfghjk],
L = [1, 2, nl, 4, 5, foo(x, y), [r, e|...]].
syntaxe
write_item (X)
imprime les éléments de X si X est une liste
sinon imprime X
ajoute un nl à la fin
write_item (X, Sep)
idem, mais ajoute le séparateur Sep entre les items imprimés
*/
% write_item : 2 versions :1 et /2
% >>> ------------------------------------------ write_item ( X) ---------------------------
% DOC
% prédicat write_item ( X)
write_item([X | L]) :-
!,
(
member(Y,[X | L]),
(
Y = nl
->
nl
;
write_item(Y)
),
fail
;
true
),
nl.
write_item(X) :-
write(X),
nl,
!.
% <<<------------------------------------------ write_item ( X)---------------------------
% >>> ------------------------------------------ write_item ( X, Sep) ---------------------------
% DOC
% prédicat write_item ( X, Sep)
write_item([X | L], Sep) :-
!,
(
member(Y,[X | L]),
(
Y = nl
->
nl,
!
;
write(Y),
write(Sep)
),
fail
;
true
),
nl.
write_item(X , _) :-
write(X),
nl,
!.
% <<<------------------------------------------ write_item ( X, Sep)---------------------------
% <<< ================================== ECRITURES SUR LE TERMINAL =============================================
% >>> ================================== COUNTERS =============================================
init_counter(Name) :-
nb_setval(Name, 0).
init_counter(Name, Value) :-
nb_setval(Name, Value).
incr_counter(Name) :-
nb_getval(Name, C),
CNew is C + 1,
nb_setval(Name, CNew).
incr_counter(Name, Incr) :-
nb_getval(Name, C),
CNew is C + Incr,
nb_setval(Name, CNew).
incr_counter_v(Name, CNew) :-
nb_getval(Name, C),
CNew is C + 1,
nb_setval(Name, CNew).
val_counter(Name, V) :-
nb_getval(Name, V).
% <<< ================================== COUNTERS =============================================
% >>> ================================== FOR USER INTERACTION =============================================
/*
a few predicates and macros to have more readable code
for demo for Laurent chaudron
say ::=
*vars
{say_}
say_ = a0 [4:]
write_info ([{say_}])
{L}
*/
write_info(L) :-
write_info_1(L),
!,
nl.
% >>> ------------------------------------------ write_info_1 ( +Info) ---------------------------
% DOC
% prédicat write_info_1 ( +Info)
write_info_1([]) :-
!.
write_info_1([X | L]) :-
!,
write_info_1(X),
write(" "),
write_info_1(L).
write_info_1(found(X)) :-
write(found),
!,
write(" "),
write_info_1(X).
write_info_1(board(B)) :-
!,
length(B, N),
nl,
display_board(B, N).
write_info_1(board(B, N)) :-
!,
display_board(B, N).
write_info_1(([X | L])) :-
!,
write_info_1([X | L]).
write_info_1(Any) :-
write(Any).
% <<<------------------------------------------ write_info_1 ( +Info)---------------------------
% <<< ================================== FOR USER INTERACTION =============================================
% probleme des N QUEENS
% affichage
display_queen_1 :-
write("♛").
display_line(K, N, M) :-
(
M > N
->
!,
write('|'),
nl,
fail
;
(
K = M
->
display_queen_1
;
write(" ")
)
),
M1 is M +1,
!,
display_line(K, N, M1).
display_board(Sol, N) :-
(
iteritems(Sol, Elt, K),
write('|'),
display_line(Elt, N, 1),
fail
;
true
).
% affichage
/*
display _queens
INPUT
L = liste of positions in rows
N = number of queens
*/
% >>> ------------------------------------------ display_queens ( (L, N)) ---------------------------
% DOC
% prédicat display_queens ( (L, N))
% Sous-sujet 2
display_queens(L, _, 0).
display_queens([X | L ], Compteur) :-
C2 is Compteur + 1,
display_queens(L, N, C2).
% <<<------------------------------------------ display_queens ( (L, N))---------------------------
% solution du problème
% fabrication d'une liste [8, 7, 6, 5 .... 1]
% >>> ------------------------------------------ liste_range ((N, L)) ---------------------------
% DOC
% prédicat liste_range ((N, L))
% nothing
liste_range(0,[]) :-
!.
liste_range(K, [K | L]) :-
K > 0,
K1 is K-1,
liste_range(K1, L).
% <<<------------------------------------------ liste_range ((N, L))---------------------------
% solver
% solver 1 : simple backtrack et colonnes dans l'ordre 1 2 .. N
/*
solve for
just print 1 st case
print all solutions
count all solutions
*/
solve_queens(N) :-
% 1° solution
solve_queens(N, _, true).
solve_queens(N, S) :-
solve_queens(N, S, true).
solve_queens(N, S, true) :-
% % solving queens for ...
writeln("... >>> solving queens for ..."),
write(N),
nl,
liste_range(N, L1),
reverse(L1, L),
solve_queens_2(L, N, [], S),
% say for . N . found (board (S))
% [say for . N . found (board (S))
write_info([[for, N, found(board(S))]]),
!.
solve_queens(N, S, first) :-
% % solving queens for ...
writeln("... >>> solving queens for ..."),
liste_range(N, L1),
reverse(L1, L),
solve_queens_2(L, N, [], S),
!.
solve_queens(N, S, all, D) :-
% % print all queens solutions for ...
writeln("... >>> print all queens solutions for ..."),
write(N),
nl,
init_counter(counter),
liste_range(N, L1),
reverse(L1, L),
!,
(
solve_queens_2(L, N, [], S),
incr_counter(counter),
display_board(S, N),
nl,
fail
;
true
),
% prints result
val_counter(counter, D),
!,
write_info([found([D, solutions])]).
solve_queens(N, S, count, D) :-
% % counts the number of cases for
writeln("... >>> counts the number of cases for "),
write(N),
nl,
init_counter(counter),
liste_range(N, L1),
reverse(L1, L),
!,
(
solve_queens_2(L, N, [], S),
incr_counter(counter),
write('.'),
fail
;
true
),
% prints result
val_counter(counter, D),
!,
write_info([found([D, solutions, for, N, queens])]).
% solves by backtracking
/*
L ::= x1 . x2 . .... : Xi : numbers of columns
called initially with (L = [1, 2, ... N]
*/
% >>> ------------------------------------------ solve_queens_2 ( (+L, +N, +K, -Solution))---------------------------
% DOC
% prédicat solve_queens_2 ( (+L, +N, +K, -Solution))
% last line
% [], N, S
% S
solve_queens_2([], N, S, S) :-
!.
% any line
% L, N, S
% S2
solve_queens_2(L, N, S, S2) :-
% trace
% prendre un élément
member_reste(L, X, Reste),
% vérifier les diagonales
K1 is X + 1,
K2 is X -1,
diagonal_ok(S, K1, K2),
% continue la récursion
solve_queens_2(Reste, N, [X | S] , S2).
% <<<------------------------------------------ solve_queens_2 ( (+L, +N, +K, -Solution)) ---------------------------
% vérifier les diagonales
% >>> ------------------------------------------ diagonal_ok ( (Liste, X1, X2)) ---------------------------
% DOC
% prédicat diagonal_ok ( (Liste, X1, X2))
diagonal_ok([], _, _) :-
!.
diagonal_ok([X | L], K, K1) :-
(
(
X = K
;
X = K1
)
->
!,
fail
;
K2 is K + 1,
K3 is K1 -1,
diagonal_ok(L, K2, K3)
).
% <<<------------------------------------------ diagonal_ok ( (Liste, X1, X2))---------------------------
% linear solver for N
% solve in linear time for N not multiple of od nor 3
solve_queens_l(N):-
solve_queens_l(N, _, true),
!.
solve_queens_l(N, S):-
solve_queens_l(N, S, true),
!.
solve_queens_l(N, S, true) :-
solve_queens_l(N, S, P, 1),
write(S),
nl,
check_sol(S),
display_board(S, N),
nl.
solve_queens_l(N, S , P, K) :-
(
K > N
->
S = []
;
!,
X is 1 +(3 * K) mod N,
K1 is K + 1,
S =[X | S1],
solve_queens_l(N, S1, P, K1)
).
% check of solutions
check_sol(S) :-
check_sol(S, S1, S2, 0),
sort(S, So),
write("So = "),
write(So),
nl,
nl,
write("S = "),
write(S),
nl,
sort(S1, So1),
write("So1 = "),
write(So1),
nl,
write("S1 = "),
write(S1),
nl,
length(S1, N1),
length(So1, No1),
(
N1 = No1
->
!
;
write('ascending diagonal error'),
nl
),
sort(S2, So2),
write("So2 = "),
write(So2),
nl,
write("S2 = "),
write(S2),
nl,
length(S2, N2),
length(So2, No2),
(
N2 = No2
->
!
;
write('descending diagonal error'),
nl
).
check_sol([], [], [], K).
check_sol([A | L],[X | L1],[Y | L2], K) :-
X is A -K,
Y is A + K,
K1 is K +1,
check_sol(L, L1 , L2, K1).
% solver 2 : simple backtrack et colonnes dans l'ordre N/2, N/2 +-1 ..... N 1 (ou un autre ordre)
% prelever un élement et garder le reste
member_reste([X | L], X, L) :-
true.
member_reste([X | L], Y,[X | U]) :-
!,
member_reste(L, Y, U).
% tests
% >>> ================================== False =============================================
% <<< ================================== False =============================================
q11 :-
display_board([1, 2, 3], 3),
display_board( [2, 4, 1, 3], 4).
% >>> ================================== tests for only first solution =============================================
t4 :-
(
solve_queens(4, S, true),
write("solution(4, S) = "),
write(solution(4, S)),
nl,
fail
;
true
).
q2 :-
(
member(K, [3, 4, 8]),
write("K = "),
write(K),
nl,
solve_queens(K, S),
fail
;
true
).
q13 :-
L = [100, 200, 300],
(
member_reste(L, X, U),
write("q3(L, X, U) = "),
write(q3(L, X, U)),
nl,
fail
;
true
).
qs3 :-
(
solve_queens(3, S),
fail
;
true
).
qs4 :-
(
solve_queens(4, S),
fail
;
true
).
qs5 :-
(
solve_queens(5, S),
fail
;
true
).
qs6 :-
(
solve_queens(6, S),
fail
;
true
).
% <<< ================================== tests for only first solution =============================================
% >>> ================================== 8 queens =============================================
qs8 :-
(
solve_queens(8, S, all, D),
fail
;
true
).
qc8 :-
(
solve_queens(8, S, count, N),
write("N = "),
write(N),
nl,
fail
;
true
).
fs8 :-
solve_queens(8, S).
% compte le nombre de solutions
qf8 :-
K = 8,
qf(8).
% <<< ================================== 8 queens =============================================
% >>> ================================== 20 queens =============================================
qf20 :-
K = 20,
qf(20).
% <<< ================================== 20 queens =============================================
% >>> ================================== Counting solutions =============================================
% compte le nombre de solutions
qf(N) :-
(
solve_queens(N, S, count, N_sol),
write_info([found([N_sol, solutions, for, N, queens])]),
fail
;
true
).
q1(N) :-
(
solve_queens(N, S, true),
!,
true
),
% prints result
% say for . N . found (board (S))
% [say for . N . found (board (S))
write_info([[for, N, found(board(S))]]),
!.
q2(N) :-
init_counter(counter),
P = true,
solve_queens(N, S, true),
incr_counter_v(counter, C),
write("C = "),
write(C),
nl.
% solution avec algorithme linéaire
ql(N) :-
solve_queens_l(N).
% <<< ================================== Counting solutions =============================================
% tests unitaires prolog
% >>> ================================== False =============================================
% <<< ================================== False =============================================
q1 :-
liste_range(4, L),
write(L),
liste_range(8, L8),
write(L8).
q21 :-
(
L = [1, 2, 3],
write("L = "),
write(L),
nl,
iteritems(L, X, N),
write("iter(X, N) = "),
write(iter(X, N)),
nl,
fail
;
true
).
SOMMAIRE