Search code examples
javaalgorithmswing2dpath-finding

Algorithm for pathfinding in 2D Array


I would like to know how to find the path from a cell passing through all cells which have same value back to the starting cell. By value here I mean either Token.CERCLE_ROUGE or Token.CERCLE_BLEU

Consider cell(4,5) == Token.CERCLE_BLEU and has neighbors: 3,4 - 4,4 - 5,4 - 3,5 - 5,5 - 3,6 - 4,6 - 5,6 all of them == Token.CERCLE_ROUGE

Now we have cell(3,4) as starting point: how one can find a path passing through (4,4), (5,4), (3,5), (5,5), (3,6), (4,6), (5,6) then back to (3,4). Here we can draw a line segment passing from cell to cell so that cell(4,5) will be in the center. (See the image below)

The idea here is to "capture" opponent's token, that's how a player gains points.

enter image description here

I'll update with any information if needed.

Update:

I found a pathfinding utility that I think can solve this, but I have no idea how to implement it: https://gist.github.com/benruijl/3385624

Below is my code:

This enum class represents a cell state:

 public enum Token {
        VIDE, CERCLE_BLEU, CERCLE_ROUGE
    }

I use the code below to check for neighbors of a cell:

 public void neighbours(int  row, int col) {

    for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1  ) {

        for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1  ) {

            if(!((colNum == col) && (rowNum == row))) {

                if(withinGrid (rowNum, colNum )) {

                   System.out.println("Neighbor of "+ row + " " + col + " is " + rowNum +" " + colNum +
                    " Contains "+ board[rowNum][colNum]);

                }
            }
        }
    }
}
private boolean withinGrid(int colNum, int rowNum) {

    if((colNum < 0) || (rowNum <0) ) {
        return false;
    }
    if((colNum >= COLS) || (rowNum >= ROWS)) {
        return false;
    }
    return true;
}

My whole code is below. I'm not yet able to adapt it to MVC, the attempts I made seems not to work so far.

import javax.swing.JFrame;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import javax.swing.*;


public final class Pha extends JFrame {

    public static int ROWS = 15;
    public static int COLS = ROWS;


    public static int cellSize = 15; 
    public static int canvasWidth = cellSize * COLS + (ROWS *4) ;
    public static int canvasHeight = cellSize * ROWS ; 
    public static int gridWidth = 1; 
    public static int halfGridWidth = gridWidth / 2;

    public static int cellPadding = cellSize / 5;
    public static int symbolSize = cellSize - cellPadding * 2; 
    public static int symbolStrokeWidth = 3; 

    public enum GameState{
        JOUE, NUL, CERCLE_ROUGE_GAGNE, CERCLE_BLEU_GAGNE
    }

    private GameState actualState;

    public enum Token{
        VIDE, CERCLE_ROUGE, CERCLE_BLEU
    }

    private Token actualPlayer;

    private Token[][] board;
    private final DrawCanvas canvas; 
    private JLabel statusBar; 

    public Pha(){

        canvas = new DrawCanvas(); 
        canvas.setPreferredSize(new Dimension(canvasWidth, canvasHeight));


        canvas.addMouseListener(new MouseAdapter() {
        @Override
        public void mouseClicked(MouseEvent e) { 
        int x = e.getX();
        int y = e.getY();

        int selectedRow = y / cellSize;
        int selectedCol;
            selectedCol = x / cellSize;


        if(actualState == GameState.JOUE){
            if(selectedRow >= 0 && selectedRow < ROWS && selectedCol >= 0
                    && selectedCol < COLS &&
                    board[selectedRow][selectedCol] == Token.VIDE){
                board[selectedRow][selectedCol] = actualPlayer; 
                updateGame(actualPlayer, selectedRow, selectedCol); 
                actualPlayer = (actualPlayer == Token.CERCLE_BLEU)? Token.CERCLE_ROUGE : Token.CERCLE_BLEU;

                neighbours(selectedRow, selectedCol);
            }
        } else { 
            initGame(); 
        }

        repaint();
    }

  });

    statusBar = new JLabel("  ");
    statusBar.setFont(new Font(Font.DIALOG_INPUT, Font.ITALIC, 15));
    statusBar.setBorder(BorderFactory.createEmptyBorder(2, 5, 4, 5));

    Container cp = getContentPane();
    cp.setLayout(new BorderLayout());
    cp.add(canvas, BorderLayout.EAST);
    cp.add(statusBar, BorderLayout.NORTH);

    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    pack(); 
    setTitle("Pha par esQmo");
    setVisible(true); 

    board = new Token[ROWS][COLS]; 
    initGame();   
}

    public void initGame(){
        for(int ligne = 0; ligne < ROWS; ++ligne){
            for(int colonne = 0; colonne < COLS; ++colonne){
                board[ligne][colonne] = Token.VIDE; 
            }
        }
        actualState = GameState.JOUE;
        actualPlayer = Token.CERCLE_ROUGE;
    }

    public void updateGame(Token theSeed, int ligneSelectionnee, int colonneSelectionnee) {
      if (aGagne(theSeed, ligneSelectionnee, colonneSelectionnee)) {  
         actualState= (theSeed == Token.CERCLE_ROUGE) ? GameState.CERCLE_ROUGE_GAGNE : GameState.CERCLE_BLEU_GAGNE;
      } else if (estNul()) { 
         actualState = GameState.CERCLE_BLEU_GAGNE;       
      }

   }
 public boolean estNul() {
      /*for (int row = 0; row < ROWS; ++row) {
         for (int col = 0; col < COLS; ++col) {
            if (board[row][col] == Token.VIDE) {
               return false; 
            }
         }
      }*/
      return false; 
   }

   public boolean aGagne(Token token, int ligneSelectionnee, int colonneSelectionnee) {
      return false; 

}


   public void neighbours(int  row, int col) {

    for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1  ) {

        for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1  ) {

            if(!((colNum == col) && (rowNum == row))) {

                if(withinGrid (rowNum, colNum )) {

                    System.out.println("Neighbor of "+ row + " " + col + " is " + rowNum +" " + colNum );

                }
            }
        }
    }
}

private boolean withinGrid(int colNum, int rowNum) {

    if((colNum < 0) || (rowNum <0) ) {
        return false;
    }
    if((colNum >= COLS) || (rowNum >= ROWS)) {
        return false;
    }
    return true;
}

class DrawCanvas extends JPanel{

        @Override
        public void paintComponent(Graphics g){ 
            super.paintComponent(g); 
            setBackground(Color.WHITE);

            g.setColor(Color.BLACK);
            for(int ligne = 1; ligne < ROWS; ++ligne){
                g.fillRoundRect(0, cellSize * ligne - halfGridWidth, canvasWidth - 1,
                        gridWidth, gridWidth, gridWidth);
            }
            for(int colonne = 1; colonne < COLS; ++colonne){
                g.fillRoundRect(cellSize * colonne - halfGridWidth, 0
                        , gridWidth, canvasHeight - 1,
                        gridWidth, gridWidth);
            }


            Graphics2D g2d = (Graphics2D)g;
            g2d.setStroke(new BasicStroke(symbolStrokeWidth,
                    BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND)); 
            for(int ligne = 0; ligne < ROWS; ++ligne){
                for(int colonne = 0; colonne < COLS; ++colonne){
                    int x1 = colonne * cellSize + cellPadding;
                    int y1 = ligne * cellSize + cellPadding;

                    if(board[ligne][colonne] == Token.CERCLE_ROUGE){
                        g2d.setColor(Color.RED);
                        g2d.drawOval(x1, y1, symbolSize, symbolSize);
                        g2d.fillOval(x1, y1, symbolSize, symbolSize);
                    } else
                        if(board[ligne][colonne] == Token.CERCLE_BLEU){
                            int x2 = colonne * cellSize + cellPadding;
                            g2d.setColor(Color.BLUE);
                            g2d.drawOval(x1, y1, symbolSize, symbolSize);
                            g2d.fillOval(x2, y1, symbolSize, symbolSize);
                        }
                }

            }



    public static void main(String[] args){
        SwingUtilities.invokeLater(() -> {
            Pha pha = new Pha();
        });
    }
}

Below, the MVC proposed by Hovercraft Full Of Eels works, but not as expected:

The enum class representing cells state:

public enum Token {
    VIDE, CERCLE_BLEU, CERCLE_ROUGE
}

Control:

import java.beans.IndexedPropertyChangeEvent;
import java.beans.PropertyChangeEvent;
import java.beans.PropertyChangeListener;
import javax.swing.JFrame;

public class Control {
    private Model model;
    private View view;

    public Control(Model model, View view) {
        this.model = model;
        this.view = view;

        view.createGrid(model.getRows(), model.getCols());

        view.getMainPanel().addPropertyChangeListener(new ViewListener());
        model.addPropertyChangeListener(Model.TOKEN, new ModelListener());
    }

    private class ViewListener implements PropertyChangeListener {
        @Override
        public void propertyChange(PropertyChangeEvent evt) {
            if (evt.getPropertyName().equals(View.CELL_SELECTION)) {
                int row = view.getSelectedRow();
                int col = view.getSelectedCol();

                Token token = model.getToken(row, col);
                if (token == Token.VIDE) {
                    token = Token.CERCLE_BLEU;
                } else if (token == Token.CERCLE_BLEU) {
                    token = Token.CERCLE_ROUGE;
                } else {
                    token = Token.VIDE;
                }
                model.setToken(token, row, col);
            }
        }
    }

    private class ModelListener implements PropertyChangeListener {
        @Override
        public void propertyChange(PropertyChangeEvent evt) {
            IndexedPropertyChangeEvent iEvt = (IndexedPropertyChangeEvent)evt;
            int index = iEvt.getIndex();
            int row = index / Model.COLS;
            int col = index % Model.COLS;
            Token token = (Token) evt.getNewValue();
            view.setCell(token, row, col);
        }
    }

    public void start() {
        JFrame frame = new JFrame("MVC");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(view.getMainPanel());
        frame.pack();
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

}

The View:

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import java.util.EnumMap;
import java.util.Map;

import javax.swing.BorderFactory;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JPanel;

public class View {

    private static final int ICON_W = 12;
    public static final String CELL_SELECTION = "cell selection";
    private int rows;
    private int cols;
    private JPanel mainPanel = new JPanel();
    private JLabel[][] grid;
    private Map<Token, Icon> iconMap = new EnumMap<>(Token.class);
    private int selectedRow;
    private int selectedCol;

    public View() {
        iconMap.put(Token.VIDE, createIcon(new Color(0, 0, 0, 0)));
        iconMap.put(Token.CERCLE_BLEU, createIcon(Color.BLUE));
        iconMap.put(Token.CERCLE_ROUGE, createIcon(Color.RED));
    }

    private Icon createIcon(Color color) {
        BufferedImage img = new BufferedImage(ICON_W, ICON_W, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g2 = img.createGraphics();
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g2.setColor(color);
        g2.fillOval(1, 1, ICON_W - 2, ICON_W - 2);
        g2.dispose();

        return new ImageIcon(img);
    }

    public void createGrid(int rows, int cols) {
        MyMouse myMouse = new MyMouse();
        this.setRows(rows);
        this.cols = cols;
        mainPanel.setLayout(new GridLayout(rows, cols, 1, 1));
        mainPanel.setBorder(BorderFactory.createLineBorder(Color.BLACK));
        mainPanel.setBackground(Color.BLACK);
        grid = new JLabel[rows][cols];
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                grid[r][c] = new JLabel(iconMap.get(Token.VIDE));
                grid[r][c].addMouseListener((MouseListener) myMouse); //cast
                grid[r][c].setOpaque(true);
                grid[r][c].setBackground(Color.WHITE);
                mainPanel.add(grid[r][c]);
            }
        }
    }

    public JPanel getMainPanel() {
        return mainPanel;
    }

    public int getSelectedRow() {
        return selectedRow;
    }

    public int getSelectedCol() {
        return selectedCol;
    }

    public void setCell(Token token, int row, int col) {
        grid[row][col].setIcon(iconMap.get(token));
    }

    public int getRows() {
        return rows;
    }

    public void setRows(int rows) {
        this.rows = rows;
    }

    private class MyMouse extends MouseAdapter {
        @Override
        public void mousePressed(MouseEvent e) {
            JLabel selection = (JLabel) e.getSource();
            for (int r = 0; r < grid.length; r++) {
                for (int c = 0; c < grid[r].length; c++) {
                    if (selection == grid[r][c]) {
                        selectedRow = r;
                        selectedCol = c;
                        int index = r * grid[r].length + c;
                        mainPanel.firePropertyChange(CELL_SELECTION, -1, index);
                    }
                }
            }
        }
    }
}

The model:

import java.beans.PropertyChangeListener;
import javax.swing.event.SwingPropertyChangeSupport;

public class Model {
    public static final int ROWS = 75;
    public static final int COLS = ROWS;
    public static final String TOKEN = "token";
    private Token[][] grid = new Token[ROWS][COLS];
    private SwingPropertyChangeSupport pcSupport = new SwingPropertyChangeSupport(this);

    public Model() {
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                grid[r][c] = Token.VIDE;
            }
        }
    }

    public Token getToken(int row, int col) {
        return grid[row][col];
    }

    public void setToken(Token token, int row, int col) {
        Token oldValue = grid[row][col];
        Token newValue = token;
        grid[row][col] = token;
        int index = row * grid[row].length + col;
        pcSupport.fireIndexedPropertyChange(TOKEN, index, oldValue, newValue);
    }

    public void addPropertyChangeListener(PropertyChangeListener listener) {
        pcSupport.addPropertyChangeListener(listener);
    }

    public void addPropertyChangeListener(String name, PropertyChangeListener listener) {
        pcSupport.addPropertyChangeListener(name, listener);
    }

    public int getRows() {
        return ROWS;
    }

    public int getCols() {
        return COLS;
    }

}

The main class:

import javax.swing.SwingUtilities;

public class Pha {

    public static void main(String[] args) {
        // run all on the Swing event thread
        SwingUtilities.invokeLater(() -> {
            Model model = new Model();
            View view = new View();
            Control control = new Control(model, view);
            control.start();
        });
    }
}

Solution

  • In the following code, I removed everything which is not essential to demonstrate the requested algorithm. The code does include some data for testing.
    I think posting a mcve is very helpful for quality questions and answers. Too much information is as bad as too little.
    The code searches a path as requested. Please note that it does not search for any particular path property (like shortest ot longest path).
    Also, the code as written looks for one path. Their may be more.
    I assume you'll need to study the code to adapt it to your needs, further test it, and hopefully improve it.

    import java.awt.BasicStroke;
    import java.awt.BorderLayout;
    import java.awt.Color;
    import java.awt.Container;
    import java.awt.Dimension;
    import java.awt.Graphics;
    import java.awt.Graphics2D;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Stack;
    
    import javax.swing.JFrame;
    import javax.swing.JPanel;
    import javax.swing.SwingUtilities;
    
    
    public final class Pha extends JFrame {
    
        //a collection of cells in the path.
        //each cell represented by [row,col]
        private Stack<int[]>path;
    
        //a path shorter than min can not surround any cell
        private static final int MIN_PATH_LEGTH = 4;
    
        //a collection of cells that has been tested
        private ArrayList<int[]>checked;
    
        //represents the cell where the search starts from
        int[] origin;
        //represents the token of the origin
        Token originToken;
    
        private static int ROWS = 15;
        private static int COLS = ROWS;
        private static int cellSize = 15;
        private static int canvasWidth = (cellSize * COLS) + (ROWS *4) ;
        private static int canvasHeight = cellSize * ROWS ;
        private static int gridWidth = 1;
        private static int halfGridWidth = gridWidth / 2;
    
        private static int cellPadding = cellSize / 5;
        private static int symbolSize = cellSize - (cellPadding * 2);
        private static int symbolStrokeWidth = 3;
    
        private enum Token{
            VIDE, CERCLE_ROUGE, CERCLE_BLEU
        }
    
        private Token[][] board;
        private final DrawCanvas canvas;
    
        //used to set different test data
        private static int testNumber = 0;
    
        public Pha(){
    
            canvas = new DrawCanvas();
            canvas.setPreferredSize(new Dimension(canvasWidth, canvasHeight));
    
            Container cp = getContentPane();
            cp.setLayout(new BorderLayout());
            cp.add(canvas, BorderLayout.EAST);
    
            setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            pack();
            setTitle("Pha par esQmo");
            setVisible(true);
    
            board = new Token[ROWS][COLS];
            initGame();
    
            //fill some data for testing
            int[] origin = loadtestData(board);
            findPath(origin);
        }
    
        private void initGame(){
    
            for(int ligne = 0; ligne < ROWS; ++ligne){
                for(int colonne = 0; colonne < COLS; ++colonne){
                    board[ligne][colonne] = Token.VIDE;
                }
            }
        }
        //search for a path
        private void findPath(int[] origin) {
    
            //initialize path and checked
            path = new Stack<>();
            this.origin = origin;
    
            int row = origin[0] , col =  origin[1];
    
            //represents the token of the origin
            originToken = board[row][col];
    
            //initialize list of checked items
            checked = new  CellsList();
    
            boolean found = findPath(row, col);
    
            if(found) {
                printPath();
            } else {
                System.out.println("No path found");
            }
        }
    
        //recursive method to find path. a cell is represented by its row, col
        //returns true when path was found
        private boolean findPath(int row, int col) {
    
            //check if cell has the same token as origin
            if(board[row][col] != originToken) {
                return false;
            }
    
            int[] cell = new int[] {row, col};
    
            //check if this cell was tested before to avoid checking again
            if(checked.contains(cell)) {
                return false;
            }
    
            //get cells neighbors
            CellsList neighbors = getNeighbors(row, col);
    
            //check if solution found. If path size > min and cell
            //neighbors contain the origin it means that path was found
            if((path.size() > MIN_PATH_LEGTH) && neighbors.contains(origin)  ) {
    
                path.add(cell);
                return true;
            }
    
            //add cell to checked
            checked.add(cell);
    
            //add cell to path
            path.add(cell);
    
            //if path was not found check cell neighbors
            for(int[] neighbor : neighbors ) {
    
                boolean found = findPath(neighbor[0],neighbor[1]);
                if(found) {
                    return true;
                }
            }
    
            //path not found
            path.pop(); //remove last element from stack
            return false;
        }
    
        //return a list of all neighbors of cell row, col
        private CellsList getNeighbors(int  row, int col) {
    
            CellsList neighbors = new CellsList();
    
            for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1  ) {
    
                for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1  ) {
    
                    if(!((colNum == col) && (rowNum == row))) {
    
                        if(withinGrid (rowNum, colNum )  ) {
    
                            neighbors.add( new int[] {rowNum, colNum});
                        }
                    }
                }
            }
    
            return neighbors;
        }
    
        private boolean withinGrid(int colNum, int rowNum) {
    
            if((colNum < 0) || (rowNum <0) ) {
                return false;
            }
            if((colNum >= COLS) || (rowNum >= ROWS)) {
                return false;
            }
            return true;
        }
    
        private void printPath() {
            System.out.print("Path : " );
            for(int[] cell : path) {
                System.out.print(Arrays.toString(cell));
            }
            System.out.println("");
        }
    
        class DrawCanvas extends JPanel{
    
            @Override
            public void paintComponent(Graphics g){
                super.paintComponent(g);
                setBackground(Color.WHITE);
    
                g.setColor(Color.BLACK);
                for(int ligne = 1; ligne < ROWS; ++ligne){
                    g.fillRoundRect(0, (cellSize * ligne) - halfGridWidth, canvasWidth - 1,
                            gridWidth, gridWidth, gridWidth);
                }
                for(int colonne = 1; colonne < COLS; ++colonne){
                    g.fillRoundRect((cellSize * colonne) - halfGridWidth, 0
                            , gridWidth, canvasHeight - 1,
                            gridWidth, gridWidth);
                }
    
    
                Graphics2D g2d = (Graphics2D)g;
                g2d.setStroke(new BasicStroke(symbolStrokeWidth,
                        BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
                for(int ligne = 0; ligne < ROWS; ++ligne){
                    for(int colonne = 0; colonne < COLS; ++colonne){
                        int x1 = (colonne * cellSize) + cellPadding;
                        int y1 = (ligne * cellSize) + cellPadding;
    
                        if(board[ligne][colonne] == Token.CERCLE_ROUGE){
                            g2d.setColor(Color.RED);
                            g2d.drawOval(x1, y1, symbolSize, symbolSize);
                            g2d.fillOval(x1, y1, symbolSize, symbolSize);
                        } else
                            if(board[ligne][colonne] == Token.CERCLE_BLEU){
                                int x2 = (colonne * cellSize) + cellPadding;
                                g2d.setColor(Color.BLUE);
                                g2d.drawOval(x1, y1, symbolSize, symbolSize);
                                g2d.fillOval(x2, y1, symbolSize, symbolSize);
                            }
                    }
                }
            }
        }
    
        public static void main(String[] args){
    
            //set test number. Change values between 0-2 to run different tests
            testNumber = 2;
            SwingUtilities.invokeLater(() -> {
                new Pha();
            });
        }
    
        //method used for testing only: load test data
        private static int[] loadtestData(Token[][] board) {
    
            switch (testNumber) {
    
                case 1:
                    board[6][6] = Token.CERCLE_ROUGE; //origin and target
                    board[6][7] = Token.CERCLE_ROUGE;
                    board[6][8] = Token.CERCLE_BLEU;
    
                    board[7][6] = Token.CERCLE_ROUGE;
                    board[7][7] = Token.CERCLE_BLEU;
                    board[7][8] = Token.CERCLE_BLEU;
    
                    board[8][6] = Token.CERCLE_ROUGE;
                    board[8][7] = Token.CERCLE_ROUGE;
                    board[8][8] = Token.CERCLE_ROUGE;
    
                    board[5][7] = Token.CERCLE_ROUGE;
                    board[5][8] = Token.CERCLE_ROUGE;
                    board[5][9] = Token.CERCLE_ROUGE;
                    board[6][9] = Token.CERCLE_ROUGE;
                    board[7][9] = Token.CERCLE_ROUGE;
                    return new int[] {6,6};
    
                case 2:
                    //line 3
                    board[3][6] = Token.CERCLE_ROUGE;
                    //line 4
                    board[4][4] = Token.CERCLE_BLEU; //origin
                    board[4][5] = Token.CERCLE_BLEU;
                    board[4][6] = Token.CERCLE_BLEU;
                    board[4][8] = Token.CERCLE_BLEU;
                    //line5
                    board[5][3] = Token.CERCLE_BLEU;
                    board[5][5] = Token.CERCLE_ROUGE;
                    board[5][7] = Token.CERCLE_BLEU;
                    board[5][8] = Token.CERCLE_ROUGE;
                    board[5][9] = Token.CERCLE_BLEU;
                    //line 6
                    board[6][2] = Token.CERCLE_BLEU;
                    board[6][3] = Token.CERCLE_ROUGE;
                    board[6][4] = Token.CERCLE_ROUGE;
                    board[6][5] = Token.CERCLE_ROUGE;
                    board[6][6] = Token.CERCLE_ROUGE;
                    board[6][7] = Token.CERCLE_ROUGE;
                    board[6][8] = Token.CERCLE_ROUGE;
                    board[6][9] = Token.CERCLE_BLEU;
                    //line 7
                    board[7][3] = Token.CERCLE_BLEU;
                    board[7][4] = Token.CERCLE_BLEU;
                    board[7][5] = Token.CERCLE_BLEU;
                    board[7][6] = Token.CERCLE_BLEU;
                    board[7][7] = Token.CERCLE_ROUGE;
                    board[7][8] = Token.CERCLE_BLEU;
                    //line 8
                    board[8][3] = Token.CERCLE_ROUGE;
                    board[8][7] = Token.CERCLE_BLEU;
                    board[8][8] = Token.CERCLE_ROUGE;
                    board[8][9] = Token.CERCLE_BLEU;
                    //line 9
                    board[9][7] = Token.CERCLE_ROUGE;
                    board[9][8] = Token.CERCLE_BLEU;
                    board[9][9] = Token.CERCLE_ROUGE;
                    //line 10
                    board[10][8] = Token.CERCLE_ROUGE;
                    board[10][9] = Token.CERCLE_ROUGE;
                    return new int[] {4,4};
    
                case 0: default:
                        board[6][6] = Token.CERCLE_ROUGE;
                        board[6][7] = Token.CERCLE_ROUGE; //origin and target
                        board[6][8] = Token.CERCLE_BLEU;
    
                        board[7][6] = Token.CERCLE_ROUGE;
                        board[7][7] = Token.CERCLE_BLEU;
                        board[7][8] = Token.CERCLE_ROUGE;
    
                        board[8][6] = Token.CERCLE_ROUGE;
                        board[8][7] = Token.CERCLE_ROUGE;
                        board[8][8] = Token.CERCLE_ROUGE;
    
                        board[5][7] = Token.CERCLE_ROUGE;
                        board[5][8] = Token.CERCLE_ROUGE;
                        board[5][9] = Token.CERCLE_ROUGE;
                        board[6][9] = Token.CERCLE_ROUGE;
                        board[7][9] = Token.CERCLE_ROUGE;
                        return new int[] {6,7};
            }
        }
    }
    
    class CellsList extends ArrayList<int[]>{
    
        @Override  //override to check by the value of int[]
        public boolean contains(Object o) {
    
            for (int[] a : this) {
                if(Arrays.equals(a, (int[]) o)) {
                    return true;
                }
            }
    
            return false;
        }
    }