:- dynamic gridsize/2.

generate(N, Out) :-
    Size is N*N,

    retractall(gridsize(_,_)),
    assertz(gridsize(N,N)),

    length(Out, Size).

coordsToIndex(X, Y, Index) :-
    gridsize(Width, _),
    Index is Y*Width+X.

indexToCoords(Index, X, Y) :-
    gridsize(Width,_),

    Y is (Index div Width),
    X is (Index mod Width).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

put(Grid, Index) :-
    nth0(Index, Grid, h).

work(_, _, 0) :- !.
work(_, -1, _) :- !, fail.

work(Grid, Index, Remaining) :-
    NewIndex is Index - 1,
    NewRem is Remaining - 1,

    (
        (
            check(Grid, Index),
            put(Grid, Index),
            work(Grid, NewIndex, NewRem)
        );
        work(Grid, NewIndex, Remaining)
    ).



%%%%%%%%%%%%%%%%%%%%%%%%%%

check(Grid, Index) :-
    indexToCoords(Index, X, Y),

    findall(I, (
        nth0(I, Grid, H), nonvar(H),
        indexToCoords(I, IX, IY),

        (
            IX = X;
            IY = Y;
            (abs(IX-X, O), abs(IY-Y, O))
        )
    ), All),

    length(All, 0).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

run(N, Out) :-
    S is N*N - 1,
    generate(N, Out),
    work(Out, S, N).