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.


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

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

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

  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 ? :)

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

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

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

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

  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.

  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

  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

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

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

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

  14. This comment has been removed by the author.

  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.

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

  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