7
$\begingroup$

On the left, we have a starting configuration for a game of Hashi, and on the right, its solution:

Hashi

That is to say, the goal is to make connections (planar, and traveling only in cardinal directions) from each node such that the total number of connections at each node is in accordance with the node's index, and such that the final graph is connected. You can play around with it here. Note: In this version, only 0, 1, or 2 connections are possible between two nodes, but for the purposes of this question, there may be an arbitrary number of connections between two nodes!

Problem statement: For each integer n > 1, does there exist a nontrivial Hashi puzzle (with a unique solution) using only index-n nodes? "Nontrivial" simply means to exclude the configuration consisting of two adjacent nodes, whose unique solution is an n-fold connection between them. For example, for n=2, any (properly embedded) cycle graph is nontrivial and uniquely solvable.

$\endgroup$
9
$\begingroup$

I claim the answer is

yes

and here's why:

To start, I will be using "walls" to block off connections between two islands. This does not make any new things possible - a walled puzzle can be converted to a wall-less one by shifting the circles parallel to the wall.

For instance, here is a "walled Hashi puzzle" - the blue line is a wall that bridges are not allowed to cross.
hashi puzzle made in puzz.link, with a vertical blue line drawn between two circles
Example taken from janko.at.

We can convert it to a wall-less puzzle by shifting the two sides of the wall in opposite directions:
the same as the above, but moving the region left of the blue line upward slightly, and moving the region right of it downward slightly

And now we have an equivalent puzzle.

So, I will be allowing these walls, since we can easily remove them. Now for the actual proof:

Using the walls, I will construct a Hashi puzzle out of separate "rooms" that do arithmetic on their bridges.
enter image description here
This room enforces that the two left-hand inputs add up to the right-hand input.

enter image description here
And this room enforces that x has the same parity as n, since we need x+a+a=n. Additionally, x must be at least 1, or otherwise we break connectivity.

So, with these tools, we can construct the puzzle!


The strategy is this: Take a bunch of the one-exit rooms, and add them together to make a single node. For instance, here's the puzzle for n=5:

enter image description here
The five rooms along the bottom (along with connectivity) enforce that a, b, c, d, and e are all at least 1. And the lonely node in the top right enforces that they add up to 5. So they must all be 1, and we have our unique solution!

n=5 solution

This is the way the "odd n" puzzles work. For even n, the bottom rooms require two incoming connections instead -- so you only need half of the number of rooms. (In fact, the puzzle for n=10 is exactly the same as the puzzle for n=5, and its solution is the same thing but doubled!)

And for completeness' sake, here is the (solved) puzzle for n=5, but unwalled to meet the rules of the original problem:

enter image description here

$\endgroup$
1
  • $\begingroup$ This brilliant! Hashi is Turing Complete :) $\endgroup$ Aug 6 '21 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.