The game of Hex is said to have, as one of its inventors, the mathematician John Nash,

Question:

The game of Hex is said to have, as one of its inventors, the mathematician John Nash, who is the subject of the book and movie A Beautiful Mind. In this game, two players, one playing black and the other playing white, take turns placing stones of their respective colors on an n × n hexagonal grid. Once a stone is placed, it cannot be moved. The black player’s goal is to connect the top and bottom sides of the grid, and the white player’s goal is to connect the left and right sides of the grid, using stones of their respective colors. Two cells are considered connected if they share an edge and both have the same color stone. (See Figure 7.12.) Describe an efficient scheme where you can determine after each move whether black or white has just won a game of Hex.

Figure 7.12