Consider the game of Hex, as in the previous exercise, but now with a twist. Suppose some

Question:

Consider the game of Hex, as in the previous exercise, but now with a twist. Suppose some number, k, of the cells in the game board are colored gold and if the set of stones that connect the two sides of a winning player’s board are also connected to k ≤ k of the gold cells, then that player gets k' bonus points.

Describe an efficient way to detect when a player wins and also, at that same moment, determine how many bonus points they get. What is the running time of your method over the course of a game consisting of n moves?

Data From Previous Exercise

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