Tuesday, July 20, 2010

8 Puzzle Problem.

The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Such a puzzle is illustrated in following diagram.
The program is to change the initial configuration into the goal configuration. A solution to the problem is an appropriate sequence of moves, such as “move tiles 5 to the right, move tile 7 to the left ,move tile 6 to the down, etc”.



To solve a problem using a production system, we must specify the global database the rules, and the control strategy. For the 8 puzzle problem that correspond to these three components. These elements are the problem states, moves and goal. In this problem each tile configuration is a state. The set of all configuration in the space of problem states or the problem space, there are only 3,62,880 different configurations o the 8 tiles and blank space. Once the problem states have been conceptually identified, we must construct a computer representation, or description of them . this description is then used as the database of a production system. For the 8-puzzle, a straight forward description is a 3X3 array of matrix of numbers. The initial global database is this description of the initial problem state. Virtually any kind of data structure can be used to describe states.

A move transforms one problem state into another state. The 8-puzzle is convenjently interpreted as having the following for moves. Move empty space (blank) to the left, move blank up, move blank to the right and move blank down,. These moves are modeled by production rules that operate on the state descriptions in the appropriate manner.



The rules each have preconditions that must be satisfied by a state description in order for them to be applicable to that state description. Thus the precondition for the rule associated with “move blank up” is derived from the requirement that the blank space must not already be in the top row.



The problem goal condition forms the basis for the termination condition of the production system. The control strategy repeatedly applies rules to state descriptions until a description of a goal state is produced . it also keep track of rules that have been applied so that it can compose them into sequence representing the problem solution. A solution to the 8-puzzle problem is given in the following figure.



Example:- Depth – First – Search traversal  and Breadth - First - Search traversal                         
                                    for 8 – puzzle problem is shown in following diagrams.





35 comments:

  1. gud explanation........ got wat i actually was not able to understand....

    ReplyDelete
  2. mast hai yr (y) so trivial but
    you have teach us in a very good way :)
    keep doing like this .

    ReplyDelete
    Replies
    1. u have teach nhi..u have "taught"

      Delete
  3. In DFS there isnt any Tree structure will be formed it keeps on growing in one branch alone !! and almost all the combinations are being expanded in the single branch itself. What is the constrain to get the end of the branch ? :)

    ReplyDelete
  4. how to solve this problem using A* algorithm ???

    ReplyDelete
  5. which one is the breadth first?? how do we do both the search algorithms seperately? pls help

    ReplyDelete
  6. sir can u plz explain the 8 puzzle problem tic-tac-toe using breadth first search...

    ReplyDelete
  7. sir can u plz expalin the 8 puzzle problem and tic-tac-toe problem using breadth first search

    ReplyDelete
  8. Please put the search text box of your website above the analog clock so that users can easily see the results below the search box.

    ReplyDelete
  9. Initial state:
    5 4 -
    6 1 8
    7 3 2
    Goal state
    1 4 7
    2 5 8
    3 6 -
    can any one explain it deeply as explained above

    ReplyDelete
  10. Good tutorial but I have two doubts
    1. How to do this using heuristic function
    2. What is the most optimal solution for solving the same problem (any other optimal technique for this)

    Thanks in advance

    ReplyDelete
  11. Thank you sir,your solution is very helpful for me.

    ReplyDelete
  12. Thanks for sharing information about Artificial Intelligence.
    Artificial Intelligence Solutions

    ReplyDelete
  13. thanks for material.
    it's useful for me.
    great job sir.

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. Role of Artificial Intelligence And Machine Learning in Financial Services Artificial Intelligence and Machine Learning are now becoming a prominent word in terms of technology. Almost every technology advancement depends widely on AI and ML that are slowing spreading their wings around.

    ReplyDelete
  16. I was wondering if it is possible to apply this method in rubiks cube solution.

    ReplyDelete
  17. Thank you for sharing this post
    Very nice post here thanks for it I always like and search such topics and everything connected to them.

    Artificial Intelligence Solutions

    ReplyDelete
  18. AI & ML in Dubai
    https://www.nsreem.com/ourservices/ai-ml/
    Artificial intelligence is very widespread today. In at least certainly considered one among its various forms has had an impact on all major industries in the world today, NSREEM is #1 AI & ML Service Provider in Dubai
    1634529374794-9

    ReplyDelete
  19. AI & ML in Dubai
    https://www.nsreem.com/ourservices/ai-ml/
    Artificial intelligence is very widespread today. In at least certainly considered one among its various forms has had an impact on all major industries in the world today, NSREEM is #1 AI & ML Service Provider in Dubai
    1634543056157-9

    ReplyDelete
  20. I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much. Flow water fountain game

    ReplyDelete
  21. Thanks for Sharing This Article.It is very so much valuable content. I hope
    these Commenting lists will help to my website
    ServiceNow Online Training
    best ServiceNow Online Training
    top ServiceNow Online Training

    ReplyDelete
  22. your blog is being updated.
    Thanks for posting a valuable and informative blog.
    I have one more information related with roblox..
    DownloadRobloxPlayer.Exe

    ReplyDelete
  23. I saw a lot of website but I conceive this one has something extra in it. Look at this very wonderful website credit card generator

    ReplyDelete