:- use_module(library(lists), [member/2]).
:- use_module(contestlib, [for/3]).
knights(N,Max) :-
PlacedKnights = [],
findall((X,Y),(for(X,1,N),for(Y,1,N)),Squares),
knights(Squares,PlacedKnights,Max).
knights([],PlacedKnights,Max) :-
length(PlacedKnights,Max).
knights([(X,Y)|Squares],PlacedKnights,Max) :-
( is_attacked(X,Y,PlacedKnights) ->
knights(Squares,PlacedKnights,Max)
;
knights(Squares,[knight(X,Y)|PlacedKnights],Max1),
knights(Squares,PlacedKnights,Max2),
Max is max(Max1,Max2)
).
is_attacked(X,Y,PlacedKnights) :-
( NX is X - 1, NY is Y - 2
; NX is X - 1, NY is Y + 2
; NX is X + 1, NY is Y - 2
; NX is X + 1, NY is Y + 2
; NX is X - 2, NY is Y - 1
; NX is X - 2, NY is Y + 1
; NX is X + 2, NY is Y - 1
; NX is X + 2, NY is Y + 1
),
member(knight(NX,NY),PlacedKnights).