Hex

Photo by Brett Sayles from Pexels

I signed up for Google's Kickstart - an online coding competition. During the practice rounds this week, I came across a coding problem based on the board game - Hex. The objective of the problem is to determine the game state from the current state of pieces on the board. There can be one of three outcomes -

• Red wins
• Blue wins
• Impossible

I did not write any code to solve this but found it interesting enough to develop a solution.

The game involves two players, one red and the other blue, and a board with hexagonal positions. Each player takes turns placing their pieces on the board. The first player to form a path from across opposite sides of the board from their corresponding color wins.

My first (and only) impulse was to treat this as a graph and use a DFS algorithm. This would require picking a cell in the top row or leftmost column and finding a path to the opposite side. I would later learn in the Google analysis notes that this approach when dealing with a 2D array is a flood fill algorithm.

The game is called Hex because each cell on the board is hexagonal, and therefore this requires specific considerations when adapting any algorithm for the given input. Each cell has 2 possible tops, lefts, rights, and bottoms.

What I had not accounted for

Runtime

The DFS / Flood Fill algorithm will take O(N^2) to run for each player. However, this problem also requires checking if the current game state is "impossible." My understanding of impossible was that one player may have played out of turn, and as a result, there were more pieces on the board than possible. A naive piece count could take care of this. 

However, reading the Google analysis notes, I learned that it was also possible to think of this as the board was in a state where one player should have won in a previous move. In the image above, the blue player should have already won, but they appear to have won twice. To identify this with Flood Fill, we would have to remove a piece and check if the player would have won and repeat this for all play pieces. This increases the runtime to O(N^4) when utilizing the flood fill algorithm.

An Optimal Solution

Google's analysis notes recommended finding a path from the opposite corners of the board. It suggests starting at the bottom left corner and top right corner and working towards the opposite side for the blue player.

In the case of blue in figure a, our starting point is the first blue piece on the left side that is blue. We find a path with blue pieces that only go towards the right side. If there is no path in these directions, i.e., only red pieces in our way, we terminate the search. If there is a path, we will stop at the right side or top side. We repeat this process for the red player starting at the top left and bottom right. 

I was initially confused about whether this direction was towards the opposite corner. The following path shown in figure e can also be discovered - as long as we move towards the opposite side.

Handling the Impossible State

In figure b above, there are two exclusive paths. This is impossible because the player cannot win twice. To determine this, we need to identify whether the two paths share at least one piece. If they don't, the board is in an impossible state.

The runtime of finding a path in one direction is O(N^2). Since we are solving for 4 such paths - O(4*N^2), which is still O(N^2)