# Existence of index-uniform Hashi puzzles

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

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.

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.

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:

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.

This room enforces that the two left-hand inputs add up to the right-hand input.

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:

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!

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:

• This brilliant! Hashi is Turing Complete :) Aug 6, 2021 at 15:29