Algorithm to solve dots and lines problem?

This is a classical game. Thought of explaining the game in my own words, But wiki does it better,

http:/开发者_运维百科/en.wikipedia.org/wiki/Dots_and_Boxes

I am trying to create this game as 2 player game, so no AI is required as of now.

But confused as to what data structure and Algorithm to use, I am saving all dots as co-ordinates in an array, e.g. [x1,y1,x2,y2,x3,y3,x4,y4,....] Where x1,y1 makes a pair and co-ordinates,

I am using java(Android), What is the better way to store co-ordinates ?

Above method seems too basic and can complicate things later.

Planning on array of objects, where each object holds x,y co-ordinates and some other info

in the object.

What algorithm I should apply to check for cycles, i.e. to know that,

move by a player has closed the points. Is this a graph problem?

Any hints on where I have to look for solving this kind of a problem.

PS: This is a 2 player game as of now, so not worried about Computer move,

but more concerned about deciding whether the last move has connected the points

(basically created a cycle? , closed box)

I checked this,

http://en.wikipedia.org/wiki/Flood_fill

something similar to that I should do I guess.

You can use as square class and have an all game structure on 2 dimensional square object array.

public class Square {
     boolean up;
     boolean right;
     boolean down;
     boolean left;

    private boolean isClosed() {
        return up && right && down && left;
    }
}

private static final int TABLE_SIZE = 5;

Square [][] table = new Square[TABLE_SIZE][TABLE_SIZE];

All move affect 2 square (except for exterior line), set their states as true and also control for square is closed;

 // draw line  
 table[1][1].right = true;
 table[2][1].left = true;

 // Check for closed
 table[1][1].isClosed();
 table[2][1].isClosed();

My code is not pretty well, written for show up algorithm.

The key elements of the board are boxes and lines. I think, the dots are just visual marks, especially when you play with pen and paper.

I'd model the board and the boxes (squares). The visualization of a box is (1) four dots, (2) upto for lines/borders in two different colors and (3) a letter in its center.

An instance of a Board class has some (4,6,9) Box instances. A two dimensional array of Box would be sufficiant. The advantage of such an array is that it is pretty easy to identify adjacent boxes (you'll need that if a player draws a line as it may affect two boxes)

Again, don't model dots. A BoxPainter can draw them on the screen.

When is a box closed? - when all of it's four borders are marked as painted. Add a simply isFilled() method to the Box class and call the method on all Box instances after every player move.

Just keep track of where the lines are. As Andreas_D mentioned, the dots serve no purpose other than being a visual aid for where to draw the lines.

Whenever a player draws a line, then you should check to see if it makes a box. You can either keep track of the boxes in an array or not. For a game, you may want to keep track of them and the player who scored the point as part of the UI. But in terms of the game, there's no need to store the boxes.

Lines can easily be stored in an 2D array.