computer algorithms The game of Hex is played on an n times

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.

Solution

import java.awt.*;

import javax.swing.*;

import java.awt.event.*;

public class hexgame

{

private hexgame() {

                                initGame();

                                createAndShowGUI();

                }

                public static void main(String[] args)

                {

                                SwingUtilities.invokeLater(new Runnable() {

                                                                public void run() {

                                                                new hexgame();

                                                                }

                                                                });

                }

                final static Color COLOURBACK = Color.WHITE;

                final static Color COLOURCELL = Color.ORANGE;               

                final static Color COLOURGRID = Color.BLACK;  

                final static Color COLOURONE = new Color(255,255,255,200);

                final static Color COLOURONETXT = Color.BLUE;

                final static Color COLOURTWO = new Color(0,0,0,200);

                final static Color COLOURTWOTXT = new Color(255,100,255);

                final static int EMPTY = 0;

                final static int BSIZE = 12;

                final static int HEXSIZE = 60;        

                final static int BORDERS = 15;

                final static int SCRSIZE = HEXSIZE * (BSIZE + 1) + BORDERS*3;

                int[][] board = new int[BSIZE][BSIZE];

                void initGame(){

                                hexmech.setXYasVertex(false);

                                hexmech.setHeight(HEXSIZE);

                                hexmech.setBorders(BORDERS);

                                for (int i=0;i<BSIZE;i++) {

                                                for (int j=0;j<BSIZE;j++) {

                                                                board[i][j]=EMPTY;

                                                }

                                }

                                board[3][3] = (int)\'A\';

                                board[4][3] = (int)\'Q\';

                                board[4][4] = -(int)\'B\';

                }

                private void createAndShowGUI()

                {

                                DrawingPanel panel = new DrawingPanel();

                                JFrame frame = new JFrame(\"Hex Testing 4\");

                                frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );

                                Container content = frame.getContentPane();

                                content.add(panel);

                               

                                frame.setSize( (int)(SCRSIZE/1.23), SCRSIZE);

                                frame.setResizable(false);

                                frame.setLocationRelativeTo( null );

                                frame.setVisible(true);

                }

                class DrawingPanel extends JPanel

                {                             

               

                                public DrawingPanel()

                                {             

                                                setBackground(COLOURBACK);

                                                MyMouseListener ml = new MyMouseListener();           

                                                addMouseListener(ml);

                                }

                                public void paintComponent(Graphics g)

                                {

                                                Graphics2D g2 = (Graphics2D)g;

                                                g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

                                                g.setFont(new Font(\"TimesRoman\", Font.PLAIN, 20));

                                                super.paintComponent(g2);

                                                for (int i=0;i<BSIZE;i++) {

                                                                for (int j=0;j<BSIZE;j++) {

                                                                                hexmech.drawHex(i,j,g2);

                                                                }

                                                }

                                                for (int i=0;i<BSIZE;i++) {

                                                                for (int j=0;j<BSIZE;j++) {                                                                             

                                                                               

                                                                                hexmech.fillHex(i,j,board[i][j],g2);

                                                                }

                                                }

                                               

                                }

                                class MyMouseListener extends MouseAdapter               {                                                              public void mouseClicked(MouseEvent e) {

                                                                int x = e.getX();

                                                                int y = e.getY();

                                                                Point p = new Point( hexmech.pxtoHex(e.getX(),e.getY()) );

                                                                if (p.x < 0 || p.y < 0 || p.x >= BSIZE || p.y >= BSIZE) return;

                                                                board[p.x][p.y] = (int)\'X\';

                                                                repaint();

                                                }                             

                                }

                }

}