/*
    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
	).