TBD.my

Full Version: [help] i need idea on how put my 2D array in best first search algo
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Code:
public class puzzlegame {

    public static void board(){
    
        int board[][]= new int[4][4];
        board[0][0] = 15;
        board[1][0] = 5;
        board[2][0] = 12;
        board[3][0] = -1;
        board[0][1] = 6;
        board[1][1] = 2;
        board[2][1] = 3;
        board[3][1] = 13;
        board[0][2] = 1;
        board[1][2] = 9;
        board[2][2] = 11;
        board[3][2] = 7;
        board[0][3] = 10;
        board[1][3] = 4;
        board[2][3] = 14;
        board[3][3] = 8;
        
        System.out.println("Le unsolved board (-1 = blank)");
        
        System.out.print(board[0][0]+" | ");
        System.out.print(board[1][0]+" | ");
        System.out.print(board[2][0]+" | ");
        System.out.print(board[3][0]+" | ");
        System.out.println();
        System.out.print(board[0][1]+"  | ");
        System.out.print(board[1][1]+" | ");
        System.out.print(board[2][1]+"  | ");
        System.out.print(board[3][1]+" | ");
        System.out.println();
        System.out.print(board[0][2]+"  | ");
        System.out.print(board[1][2]+" | ");
        System.out.print(board[2][2]+" | ");
        System.out.print(board[3][2]+"  | ");
        System.out.println();
        System.out.print(board[0][3]+" | ");
        System.out.print(board[1][3]+" | ");
        System.out.print(board[2][3]+" | ");
        System.out.print(board[3][3]+"  | ");
        
    }
    
    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

[Image: 4iu214ljr]

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 ?
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, 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

[Image: puzzle15adfin.jpg]

without the GUI

i think i wanna do the swap function first before implementing the algorithm.
Raw idea, check the algorithm
Code:
http://jimmod.com/blog/2011/02/jimmys-blog-slide-number-puzzle-game-with-echo2-framework/
DONE ! but complicated puzzles cannot be solved by this code dunno why :'(

Rage 2

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))
            queue.add(successor);
    }

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

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

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

        // Add initial state to queue.
        queue.add(new EightPuzzle.State(initial));

        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.
            closed.add(state);

            // Add successors to the queue.
            addSuccessor(state.moveS());
            addSuccessor(state.moveN());
            addSuccessor(state.moveW());
            addSuccessor(state.moveE());
        }
    }

    // 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);
    }
}
nice.. i found this
Code:
http://www.cs.cmu.edu/~adamchik/15-121/labs/HW-7%20Slide%20Puzzle/lab.html