The game of Hex is played on an n times n board composed of hexagonal cells. Two

Question

The game of Hex is played on an n times n board composed of hexagonal cells. Two players take turns placing black and white stones on the cells (see Figure 1 for an illustration of a hex game in progress). If the upper left and lower right sides are connected to each other by a path of black stones, the black player wins. If the lower left and upper right sides are connected to each other by a path of white stones, the white player wins. Formalize the problem of detecting when one of the players has won and show how Union-Find can help with this problem. Provide some details as to the resulting running-time of your approach

Explanation / Answer

Solution:- The rules of Hex are simple.

i) Players take turns placing a piece of their color on an un occupied hexagon.

ii) The game is won when one player establishes an unbroken chain of his pieces connecting his sides of the board.

iii)The player to move 2nd has the chance of swapping colors, effectively stealing the first player's move.

Two pieces are said to be n-connected if they can be joined to form an unbeatable connection in n moves when considered in isolation.

Golden Rule in Hex is a player's position is only as good as the weakest link in his best connection across the board.

Play first in the centre, then seek to form on each of white sides a chain of seperated links that are either diagonal or vertical. If the black checks white vertically, white switch to diagonal play and if black checks white diagonally, white switch to vertical.

Once white succeed in joining your two sides with a disconnected chain on which each missing link is a double play, white cannot be blocked.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.