# Encoding nlp encoding

Name nlp encoding [Root]    Puzzles (51)    NumberSquares (4) Martin Gebser nlp encoding of Putting Numbers 2009-03-30 13:03 2008-11-29 00:10 No %% generate_number_square_normal.lp %% -- a normal logic program for creating number squares. %% First define the four possible directions of the numbers. The %% second and the third argument give the direction vector and they %% are used to make the following encoding more readable. dir(n, 0, 1). dir(e, 1, 0). dir(s, 0, -1). dir(w, -1, 0). %% Define a new atom for every different number in the input. num(N) :- number(N, Pos, B). %% Each different symbol may occur in any position of the grid: grid(X, Y, S) :- not not_grid(X, Y, S), square(X, Y), symbol(S). not_grid(X, Y, S) :- not grid(X, Y, S), square(X, Y), symbol(S). %% It is an error if a grid square contains two different values: :- grid(X, Y, S_1), grid(X, Y, S_2), square(X, Y), symbol(S_1), symbol(S_2), S_1 < S_2. %% Since we know the length of all input numbers, we don't want to %% search them from places where they do not fit in. A number doesn't %% fit in a position if it extends out of the square. impossible_place(N, X, Y, Dir) :- number(N, Pos, B_1), square(X, Y), dir(Dir, X_d, Y_d), not square(X + Pos * X_d, Y + Pos * Y_d). %% A square is a possible place for the number if it is not %% impossible. possible_place(N, X, Y, Dir) :- not impossible_place(N, X, Y, Dir), num(N), square(X, Y), dir(Dir, X_d, Y_d). %% Next, a number is at a place if it fits in there and all its digits %% are in the correct place: at(N, X, Y, Dir) :- ok_num(N, Pos, X, Y, Dir) : number(N, Pos, B), possible_place(N, X, Y, Dir). %% A the "Pos"th digit of the number is correct if it occurs in the %% grid at the correct position. ok_num(N, Pos, X, Y, Dir) :- number(N, Pos, B_1), possible_place(N, X, Y, Dir), grid(X + Pos * X_d, Y + Pos * Y_d, B_1), dir(Dir, X_d, Y_d). %% We have placed a number if it occurs somewhere: found(N) :- at(N, X, Y, Dir), possible_place(N, X, Y, Dir). %% It is an error if some number has not been found: :- num(N), not found(N).