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

Question

The game of Hex is played on an n × 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.

blac OKO O O bla Figure 1: An illustration of a Hex game in progress, with n 11 5. [10 pts] The game of Hex is played on an n x 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

For the game of Hex n x n (with n=11), we will use UNION-FIND approaches.

User defined SET structure wil be used.

struct set
{
   int data;   //Each cell number
   int color;    //0->Black 1->White
   struct set* parent;
}

Here each set-node will have a key value(or cell number).
There will be total n*n cells.
In this case, where n=11
=> n * n
=> 11 * 11
=> 121
Therefore, 0 to 120 cell numbers.

UNION operation to connect each new cell with one of the neighbouring cell if it has the same color.
FIND operation to check if two cells are in the same set. We will see if both the set-node have the same parent.
We will apply FIND operation on every added cell and one of the border same colored cell.[List of desired cells should be maintained from the start]

void UNION(set subsets[],set *x)
{
   set it;
   for(it=x->data.start();it!=x->data.end();it++)
   {
       if(it->color==x->color)
       {   x->parent = it;
           break;
       }
   }
   x->parent = -1;
}

bool FIND(set x)
{
   if(x->color == 0)
       return FIND_EL(x,black_list);
   else   return FIND_EL(x,white_list);
}

bool FIND_EL(set x,vector<int> list)
{
   int first_parent = findParent(x);
   for(int i=0;i<list.size();i++)
       int second_parent = findParent(list[i]);
      
   if(first_parent == second_parent)
       return true;
   return false;
}

int findParent(set x)
{
   if(x->parent == NULL)
       return x->data;
   findParent(x->parent);
}

So if the parents of two cells belong to the same set, they will have the same parent.
Initial desired list should be made.

All corner cell number should be added to the respective list.(If we start giving cell numbers from the left corner and to it spirally clockwise.)
0,1,2,3,4,5,6,7,8,9,10 --- Black_list
10,11,12,13,14,15,16,17,18,19,20 --- White_list
20,21,22,23,24,25,26,27,28,29,30 --- Black_list
30,31,32,33,34,35,36,37,38,39,0 --- White_list

Initial set-node declaration:
   set temp;
   temp->data = x (as entered by the user)
   temp->color = 0|1 (Black or white,according to user's turn)
   temp->parent = NULL;

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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