Show Bid Request
Solving the 8-puzzle by implementing A* algorithm.
Bid Request Id: 34522
|
|
|
|
Posted by: |
Winner99 (2 ratings)
(Software buyer rating 10 )
|
|
Posted: |
Nov 8, 2002
12:52:10 AM EDT
|
|
Bidding Closes: |
Nov 11, 2002
12:54:34 AM EDT
|
|
Viewed (by coders): |
179 times
|
|
Deadline: |
11/12/2002
TIME EXPIRED
|
|
|
|
|
Description:
Solving the 8-puzzle by implementing A* algorithm.
I want code in java that implement A* algorithm (Heuristic search) for the 8-puzzle game by given any initial state for example:
2 3 5
8 7 6
1 9 4
and to solve it to get this Goal state:
1 2 3
8 9 4
7 6 5
I do not want to use GUI (graphically), I want to use DOS interface only, and also I want to show these outputs :
1. Show the puzzles from start to the goal state (only the minimum path, not all puzzles)
2. Movements of the blank (could be 0 or 9) tile for example : Tile [3] Down (only puzzles in the minimum path).
3. Show value of Heuristic function at each puzzle f(n) ((only puzzle in the minimum path)
Finally number of movements. (this algorithm must result minimum number of steps to reach goal state).
^g(n)= the depth of node n in the search graph.
^h(n)=number of tiles out of place compared with goal state.
Here is an example shows what I want the code to do :
First: ask the user to enter initial state then start solve the problem:
Enter initial state : 283164795 // 9 àmeans space
Initial state
2 8 3
1 6 4
7 9 5
f = 4 (0+4)
2 8 3
1 9 4
7 6 5
f = 4 (1+4)
Tile (8) up
2 9 3
1 8 4
7 6 5
f = 5 (2+3)
Tile (5) up
9 2 3
1 8 4
7 6 5
f = 5 (3+2)
Tile (2) left
1 2 3
9 8 4
7 6 5
f = 5 (4+1)
Tile (1) down
1 2 3
8 9 4
7 6 5
f = 5 (5+0)
Tile (4) right
Total number of movements :5
Deliverables:
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Complete ownership and distribution copyrights to all work purchased.
Platform:
Java (j2sdk-1_3_1_01)
Windows Me
Must be 100% finished and received by buyer on:
Nov 12, 2002 EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation, you can report it to: abuse@rentacoder.com.
|
|
|
Bidding/Comments:
|
All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. |
See all rejected bids (and all comments)
| Name |
Bid Amount
|
Date |
Coder Rating |
|
|
This bid was accepted by the buyer!
|
$25 (USD)
|
Nov 8, 2002
1:10:15 AM EDT
|
9.38
(Superb)
|
|
|
I would enjoy writing this program for you. I have lots of experience with algorithms for searching graphs and game trees, including A-star. I can easily do this 100% complete and correct in a couple of hours.
One thing I should point out... A-star, in general, is not guaranteed to give you the shortest path to the goal state. However, I believe the heuristic you have chosen will force it to examine the nearest states first.
|
|
|
|
|
|
|
