User:15puzzle
CONTENTS
Chapter 1: INTRODUCTORY CONCEPTS
1.1 What is 15-Puzzle Problem
1.2 History of the Puzzle
1.3 How Data mining is implemented here
Chapter 2: CONVENTIONS USED
2.1 Frame Representation
Chapter 3: DESIGN
3.1 Flowchart
3.2 Algorithm
3.2.1 Time Complexity
3.2.2 Space Complexity
3.3 Decision tree
Chapter 4: FUNCTIONS
4.1 What is Empty Top condition?
4.2 Algorithm for Empty Top function
4.3 What is Empty Left condition?
4.4 Algorithm for Left Top function
4.5 What is Empty Right Condition?
4.6 Algorithm for Empty Right function
Chapter 5: EXCEPTION HANDLER
5.1 What is an Exception case?
5.2 Exception cases for number 4,8,12
5.3 Exception cases for number 10
5.4 Exception cases for number 11
5.5 Exception cases for number 12
Chapter 6: LIMITATIONS
6.1 Limitations
6.2 Disadvantages
6.3 Advantages
Chapter 7:CONCLUSION
What is 15-Puzzle problem:
The puzzle consists of 15 numbered tiles on a square frame with a capacity of 16
tiles. We are given an initial arrangement of the tiles, and the objectives are
to transform this arrangement in to the goal arrangement of figure 1.1 through a
series of legal moves. The only legal moves are ones in which a tile adjacent to
the empty spot (ES) is moved to ES.
Thus form the any initial arrangement four moves is possible. We can move any
one of the tiles adjacent to the empty spot. Following this moves, other moves
can be made. Each moves creates a new arrangement of the tiles. These
arrangements are called the state of the puzzle. The initial and the goal
arrangements are called the initial and the goal state. A state is reachable
from the initial state iff there is a sequence of legal moves form the initial
state to this state. The state space of an initial state consists of all states
that can be reached from the initial state.
It is easy to see that there are 16!
different arrangements of the tiles on the frame. Of those only one-half are
reachable from any given initial state. It is clear that the state phase of the
problem is very large. Before attempting to search this state space for the goal
state, it would be worthwhile to determine whether the goal state s reachable
from the initial state.
1.2 The history of the 15 puzzle:
It is not clear when the first slide puzzle was invented or made. But it is a
well-known fact that in 1878 Sam Loyd, America's greatest puzzle-expert, "drove
the whole world crazy" (in his own words) with his newly "discovered" 14-15
puzzle. This was a variation on the "Puzzle of 15" which was made and sold by
the Embossing Company from New York about 10 years earlier. This puzzle
consisted of 15 numbered square pieces that could be slided around in a square
box that was big enough to contain 16 pieces. The pieces should be placed at
random in the box and you should sort the pieces in ascending order without
taking the pieces out of the box (so the only thing that is allowed is to slide
the pieces). Not every randomly placed pattern of pieces can be sorted by just
shuffling and Sam Loyd cleverly made use of this fact.
It was not surprising that Sam drove the whole world crazy by his variation of
the puzzle of 15. The problem that he formulated was impossible to solve. When
you bought Sam's 14-15 puzzle the empty square was positioned bottom right. The
pieces were numbered in order from left to right and from top to bottom; only
the pieces numbered 14 and 15 were reversed. You should re-order the pieces so
all the pieces are in the correct position and the empty place should be
positioned bottom right again. For the correct solution a prize of 1000 dollar
was offered but Sam kept that money in his pocket. A slide puzzle with square
pieces can only be solved when the number of exchanges necessary to solve the
puzzle is even. The 14-15 puzzles attracted a
worldwide attention that can only be compared with the Rubik's Cube that
conquered the world 100 years later. Ernö Rubik was in fact inspired by the
slide puzzle when he designed his famous cube which can be seen as a 3
dimensional version of a slide puzzle.
Quotation from the Cyclopedia of Puzzles written by Sam Loyd.
"The older inhabitants of Puzzle land will remember how
in the early seventies I drove the entire world crazy over a little box of
movable pieces which became known as the "14-15 Puzzle". The fifteen pieces were
arranged in the square box in regular order, only with the 14 and 15 reversed,
as shown in the figure. The puzzle consisted in moving the pieces about, one at
a time, so as to bring them back in the present position in every respect except
that the error in the 14 and 15 must be corrected. A price of $1000, which was
offered for the first correct solution to the problem has never been claimed."
A clever variation of the 14-15 puzzle is the so called "Rate your mind pal"
puzzle that is shown beside. This puzzle seems impossible to solve at first
sight, certainly for someone who is familiar with the 14-15 puzzle. This puzzle
can be solved however. Think hard ... and when you do not find the answer ask me
for a hint.
Since the famous Sam Loyd's slide puzzle thousands of different slide puzzles
are made. Most of them formed a picture when correctly solved. A slide puzzle
with the companies logo was used by a lot of companies as a small gift for their
relations. Around 1910 the idea to use rectangular pieces came up. These puzzles
are most of the time much more difficult to solve than puzzles with only square
pieces.
For more information on slide puzzles you can consult Edward Hordern's
book Sliding Piece Puzzles published by the Oxford University Press in 1986. A
detailed discussion of the puzzle of 15 and others is given in Automated
Reasoning: Introduction and Applications, by Larry Wos, Ross Overbeek, Ewing
Lusk, and Jim Boyle published by McGraw-Hill.
A nice variation of the basic slide puzzle is a slide puzzle with 15 pieces
numbered form 0(empty) to 15 (inclusive) with the instruction to slide the
pieces so the sum of all rows and the sum of all columns and the sum of the
diagonals equals 30. Such an ordering is called a magic square.
1.3 HOW DATA MINING IS IMPLEMENTED HERE
In this section we will be
discussing about how Data Mining is related to this project. As we have seen
earlier, in the 15-puzzle problem there are total 16 positions for the tiles
(including the empty tile) .So there can be 16! number of arrangements for the
15 tiles ‘ which is definitely a huge number. It is impossible to deal with this
large number of data. So for any sequence given by the user we have to convert
it into a definite pattern (i.e. in ascending order 1-15) by proper slides.
Moreover we have constructed a Decision Tree giving the whole picture of our
problem. Decision Tree is a very important part of Data Mining. Many algorithms
of Data Mining make direct use of Decision Trees. Thus we are properly
implementing Data Mining and Pattern Recognition in our project.
2.1 Convention Used
This section is concerned with the basic conventions used to construct or solve
the 15-puzzle problem. The 15-puzzle frame (fig 2.1) consists of 15 numbered
tiles with a capacity of 16 tiles. This section includes how the 15-Puzzle frame
is represented and how the basic conventions are combined to develop the
algorithm.
2.1 THE FRAME REPRESENTATION
Numbers ranging from 0 to 15 represents the 15-Puzzle frame. It is shown in
fig-2.1. The 1st position is represented by number 0, 2nd position by 1 and so
on. It is clear that number 1 will be in 0th position,2 will be in 1st position…
in the frame.
3.2 ALGORITHM
(Written according to Pseudocode convention)
1. Algorithm 15Puzzle(p)
2. //p is a pointer pointing to the first element of the sequence
3. //pcp is the present column position, prp is present row position
4. // ocp is original column position, orp is original row position
5. // The functions Exception Handler( , ),empty left(),empty right(),empty
top() are
6. // defined previously, no is the handler number.
7. {
8. p:=0;
9.. p:=p+1;
10. while(p<15) do
11. {
12. if(p=p.value)then
13. {
14. go to step 4;
15. }
16. else
17. {
18. if (p.value == 4 or 8 or 9 or 11 or 12) then
19. Exception Handler(no,p);
20. if(pcp==4) empty top();
21. if ((pcp>ocp)&(prp!=4)) then empty left();
22. if((pcp<ocp)&(prp!=4)) then empty right();
20. if((prp>orp)&(pcp==ocp)) then empty top();
22. }
23. }
24. }