Search Problems   RSS Feed
projecteuler.net

Hex

 Published on Saturday, 7th November 2026, 04:00 pm and solved by 18

Problem 1018

Hex is a game for two players who take turns alternately placing stones on the empty hexagonal cells of a diamond shaped board like the one shown here:

1018_hex_sin_small.png

The size of the board varies, but the $11 \times 11$ board seen in the figure is the most standard size.

The first player uses white stones, and the second player uses black stones. Once a stone is placed, it is never moved.

The first player wins the game by building a path of adjacent cells occupied by white stones that connects the two white sides of the board.
Similarly, the second player wins the game by building a path of adjacent cells occupied by black stones that connects the two black sides of the board.
The above figure shows a winning position of the second player. The stones forming the path are marked.

The game cannot end in a draw.

Let $H(N)$ be the number of different games that can be played on a $N \times N$ sized board. In other words, $H(N)$ is the number of possible sequences of moves until a player wins the game.

For example, $H(2)=24$, $H(3)=257760$, $H(4)=10663950528000$.

Find $H(11)$ and give your answer modulo $1\,000\,000\,007$.



Copied to Clipboard