/* 8. Place as few knights as possible on a chessboard in such a way that each square is controlled by at least one Knight, including the squares on which there is a Knight. How would the formulation differ if occupied squares were not to be under attack? (Schuh) [The following code requires ECLiPSe version 4 or later] */ :- lib(ic). :- lib(branch_and_bound). solve(N) :- M is N+4, % add 2 dummy rows around the board dim(Board, [M,M]), ( for(I,1,N+4), param(Board,N) do ( for(J,1,N+4), param(Board,I,N) do ( I >= 3, I =< N+2, J >= 3, J =< N+2 -> Board[I,J] :: 0..1, % proper square threatened(Board, I, J) ; Board[I,J] #= 0 % dummy square ) ) ), term_variables(Board, Vars), Sum #= sum(Vars), bb_min((labeling(Vars),print_solution(Board,N)), Sum, bb_options{strategy:step}). threatened(Board, I, J) :- Board[I-2,J-1] + Board[I-2,J+1] + Board[I+2,J-1] + Board[I+2,J+1] + Board[I-1,J-2] + Board[I-1,J+2] + Board[I+1,J-2] + Board[I+1,J+2] #> 0. print_solution(Board,N) :- ( for(I,3,N+2), param(Board,N) do ( for(J,3,N+2), param(Board,I) do Square is Board[I,J], printf("%3d", Square) ), nl ).