Hashi Puzzle Representation to solve all solutions with Prolog Restrictions

Question

Im trying to write a prolog program that receives a representation of an unsolved Hashi board and answers all the possible solutions, using restrictions. Im having an hard time figuring out which is the best (or a very good) way of representing the board with the bridges and without. The program is supposed to draw the boards for an easy reading of the solutions.

board(
       [[3, 0, 6, 0, 0, 0, 6, 0, 3],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [2, 0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 3, 0, 0, 2, 0, 0, 0],
        [0, 3, 0, 0, 0, 0, 4, 0, 1]]
    ).

For example, this representation is only good without the bridges, since it holds no info about them. The drawing of this board would be basicly turning the 0's into spaces, and the board would be drawn like this:

3   6       6   3 

  1               

2         1       


1   3     2       
  3         4   1 

which is a decent representation of a real hashi board.

The point now is to be able to draw the same thing, but also draw bridges if there's any. I must be able to do so before i even think of making the restrictions themselves, since going at it with a bad way of representation will make my job alot more difficult.

I started thinking of solutions like this:

if every element of the board would be a list:

[NumberOfConnections, [ListOfConnections]]

but this gives me no info for the drawing, and what would the list of connections really have?

maybe this:

[Index, NumberOfConnections, [ListOfIndex]]

this way every "island" would have a unique ID and the list of connections would have ids but drawing still sounds kinda hard, in the end the bridges can only be horizontal or vertical

Anyway, anyone can think of a better way of representation that makes it the easiest to achive the final goal of the program?

Answer 1

Nice puzzle, I agree. Here is a half-way solution in ECLiPSe, a Prolog dialect with constraints (http://eclipseclp.org).

The idea is to have, for every field of the board, four variables N, E, S, W (for North, East, etc) that can take values 0..2 and represent the number of connections on that edge of the field. For the node-fields, these connections must sum up to the given number. For the empty fields, the connections must go through (N=S, E=W) and not cross (N=S=0 or E=W=0).

Your example solves correctly:

?- hashi(stackoverflow).
3 = 6 = = = 6 = 3 
|   X       X   | 
| 1 X       X   | 
| | X       X   | 
2 | X     1 X   | 
| | X     | X   | 
| | X     | X   | 
1 | 3 - - 2 X   | 
  3 = = = = 4   1 

but the wikipedia one doesn't, because there is no connectedness constraint yet!

:- lib(ic).  % uses the integer constraint library

hashi(Name) :-
        board(Name, Board),
        dim(Board, [Imax,Jmax]),
        dim(NESW, [Imax,Jmax,4]),   % 4 variables N,E,S,W for each field
        ( foreachindex([I,J],Board), param(Board,NESW,Imax,Jmax) do
            Sum is Board[I,J],
            N is NESW[I,J,1],
            E is NESW[I,J,2],
            S is NESW[I,J,3],
            W is NESW[I,J,4],
            ( I > 1    -> N #= NESW[I-1,J,3] ; N = 0 ),
            ( I < Imax -> S #= NESW[I+1,J,1] ; S = 0 ),
            ( J > 1    -> W #= NESW[I,J-1,2] ; W = 0 ),
            ( J < Jmax -> E #= NESW[I,J+1,4] ; E = 0 ),
            ( Sum > 0 ->
                [N,E,S,W] #:: 0..2,
                N+E+S+W #= Sum
            ;
                N = S, E = W,
                (N #= 0) or (E #= 0)
            )
        ),

        % find a solution
        labeling(NESW),
        print_board(Board, NESW).


print_board(Board, NESW) :-
        ( foreachindex([I,J],Board), param(Board,NESW) do
            ( J > 1 -> true ; nl ),
            Sum is Board[I,J],
            ( Sum > 0 ->
                write(Sum)
            ; 
                NS is NESW[I,J,1],
                EW is NESW[I,J,2],
                symbol(NS, EW, Char),
                write(Char)
            ),
            write(' ')
        ),
        nl.

symbol(0, 0, ' ').
symbol(0, 1, '-').
symbol(0, 2, '=').
symbol(1, 0, '|').
symbol(2, 0, 'X').


% Examples

board(stackoverflow,
     []([](3, 0, 6, 0, 0, 0, 6, 0, 3),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0),
        [](0, 1, 0, 0, 0, 0, 0, 0, 0),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0),
        [](2, 0, 0, 0, 0, 1, 0, 0, 0),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0),
        [](1, 0, 3, 0, 0, 2, 0, 0, 0),
        [](0, 3, 0, 0, 0, 0, 4, 0, 1))
    ).
board(wikipedia,
     []([](2, 0, 4, 0, 3, 0, 1, 0, 2, 0, 0, 1, 0),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 1),
        [](0, 0, 0, 0, 2, 0, 3, 0, 2, 0, 0, 0, 0),
        [](2, 0, 3, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0),
        [](0, 0, 0, 0, 2, 0, 5, 0, 3, 0, 4, 0, 0),
        [](1, 0, 5, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0),
        [](0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 4, 0, 2),
        [](0, 0, 4, 0, 4, 0, 0, 3, 0, 0, 0, 3, 0),
        [](0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
        [](2, 0, 2, 0, 3, 0, 0, 0, 3, 0, 2, 0, 3),
        [](0, 0, 0, 0, 0, 2, 0, 4, 0, 4, 0, 3, 0),
        [](0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0),
        [](3, 0, 0, 0, 0, 3, 0, 1, 0, 2, 0, 0, 2))
    ).

Answer 2

What a cool puzzle! I did a few myself, and I don't see an obvious way to make solving them deterministic, which is a nice property for a puzzle to have. Games like Tetris derive much of their ongoing play value from the fact that you don't get bored--even a good strategy can continually be refined. This has a practical ramification: if I were coding this, I would spend no further time trying to find a deterministic algorithm. I would instead focus on the generate/test paradigm Prolog excels at.

If you know you're going to do generate-and-test, you know already where all your effort at optimization is going to go: making your generator more intelligent (so it generates better candidates) and making your test fast. So I'm looking at your board representation and I'm asking myself: is it going to be easy and fast to generate alternatives from this? And we both know the answer is no, for several reasons:

• Finding alternative islands to connect to from any particular island is going to be highly inefficient: searching a list forward and backward and then indexing all the other lists by the current offset. This is a huge amount of list finagling, which won't be cheap.

• Detecting and preventing a bridge crossing is going to be interesting.

• More to the point, the proper way to encode bridges is not obvious with this design. Islands can be separated by great distances--are you going to put a 0/1/2 in every connecting cell? If so, you have a data duplication problem; if not, you're going to have some fun calculating which location should hold the bridge count.

• It's just an intuition, but having a heterogeneous data structure like this where the "kind" of element is determined entirely by whether the indices are odd or even, strikes me as unwelcome.

I think what you've got for the board layout is a great input format, but I don't think it's going to serve you well as an intermediate representation. The game is clearly a graph problem. This suggests one of the two classic graph data structures might be more helpful: the adjacency list, or the edge matrix. Either of these will expedite choosing alternatives for bridge layout, but it's not obvious to me (maybe to someone who does more graph theory) how one would prevent bridge crossings. Ideally, your data structure would simply prevent bridge crossings from occurring. Next best would be preventing the generator from generating candidate solutions with bridge crossings; worst would be to simply fail them at the test stage.

Answer 3

For drawing bridges, you could use ASCII 179 for single vertical bridges, 186 for double vertical bridges, 196 for single horizontal bridges, and 205 for double horizontal bridges. This depends on which extended ASCII set is in use, though. It works in the most common.

---

For internal representation, I'd use -1 and -2 for single and double bridges in one direction, and -3 and -4 in the other. You could use just about any symbol that isn't 0-8, but this has the added benefit of simply adding the bridges to the island (converting (-3, -4) to (-1, -2)) to check the solution. If the sum is 0, that island is solved.