6 replies to this topic

[headhunterz]

hi everybody. i write a project for my university.a picture puzzle! my problem is the automatic game.this means at the beginning of the game player can play the game or le the computer to play the game. if you can help me for automatic algorithm so please do that!

Attached Files

•  picture puzzle..rar   1.3MB   125 downloads

[headhunterz]

me again! if my project is elementary please forgive! im a beginner

[zoranh]

Is that a puzzle with one piece missing, like 8-puzzle (3x3) or 15-puzzle (4x4)? (Sorry for asking, I'm not using RAR and cannot look into your attachment easily.)

[headhunterz]

bonjour!!!yes thats a 3*3 puzzle.
thanks for your attention

[zoranh]

I'll give you the precise guidelines as stated in book Artificial Intellicence - A Modern Approach (2nd edition) by Russell and Norvig (founders of the IDA* algorithm). If you manage to get possession of this book, you'll find full explanations in chapter on Informed Search and Exploration, section on heuristic functions.

This is what it says in few details.

8-puzzle (3x3) has about 170,000 unique states and can be solved by brute force. 15-puzzle (4x4) has around 10^13 unique states and can't be solved like that.

General solution is based on A* search and a heuristic function that never overestimates the number of steps to the goal (called admissible heuristic). This condition is important, and you should read some theory on heuristics to find out why (there are exact proofs and they're fun for themselves).

Suggested heuristics are:

• Total number of misplaced tiles; if all tiles are out of place then value is 8, if puzzle is solved then value is 0.
  
• Sum of all distances of tiles from their goal positions. For each tile distance from goal position is sum of horizontal and vertical distances from goal position, and not diagonal distance.

I haven't tried to solve this particular problem, but I have tried many other functions and methods described in this book and they never failed. Go straight to second heuristic and that will give you quite optimal solution to this search problem.

For more details on A* and IDA* (A* is sufficient for this puzzle), refer to Google almighty, who will probably point you further to Wikipedia almighty.

[zoranh]

I've added few more words and posted the blog on this topic:
http://forum.codecal...mmatically.html

Thanks for giving me the topic to write about.

[headhunterz]

thanks my friend.
thanks a lot................