prolog, knight attack

Question

I have one-dimensional array which means chess table. I would like to find all positions which knight could attack. For example, have 3x3 chess table (K is Knight, X is attack position):

---------------
| X |    |    |
---------------
|    |    | K |
---------------
| X |    |    |
---------------

and for this table, in prolog program I would like to have array:

-------------------------------------
| X |   |   |   |   | K | X |   |   |
-------------------------------------

I want to write universal program for all cases - 3x3 table, 4x4, 5x5, etc.

I tried:

control(Table, N, Pos, NewTable) :- insert(Table, Pos, 'k' , TempTable1, 1),
                     insert(TempTable1, Pos-N*2+1, 'x' , TempTable2, 1),
                     insert(TempTable2, Pos-N*2-1, 'x' , TempTable3, 1),
                     insert(TempTable3, Pos-N  +2, 'x' , TempTable4, 1),
                     insert(TempTable4, Pos-N  -2, 'x' , TempTable5, 1),
                     insert(TempTable5, Pos+N*2+1, 'x' , TempTable6, 1),
                     insert(TempTable6, Pos+N*2-1, 'x' , TempTable7, 1),
                     insert(TempTable7, Pos+N  +2, 'x' , TempTable8, 1),
                     insert(TempTable8, Pos+N  -2, 'x' , NewTable,   1).

There N - is table size (3), Pos - knight position. The "insert" is OK, but "control" doesn't work correctly:

?- control([0,0,0,0,0,0,0,0,0], 3, 6, R).
R = [x, 0, 0, 0, x, k, x, 0, 0].

should be R = [x, 0, 0, 0, 0, k, x, 0, 0].

Any ideas, how to change "control" predicate?

Answer 1

Remove inserts until the rogue x disappears. That should tell you where the problem is.

EDIT: Ah-ha! It should have occurred to me before. You are not clipping knight moves when they go pass the left or right edge of the board, so the knight moves up to the top rank, then two to the right, which wraps around to the middle rank and plonks the knight right next to its starting position. insert can only clip top and bottom because it only sees an array; it doesn't know how wide the board is.

Answer 2

I will agree with Arian. It really seems much easier to use two coordinates. But if you really want to keep everything as it is, I have come up with something that seems like a solution.

You didn't write anything about your insert/5 predicate, so I will assume you have this:

insert(A, Pos, H, A, X) :-
    Pos < 1,
    !.
insert([], Pos, H, [], N) :-
    !.
insert([H1|T1], Pos, H, [H|T1], N) :-
    N =:= Pos,
    !.
insert([H1|T1], Pos, H, [H1|T2], N) :-
    N < Pos,
    N2 is N + 1,
    insert(T1, Pos, H, T2, N2).

To help with coordinates, I wrote a predicate that tells you row and a column of a position:

getposition(Size, Pos, Row, Column) :-
    First is truncate(Pos / Size),
    (Pos mod Size > 0,!,Row is First + 1;Row is First),
    Second is Pos - First * Size,
    (Second =:= 0,!,Column is Size;Column is Second).

This way you can get row+column of the knight, calculate row+column of new attack position and compare them. If it is correct - you insert, if not correct - you ignore insert.

control(Table, N, Pos, NewTable) :-
    insert(Table, Pos, 'k' , TempTable1, 1),
    getposition(N, Pos, Row1, Column1),

    getposition(N, Pos-N*2+1,RowA, ColumnA),
    (RowA =:= Row1 - 2, ColumnA =:= Column1 + 1,!,
    insert(TempTable1, Pos-N*2+1, 'x' , TempTable2, 1);TempTable2 = TempTable1),    

    getposition(N, Pos-N*2-1,RowB, ColumnB),
    (RowB =:= Row1 - 2, ColumnB =:= Column1 - 1,!,
    insert(TempTable2, Pos-N*2-1, 'x' , TempTable3, 1);TempTable3 = TempTable2),

    getposition(N, Pos-N + 2,RowC, ColumnC),
    (RowC =:= Row1 - 1, ColumnC =:= Column1 + 2,!,
    insert(TempTable3, Pos-N  +2, 'x' , TempTable4, 1);TempTable4 = TempTable3),

    getposition(N, Pos-N - 2,RowD, ColumnD),    
    (RowD =:= Row1 - 1, ColumnD =:= Column1 - 2,!,
    insert(TempTable4, Pos-N  -2, 'x' , TempTable5, 1); TempTable5 = TempTable4),

    getposition(N, Pos+N*2+1,RowE, ColumnE),
    (RowE =:= Row1 + 2, ColumnE =:= Column1 + 1,!,
    insert(TempTable5, Pos+N*2+1, 'x' , TempTable6, 1); TempTable6 = TempTable5),

    getposition(N, Pos+N*2-1,RowF, ColumnF),    
    (RowF =:= Row1 + 2, ColumnF =:= Column1 - 1,!,
    insert(TempTable6, Pos+N*2-1, 'x' , TempTable7, 1); TempTable7 = TempTable6),

    getposition(N, Pos+N + 2,RowG, ColumnG),
    (RowG =:= Row1 + 1, ColumnG =:= Column1 + 2,!,
    insert(TempTable7, Pos+N  +2, 'x' , TempTable8, 1); TempTable8 = TempTable7),

    getposition(N, Pos+N - 2,RowH, ColumnH),
    (RowH =:= Row1 + 1, ColumnH =:= Column1 - 2,!,
    insert(TempTable8, Pos+N  -2, 'x' , NewTable,   1); NewTable = TempTable8).

This is probably not the best solution, as it is cumbersome and my prolog skills are limited, but at least it works!

?- control([0,0,0,0,0,0,0,0,0], 3, 6, R).
R = [x, 0, 0, 0, 0, k, x, 0, 0].

?- control([0,0,0,0,0,0,0,0,0], 3, 5, R).
R = [0, 0, 0, 0, k, 0, 0, 0, 0].

Answer 3

a different approach would be doing something like this:

knight_in_range(X,Y):-
    knight_move(X,Y,Xn,Yn),
    knight(Xn,Yn).

%writing manually all the pairs is kinda boring
knight_move(X,Y,Xn,Yn):-
    alter(Ax),
    alter(Ay,Ax),
    Yn is Y+Ay,
    Xn is X+Ax.

alter(Ax):-
    member(Ax,[1,2,-1,-2]).
alter(Ay,Ax):-
    Ay is 2/Ax.
alter(Ay,Ax):-
    Ay is -2/Ax.

to get the list you simply ask if each square is under attack or not.
while it should take more time for this specific application i think it's a bit less messy xd also, if you have the nxn solution you can easily/fast get the (n+1)x(n+1)