"Squares" Logic Riddle Solution in Prolog

Question

"Squares"

Input:

Board size m × n (m, n ∈ {1,...,32}), list of triples (i, j, k), where i ∈ {1,...,m}, j ∈ {1,...,n}, k ∈ {0,...,(n-2)·(m-2)}) describing fields with numbers.

Output:

List of triples (i, j, d) showing solved riddle. Triple (i, j, d) describes square with opposite vertices at coordinates (i, j) and (i+d, j+d).

Example:

Input:

7. 7. [(3,3,0), (3,5,0), (4,4,1), (5,1,0), (6,6,3)].

Output:

[(1,1,2), (1,5,2), (2,2,4), (5,1,2), (4,4,3)]

Image:

Explanation:

I have to find placement for x squares(x = fields with numbers). On the circuit of the each square, exactly at one of his corners should be only one digit equal to amount of digits inside the square. Sides of squares can't cover each other, same as corners. Square lines are "filling fields" so (0,0,1) square fills 4 fields and have 0 fields inside.

I need a little help coding solution to this riddle in Prolog. Could someone direct me in the right direction? What predicates, rules I should use.

Answer 1

Since Naimads life is worth saving(!), here is some more directive help.

Programmers tend to work out their projects either in bottomp-up (starting from "lower" levels of functionality, building up to a complete application) or top-down (starting with a high level "shell" of functionality that provides input/output, but with the solution processing stubbed in for later refinement).

Either way I can recommend an approach for Prolog progrmming that has been championed by the Ruby programming community: Test Driven Development.

Let's pick a couple of functional requirement, one high and one low, and discuss how this bit of philosophy might help.

The high level predicate in Prolog is one which takes all the input and output arguments and semantically defines the problem. Note that we can write down such a predicate without giving any care as to how the solution process will get implemented:

/* squaresRiddle/4 takes inputs of Height and Width of a "board" with
   a list of (nonnegative) integers located at cells of the board, and
   produces a corresponding list of squares having one corner at each
   of those locations "boxing in" exactly the specified counts of them
   in their interiors.  No edges can overlap nor corners coincide.  */
squaresRiddle(Height,Width,BoxedCountList, OutputSquaresList).

So far we have just framed the problem. The useful progress is given by the comment (clearly defining the inputs and outputs at a high level), and the code at this point just guarantees "success" with whatever arguments are passed. So a "test" of this code:

?= squaresRiddle(7,7,ListIn,ListOut).

won't produce anything except free variables.

Next let's give some thought to how the input list and output list ought to be represented. In the Question it is proposed to use triples of integers as entries of these lists. I would recommend instead using a named functor, because the semantics of those input triples (giving an x,y coordinate of a cell with a count) are subtly different from that of the output triples (giving an x,y coordinate of upper left corner and an "extent" (height&width) of the square). Note in particular that an output square may be described by a different corner than the one in the corresponding input item, although the one in the input item needs to be one of the four corners of the output square.

So it tends to make the code more readable if these constructs are distinguished by simple functor names, e.g. BoxedCountList = [box(3,3,0),box(3,5,0),box(4,4,1),box(5,1,0),box(6,6,3)] vs. OutputSquaresList = [sqr(1,1,2), sqr(1,5,2), sqr(2,2,4), sqr(5,1,2), sqr(4,4,3)].

Let's give a little thought to how the search for solutions will proceed. The output items are in 1-to-1 correspondence with the input items, so the lists will have equal length in the end. However choosing the kth output item depends not only on the kth input item, but on all the input items (since we count how many are in the interior of the output square) and on the preceding output items (since we disallow corners that meet and edges that overlap).

There are several ways to manage the flow of decision making consistent with this requirement, and it seems to be the crux of this exercise to pick one approach and make it work. If you are familiar with difference lists or accumulators, you have a head start on ways to do it.

Now let's switch to discussing some lower level functionality. Given an input box there are potentially a number of output sqr that could correspond to it. Given a positive "extent" for the output, the X,Y coordinates of the input can be met with any of the four corners of the output square. While more checking is required to verify the solution, this aspect seems a good place to start testing:

/* check that coordinates X,Y are indeed a corner of candidate square */
hasCorner(sqr(SX,SY,Extent),X,Y) :-
    (SX is X ; SX is X + Extent),
    (SY is Y ; SY is Y + Extent).

How would we make use of this test? Well we could generate all possible squares (possibly limiting ourselves to those that fit inside the height and width of our "board"), and then check whether any have the required corner. This might be fairly inefficient. A better way (as far as efficiency goes) would use the corner to generate possible squares (by extending from the corner by Extent in any of four directions) subject to the parameters of board size. Implementation of this "optimization" is left as an exercise for the reader.