home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / examples.arc / EXAMPL57.PRO < prev    next >
Encoding:
Prolog Source  |  1986-10-07  |  1.7 KB  |  57 lines
  1. /* Program 57 */
  2. /*
  3.   This program places n queens on a chess board by
  4.   exhaustive search.  For this reason it takes
  5.   awhile, taking slightly over three minutes to
  6.   place 8 queens using a 6 Mhz AT type machine.
  7. */
  8.  
  9. domains
  10.     queen = q(integer,integer)
  11.     queens=queen*
  12.     freelist = integer*
  13.     board=board(queens,freelist,freelist,freelist,freelist)
  14. predicates
  15.     placeN(integer,board,board)
  16.     place_a_queen(integer,board,board)
  17.     nqueens(integer)
  18.     makelist(integer,freelist)
  19.     findandremove(integer,freelist,freelist)
  20.  
  21. goal
  22.   write("Enter the number of queens.\nMore than 3 and less than 9."),nl,
  23.   readint(Num), 
  24.   clearwindow,
  25.   writef("solving the % queens problem.",Num),nl,
  26.   write("[ctrl][break] to stop"),nl,
  27.   time(_,M1,S1,H1),
  28.   writef("start time: %:%.%\n",M1,S1,H1),
  29.   nqueens(Num),
  30.   time(_,M2,S2,H2),nl,
  31.   writef("end time: %:%.%\n",M2,S2,H2).
  32.   
  33. clauses
  34.     nqueens(N):-
  35.         makelist(N,L),Diagonal=N*2-1,makelist(Diagonal,LL),
  36.         placeN(N,board([],L,L,LL,LL),board(Final,_,_,_,_)),write(Final).
  37.  
  38.     placeN(_,board(D,[],[],D1,D2),board(D,[],[],D1,D2)):-!.
  39.     placeN(N,Board1,Result):-
  40.         place_a_queen(N,Board1,Board2),
  41.         placeN(N,Board2,Result).
  42.  
  43.     place_a_queen(N,board(Queens,Rows,Columns,Diag1,Diag2),
  44.             board([q(R,C)|Queens],NewR,NewC,NewD1,NewD2)):-
  45.         findandremove(R,Rows,NewR),
  46.         findandremove(C,Columns,NewC),
  47.         D1=N+C-R,findandremove(D1,Diag1,NewD1),
  48.         D2=R+C-1,findandremove(D2,Diag2,NewD2).
  49.  
  50.    findandremove(X,[X|Rest],Rest).
  51.    findandremove(X,[Y|Rest],[Y|Tail]):-
  52.         findandremove(X,Rest,Tail).
  53.  
  54.    makelist(1,[1]).
  55.    makelist(N,[N|Rest]):-
  56.         N1=N-1,makelist(N1,Rest).
  57.