home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
prolog
/
library
/
prolo_c
/
exampl57.pro
< prev
next >
Wrap
Text File
|
1986-10-06
|
2KB
|
57 lines
/* Program 57 */
/*
This program places n queens on a chess board by
exhaustive search. For this reason it takes
awhile, taking slightly over three minutes to
place 8 queens using a 6 Mhz AT type machine.
*/
domains
queen = q(integer,integer)
queens=queen*
freelist = integer*
board=board(queens,freelist,freelist,freelist,freelist)
predicates
placeN(integer,board,board)
place_a_queen(integer,board,board)
nqueens(integer)
makelist(integer,freelist)
findandremove(integer,freelist,freelist)
goal
write("Enter the number of queens.\nMore than 3 and less than 9."),nl,
readint(Num),
clearwindow,
writef("solving the % queens problem.",Num),nl,
write("[ctrl][break] to stop"),nl,
time(_,M1,S1,H1),
writef("start time: %:%.%\n",M1,S1,H1),
nqueens(Num),
time(_,M2,S2,H2),nl,
writef("end time: %:%.%\n",M2,S2,H2).
clauses
nqueens(N):-
makelist(N,L),Diagonal=N*2-1,makelist(Diagonal,LL),
placeN(N,board([],L,L,LL,LL),board(Final,_,_,_,_)),write(Final).
placeN(_,board(D,[],[],D1,D2),board(D,[],[],D1,D2)):-!.
placeN(N,Board1,Result):-
place_a_queen(N,Board1,Board2),
placeN(N,Board2,Result).
place_a_queen(N,board(Queens,Rows,Columns,Diag1,Diag2),
board([q(R,C)|Queens],NewR,NewC,NewD1,NewD2)):-
findandremove(R,Rows,NewR),
findandremove(C,Columns,NewC),
D1=N+C-R,findandremove(D1,Diag1,NewD1),
D2=R+C-1,findandremove(D2,Diag2,NewD2).
findandremove(X,[X|Rest],Rest).
findandremove(X,[Y|Rest],[Y|Tail]):-
findandremove(X,Rest,Tail).
makelist(1,[1]).
makelist(N,[N|Rest]):-
N1=N-1,makelist(N1,Rest).