Focus on a Puzzle: There Is No Spoon – Episode 2

There Is No Spoon – Episode 2 is one of my favorite puzzles on CodinGame. It consists of solving a game of Hashiwokakero. It requires a slightly different approach than for standard graph games. Solving it requires using two clever search algorithms. In this article, I will explain how I solved the puzzle.

Rules of a Hashiwokakero GameClose rules

Some Puzzling Vocabulary

Before I start, here is a list of some terms which I am going to use:

• Power of a node: the amount of links a node should have with neighboring nodes (1 to 8)
• Bridge: a connection of 1 or 2 links between 2 nodes
• Power of a bridge: the amount of links in a bridge (1 or 2)
• Saturation of a link: a node is considered saturated once all bridges connected to it have been built.

Interpretation of the Grid

The set of nodes can be represented in a number of ways. Here below is what I did.

I created a class “Node” which stores the following information:

• Its power
• The indexes of the neighbouring nodes in all directions (Up, Down, Left and Right)
• The number of bridges connecting the neighbouring nodes

I also created a class “Grid,” which contains the list of bridges currently built, and the list of all nodes.

Helpful Functions

Before getting started with the 2 pivotal search algorithms, I first coded some fundamental methods to help me simplify the resolution of the puzzle:

The “Valid” Function

This function checks if the current grid’s state is valid and returns a boolean. There are two things to check to ensure that a grid is in a valid state.

First, it checks if a node is isolated. As the rules state, the links must connect all the nodes into a single connected group.

In the example below, no additional bridge can connect one of the 2 nodes. It means that these two nodes are isolated, which is against the rules.

2 = 2

The “Valid” function also checks if the sum of links that can connect a node is inferior or equal to its power.

In the example below, only 4 bridges of power 1 can connect the central node. However, its power is 5, so there should theoretically be one more link connected to it. As all the neighbouring nodes are saturated, the grid’s state is faulty.

. . 1 . .
. . | . .
1 - 5 - 1
. . | . .
. . 1 . .

The “Draw” Function

The “Draw” function creates a bridge of given power (1 or 2) between 2 nodes. It then updates the power of both nodes and their possible bridges as well as links that the bridge made impossible.

For example, consider the following sub-grid where you’ve just drawn a vertical link:

. 1 .
1 | 1
. 1 .

The left neighbour of the node on the right becomes -1 (which means no neighbor), as the link prevents any drawing of a bridge across another bridge. As the rules state, the links must not cross any other links.

The “Clone” Function

As indicated by its name, this function clones the current grid’s state. When running the search algorithm, your code will explore different possible states of the grid. Some of the states will be invalid; if you didn’t clone the initial grid’s state and only modified it, you’ll have a hard time retrieving it.

The “Revert” Function

As I explained above, you need to be able to retrieve the last valid grid’s state you explored in case you run into an invalid state. As indicated by its name, the “Revert” function reverts the current grid’s state to the last valid grid state.

The Intersection Search

In short, the intersection search looks for bridges that are 100% sure.

Some examples will help you understand what I mean by a 100% sure bridge.

Here below, the node at the top left has only 1 neighbor, so there must be a bridge connecting the two.

1 . 2        1 - 2
 . . .   ->   . . . 
. . 1        . . 1

In the next example, the node at the top left has 2 neighbors (down and on the right), so a solution must connect the node to both neighbors with a bridge of power 1. Indeed, the only solution for a node of power 3 with 2 neighbors is to connect one neighbor with a bridge of power 2 and connect the other with a bridge of power 1. Which means having at least 2 bridges of power 1!

3 . 2        3 - 2
. . .   ->   | . .
2 . 1        2 . 1

In this third example, the node of power 5 has 3 neighbors. Using the same reasoning as above, a solution for this node must connect 2 neighbors with bridges of power 2, and connect the last neighbor with a bridge of power 1. Thus, in all directions, there will be a bridge with at least a power of 1.

2 . .        2 . .
. . .        | . .
5 . 2   ->   5 - 2
. . .        | . .
2 . 1        2 . 1

From the three examples above, you have probably guessed the conditions that make a possible bridge 100% sure. It happens when all possible configurations around a node necessarily include a bridge in every (valid) direction.

Here’s a simple formula which helped me determine 100% sure bridges:

Let S be the maximum number of bridges a node can have with its neighbors (basically the maximum power of such a bridge is the maximum between this neighbor’s power and 2), and let N represent the power of the node. (S >= N in a valid grid)

Let p be the maximum power of a bridge radiating from this node in a particular direction d (1 or 2).

Then I defined “magicVal” as:

magicVal = N - S + p

If magicVal is strictly superior to 0, it means a bridge of power equal to magicVal can be built in the direction d.

In the last example above, the magicVal of the node of power 5 in the right direction is 5-5+1=1.

I used this simple formula for each node and for all directions.

Of course, my algorithm could be slightly optimized (if I check the left neighbour node b of a node a, then I don’t need to check the right neighbour of node a). The intersection search runs as long as any sure bridge can be built. After this search, I need to use the elimination search.

The Elimination Search

Run out of sure moves? Don’t fear, the elimination search is here! Very frequently, the intersection search will only make a few moves and then stop. What should you do then? The answer is simple: use what you always do when you run out of good algorithms – BRUTE FORCE! 😊

You have to make an assumption: connect two nodes with a link and assume it’s a correct move.

Then you keep on running the intersection search. Remember to copy the grid before making an assumption, as you may make a wrong assumption and then lose the progress you made in your search of a working solution.

Once you make an assumption, a new grid is created and needs to be checked with the intersection search. This is where the valid method comes into action. After an assumption, during an iteration of the intersection search, the grid may become invalid. As soon as it becomes invalid, revert the grid to its cloned state, and update the assumption as incorrect (make something like an “anti-draw” function).

If the intersection search does not invalidate the created grid and all the nodes have not been saturated, another assumption needs to be made. For the grid state to be invalidated, all possible assumptions from this grid must be wrong.

At some point, you should obtain a complete grid with all nodes saturated. If this last grid state is valid, you have found a solution!

Possible Hindrances

• When drawing a bridge, don’t forget to update the values related to the two nodes of the bridge.
• When drawing a bridge connecting a node of power 2, the maximum power of possible bridges radiating from this node in all other directions becomes 1.
• If a node becomes saturated, there can’t be any additional links radiating from it in any direction.
• The solution is supposed to be HUGE, so there is room for a lot of errors. I therefore suggest you implement the solution one step at a time. First, make sure the intersection search is 100% complete before moving on to coding the elimination search.

Summing Up…

That’s it! I’ve broken up the puzzle There Is No Spoon – Episode 2 into 4 simple parts. Quite a bunch of code, but relatively easy to implement! I haven’t shared a single line of code, which you may find frustrating; but hey, I just told you everything you need to be able to solve it! The implementation is up to you…

Good luck!

---

Solve There Is No Spoon Ep. 2