Thread Rating:
  • 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
[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[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 ?
[Image: Captu3re.jpg]
Reply
14-05-2013, 03:28 PM,
Post: #2
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.
Reply
14-05-2013, 10:29 PM,
Post: #3
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

[Image: puzzle15adfin.jpg]

without the GUI

i think i wanna do the swap function first before implementing the algorithm.
[Image: Captu3re.jpg]
Reply
15-05-2013, 09:01 AM,
Post: #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/
Reply
28-05-2013, 04:30 PM,
Post: #5
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 :'(

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);
    }
}
[Image: Captu3re.jpg]
Reply
28-05-2013, 07:12 PM,
Post: #6
RE: [help] i need idea on how put my 2D array in best first search algo
nice.. i found this
Code:
http://www.cs.cmu.edu/~adamchik/15-121/labs/HW-7%20Slide%20Puzzle/lab.html
Reply


Possibly Related Threads...
Thread Author Replies Views Last Post
  array problem in GUI th3phantom 1 731 03-05-2012, 09:01 PM
Last Post: cupin06
  [Tut]Java Array Name Ujang 2 687 19-04-2012, 03:07 PM
Last Post: pron3t
  [TUT]Java Array Statment Ujang 5 888 19-04-2012, 03:06 PM
Last Post: pron3t
  [help]java error buffered problem and array pron3t 3 792 02-03-2012, 05:25 PM
Last Post: s3m00t

Forum Jump: