# Game 3x3

Printable View

• December 20th, 2009, 05:14 AM
Koren3
Game 3x3
Hallo, I am doing GamingTable size 3x3(look at the picture)http://img704.imageshack.us/img704/5...mingtabled.jpg. And i need generate some solution but i donīt know how can i do this. Target is find the best algorithm for solution.
My code:
Main class
Code :

```public class Main {   /** * @param args the command line arguments */ public static void main(String[] args) { try { GamingTable g1 = new GamingTable(3); System.out.println(g1); g1.move(GamingTable.Direction.UP); System.out.println("Done"); System.out.println(g1); } catch (NotPossibleMoveException ex) { System.out.println("Not done"); }     }   }```
Class GamingTable
Code :

```public class GamingTable { private short data [][]; private int positionX; private int positionY; private final int EMPTY = -1; public enum Direction {UP, DOWN, LEFT, RIGHT}   public GamingTable(int size) { data = new short[size][size]; short counter = 1; for (int y = 0; y < size; y++) { for (int x = 0; x < size; x++) { data[x][y]=counter++; }   } positionX = size - 1; positionY = size - 1; data[positionX][positionY] = EMPTY; }   public GamingTable() { this(4); }   public GamingTable(GamingTable g) { this.positionX = g.positionX; this.positionY = g.positionY; this.data= new short[g.data.length][g.data.length]; for (int i = 0; i < data.length; i++) { System.arraycopy(g.data[i],0,this.data[i],0,data[i].length); } }   public GamingTable(short[][] data, int startX, int startY) throws InvalidTableConfigurationException { if(data.length < 1 || data.length != data[0].length || data[startX][startY] != EMPTY) throw new InvalidTableConfigurationException(); this.positionX = startX; this.positionY = startY; this.data = new short[data.length][data.length]; for (int y = 0; y < data.length; y++) { for (int x = 0; x < data.length; x++) { this.data[x][y] = data[y][x]; }   } }   @Override public String toString() { String s = ""; for (int y = 0; y < data.length; y++) { for (int x = 0; x < data.length; x++) { s += data[x][y]; } s +="\n";   } return s; }   public int fitness() { int fitness = 0; short counter = 1; for (int y = 0; y < data.length; y++) { for (int x = 0; x < data.length; x++) { if(data[x][y] == counter) { fitness ++; } counter ++; }   } return fitness; }   public boolean isSolution() { return fitness() == data.length * data.length -1; }   public void move(Direction dir) throws NotPossibleMoveException { switch(dir) { case UP: if(positionY <= 0) throw new NotPossibleMoveException(); swap(positionX, positionY, positionX, positionY-1); positionY -= 1; break; case DOWN: if(positionY >= data.length-1) throw new NotPossibleMoveException(); swap(positionX, positionY, positionX, positionY+1); positionY += 1; break; case LEFT: if(positionX <= 0) throw new NotPossibleMoveException(); swap(positionX, positionY, positionX-1, positionY); positionX -= 1; break; case RIGHT: if(positionX >= data.length-1) throw new NotPossibleMoveException(); swap(positionX, positionY, positionX+1, positionY); positionX += 1; break; } }   private void swap(int x1, int y1, int x2, int y2) { short tmp = data[x1][y1]; data[x1][y1] = data [x2][y2]; data[x2][y2] = tmp; }     }```
Class Solver
Code :

```public class Solver implements ISolver {   }```
Interface ISolver
Code :

```interface ISolver {   }```
• December 20th, 2009, 08:43 PM
helloworld922
Re: Game 3x3
The simplest method for performing such a search is a brute strength breadth-depth search.

The idea is simply start by trying all possible single moves with the current board configuration. If one of them solves the puzzle, then mark the puzzle as solved. If not, recursively pass each new modified board through the algorithm.

This will automatically find one of the possible minimum number of steps to solve this type of puzzle (can you see why?). It's not an efficient algorithm, but because this puzzle is so small it's sufficient to use such an algorithm (sorry, I don't know the running time for this algorithm :( )

A more efficient method of solving this puzzle is to apply anything you know about solving this type of puzzle (certain types of piece movements that will get the board into a configuration you want, etc.), which unfortunately for me is pretty much nill.