8 queens 4

Description

Program solves 8 queens problem

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Download

Program source code: 8_queens_4.pl

Listing

% Figure 4.9   Program 2 for the eight queens problem.
 
 
% solution( Queens) if 
%   Queens is a list of Y-coordinates of eight non-attacking queens
 
solution( Queens)  :-
   permutation( [1,2,3,4,5,6,7,8], Queens),
   safe( Queens). 
 
permutation( [], [] ). 
 
permutation( [Head | Tail], PermList)  :-
   permutation( Tail, PermTail),
   del( Head, PermList, PermTail).   % Insert Head in permuted Tail 
 
% del( Item, List, NewList): deleting Item from List gives NewList
 
del( Item, [Item | List], List). 
 
del( Item, [First | List], [First | List1] )  :-
   del( Item, List, List1). 
 
% safe( Queens) if 
%   Queens is a list of Y-coordinates of non-attacking queens
 
safe( [] ). 
 
safe( [Queen | Others] )  :-
   safe( Others),
   noattack( Queen, Others, 1). 
 
noattack( _, [], _). 
 
noattack( Y, [Y1 | Ylist], Xdist)  :-
   Y1-Y =\= Xdist,
   Y-Y1 =\= Xdist,
   Dist1 is Xdist + 1,
   noattack( Y, Ylist, Dist1).

Comments

pl/prolog/pllib/8_queens_4.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0