• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 [help] i need idea on how put my 2D array in best first search algo
14-05-2013, 12:29 AM, Post: #1 Timon TBD Members  Posts: 167 Joined: Jul 2011 Reputation: 0 [help] i need idea on how put my 2D array in best first search algo
Code:
public class puzzlegame {

public static void board(){

int board[][]= new int;
board = 15;
board = 5;
board = 12;
board = -1;
board = 6;
board = 2;
board = 3;
board = 13;
board = 1;
board = 9;
board = 11;
board = 7;
board = 10;
board = 4;
board = 14;
board = 8;

System.out.println("Le unsolved board (-1 = blank)");

System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.println();
System.out.print(board+"  | ");
System.out.print(board+" | ");
System.out.print(board+"  | ");
System.out.print(board+" | ");
System.out.println();
System.out.print(board+"  | ");
System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.print(board+"  | ");
System.out.println();
System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.print(board+" | ");
System.out.print(board+"  | ");

}

public static void Bestfirst(){

}

public static void main(String[] args) {
board();

}

}

so far my code
its a 15 puzzle game
tujuan saya menggunakan algorithm tersebut untuk menyusun semua nombor yang semak samun mengikut turutan dengan mengalihkan value -1 itu sahaja.
SWAP value -1 itu dengan number terdekat sehingga semua numbor tersusun ini algorithms nya nk tulis code tuh bole tapi masalahnye xde idea mcm mane nk
implement nombor tersebut

kena ada swap function ke ?

any ideas guys ? 14-05-2013, 03:28 PM, Post: #2 linear TBD Members  Posts: 203 Joined: Oct 2012 Reputation: 4 RE: [help] i need idea on how put my 2D array in best first search algo
What do you want want? i cant figure out. but maybe you are looking about sorting. There is plenty way to sort. Each sorting way has their own algorithm and efficiency. For start you can use bubble sort or simple sort.
14-05-2013, 10:29 PM, Post: #3 Timon TBD Members  Posts: 167 Joined: Jul 2011 Reputation: 0 RE: [help] i need idea on how put my 2D array in best first search algo
(14-05-2013, 03:28 PM)linear Wrote: What do you want want? i cant figure out. but maybe you are looking about sorting. There is plenty way to sort. Each sorting way has their own algorithm and efficiency. For start you can use bubble sort or simple sort. i know sort but i dunwan to sort i wan to use the best first search algorithm for solving this puzzle with heuristics. if sort i need to make into array list or linked list. as you can see this is 2D array visual reprentation of the numbers are like this without the GUI

i think i wanna do the swap function first before implementing the algorithm. 15-05-2013, 09:01 AM, Post: #4 linear TBD Members  Posts: 203 Joined: Oct 2012 Reputation: 4 RE: [help] i need idea on how put my 2D array in best first search algo
Raw idea, check the algorithm
Code:
http://jimmod.com/blog/2011/02/jimmys-blog-slide-number-puzzle-game-with-echo2-framework/
28-05-2013, 04:30 PM, Post: #5 Timon TBD Members  Posts: 167 Joined: Jul 2011 Reputation: 0 RE: [help] i need idea on how put my 2D array in best first search algo
DONE ! but complicated puzzles cannot be solved by this code dunno why :'( Code:
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class EightPuzzle {

// Tiles for successfully completed puzzle.
static final byte [] goalTiles = { 0, 1, 2, 3, 4,5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

// A* priority queue.
final PriorityQueue <EightPuzzle.State> queue = new PriorityQueue<EightPuzzle.State>(100, new Comparator<EightPuzzle.State>() {
@Override
public int compare(EightPuzzle.State a, EightPuzzle.State b) {
return a.priority() - b.priority();
}
});

// The closed state set.
final HashSet <EightPuzzle.State> closed = new HashSet <EightPuzzle.State>();

// State of the puzzle including its priority and chain to start state.
class State {
final byte [] tiles;    // Tiles left to right, top to bottom.
final int spaceIndex;   // Index of space (zero) in tiles
final int g;            // Number of moves from start.
final int h;            // Heuristic value (difference from goal)
final EightPuzzle.State prev;       // Previous state in solution chain.

// A* priority function (often called F in books).
int priority() {
return g + h;
}

// Build a start state.
State(byte [] initial) {
tiles = initial;
spaceIndex = index(tiles, 0);
g = 0;
h = heuristic(tiles);
prev = null;
}

// Build a successor to prev by sliding tile from given index.
State(EightPuzzle.State prev, int slideFromIndex) {
tiles = Arrays.copyOf(prev.tiles, prev.tiles.length);
tiles[prev.spaceIndex] = tiles[slideFromIndex];
tiles[slideFromIndex] = 0;
spaceIndex = slideFromIndex;
g = prev.g + 1;
h = heuristic(tiles);
this.prev = prev;
}

// Return true iif this is the goal state.
boolean isGoal() {
return Arrays.equals(tiles, goalTiles);
}

// Successor states due to south, north, west, and east moves.
EightPuzzle.State moveS() { return spaceIndex > 3 ? new EightPuzzle.State(this, spaceIndex - 4) : null; }
EightPuzzle.State moveN() { return spaceIndex < 12 ? new EightPuzzle.State(this, spaceIndex + 4) : null; }
EightPuzzle.State moveE() { return spaceIndex % 4 > 0 ? new EightPuzzle.State(this, spaceIndex - 1) : null; }
EightPuzzle.State moveW() { return spaceIndex % 4 < 3 ? new EightPuzzle.State(this, spaceIndex + 1) : null; }

// Print this state.
void print() {
System.out.println("p = " + priority() + " = g+h = " + g + "+" + h);
for (int i = 1; i < 17; i++){

System.out.printf(" "+"%3s",tiles[i-1]+" "+"|" );
if (i %4 == 0)
{
System.out.println();
}
}
}

// Print the solution chain with start state first.
void printAll() {
if (prev != null) prev.printAll();
System.out.println();
print();
}

@Override
public boolean equals(Object obj) {
if (obj instanceof EightPuzzle.State) {
EightPuzzle.State other = (EightPuzzle.State)obj;
return Arrays.equals(tiles, other.tiles);
}
return false;
}

@Override
public int hashCode() {
return Arrays.hashCode(tiles);
}
}

// Add a valid (non-null and not closed) successor to the A* queue.
void addSuccessor(EightPuzzle.State successor) {
if (successor != null && !closed.contains(successor))
}

// Run the solver.
void solve(byte [] initial) {

queue.clear();
closed.clear();

// Click the stopwatch.
long start = System.currentTimeMillis();

// Add initial state to queue.

while (!queue.isEmpty()) {

// Get the lowest priority state.
EightPuzzle.State state = queue.poll();

// If it's the goal, we're done.
if (state.isGoal()) {
long elapsed = System.currentTimeMillis() - start;
state.printAll();
System.out.println("elapsed (ms) = " + elapsed);
return;
}

// Make sure we don't revisit this state.

// Add successors to the queue.
}
}

// Return the index of val in given byte array or -1 if none found.
static int index(byte [] a, int val) {
for (int i = 0; i < a.length; i++)
if (a[i] == val) return i;
return -1;
}

// Return the  distance between tiles with indices a and b.
static int manhattenDistance(int a, int b) {
return Math.abs(a / 4 - b / 4) + Math.abs(a % 4 - b % 4);
}

// For our A* heuristic, we just use sum of distances of all tiles.
static int heuristic(byte [] tiles) {
int h = 0;
for (int i = 0; i < tiles.length; i++)
if (tiles[i] != 0)
h += manhattenDistance(i, tiles[i]);
return h;

}

public static void main(String[] args) {

// This is a harder puzzle than the SO example
//This will not run! its out of memory when its run
//Perhaps with supercomputer you will be able to run it
//byte [] initial = { 2, 1, 4, 3, 0, 9, 6, 7, 8, 5, 11, 10, 12, 13, 14, 15 };

// This is taken from the SO example.
//byte [] initial = { 1, 2, 4, 3, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
byte [] initial = { 1 , 2 , 4 , 3 , 5 , 0 , 6 , 7 , 8 , 9 , 10, 11, 12, 13, 14, 15 };

new EightPuzzle().solve(initial);
}
} 28-05-2013, 07:12 PM, Post: #6 linear TBD Members  Posts: 203 Joined: Oct 2012 Reputation: 4 RE: [help] i need idea on how put my 2D array in best first search algo
nice.. i found this
Code: 