Search Exercises
----------------
1. Use the search/6 predicate from the ic_search library and the
standard model for the queens problem (given below) to find ONE
solution to the 42-queens problem.
With a naive search strategy this requires millions of backtracks.
Using heuristics and/or incomplete search, try to find a solution
in less than 100 backtracks!
2. How many solutions does the 9-queens problem have?
3. Solve the "8 sticky queens problem": Assume that the queens
in neighbouring columns want to stick together as close as possible.
Minimize the sum of the vertical distances between neighbouring queens.
What is the best and what is the worst solution for this problem?
Standard model for the queens problem:
queens(N, Board) :-
length(Board, N),
Board :: 1..N,
( fromto(Board, [Q1|Cols], Cols, []) do
( foreach(Q2, Cols), param(Q1), count(Dist,1,_) do
noattack(Q1, Q2, Dist)
)
).
noattack(Q1,Q2,Dist) :-
Q2 #\= Q1,
Q2 - Q1 #\= Dist,
Q1 - Q2 #\= Dist.