Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# A* and IDA* searches to solve a Sliding-Block puzzle

By: a guest on Dec 6th, 2010  |  syntax: C++  |  size: 3.40 KB  |  views: 1,279  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. class Compare
2. {
3. public:
4.  bool operator()(shared_ptr<Puzzle> puzzA, shared_ptr<Puzzle> puzzB)
5.  {
6.          if (Search::F(puzzA) > Search::F(puzzB))
7.                 return true;
8.         else
9.                 return false;
10.
11.  }
12. };
13.
14. shared_ptr<Puzzle> Search::AStar(shared_ptr<Puzzle> puzzle)
15. {
16.         //Phase IV: A* Graph Search.
17.         shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
18.         priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
19.         set<string> closedlist;
20.
21.         fringe.push(puzzle);
22.         while (!fringe.empty())
23.         {
24.                 shared_ptr<Puzzle> current = fringe.top();
25.                 fringe.pop();
26.                 if (current->isSolved())
27.                 {
28.                         solution = current;
29.                         break;
30.                 }
31.                 else
32.                 {
33.                         if (!closedlist.count(current->uniqueID())) //if not in closedlist
34.                         {
35.                                 closedlist.insert(current->uniqueID());
36.                                 vector<shared_ptr<Puzzle> > successors = current->Successors();
37.                                 vector<shared_ptr<Puzzle> >::iterator it;
38.                                 for (it = successors.begin(); it != successors.end(); it++)
39.                                 {
40.                                         if (!closedlist.count((*it)->uniqueID()))
41.                                         {
42.                                                 if ((*it)->isSolved())
43.                                                         return (*it);
44.                                                 else
45.                                                         fringe.push((*it)); //add successor if not in closedlist
46.                                         }
47.                                 }
48.                         }
49.                 }
50.         }
51.         return solution;
52. }
53.
54.
55. int Search::heuristic(shared_ptr<Puzzle> puzzle)
56. {
57.         //h(n); Manhattan distance heuristic.
58.         int distance = 0;
59.         int counter = 1;
60.         for (int i = 1; i < puzzle->N+1; i++)
61.         {
62.                 for (int j = 1; j < puzzle->N+1; j++)
63.                 {
64.                         //For each block in order:
65.                         //Look at its coordinates.
66.                         //What's the difference along each axis to the correct place?
67.                         int diffx = abs(i - puzzle->index[counter]->posX);
68.                         int diffy = abs(j - puzzle->index[counter]->posY);
69.                         int manhattan = diffx + diffy;
70.                         distance += manhattan;
71.                         counter++;
72.                 }
73.         }
74.         return distance;
75. }
76.
77. int Search::pathCost(shared_ptr<Puzzle> puzzle)
78. {
79.         //g(n); Path cost function. Distance from initial to current state.
80.         //We count the number of moves made so far.
81.         return puzzle->moveQueue.size();
82. }
83.
84. int Search::F(shared_ptr<Puzzle> puzzle)
85. {
86.         //f(n) Total cost; used by A*.
87.         //f(n) = g(n) + h(n)
88.         return pathCost(puzzle) + heuristic(puzzle);
89. }
90.
91. shared_ptr<Puzzle> Search::IDAStar(shared_ptr<Puzzle> puzzle)
92. {
93.         //Phase IV Bonus: Iterative Deepening A* Graph Search.
94.         shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
95.         priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
96.         set<string> closedlist;
97.
98.         int Flimit = 0;
99.         while (!solution)
100.         {
101.                 Flimit++;
102.                 //cout << "Current F limit: " <<Flimit <<endl;
103.                 closedlist.clear();
104.                 while (!fringe.empty())
105.                         fringe.pop(); //empty the fringe
106.                 fringe.push(puzzle);
107.                 while (!fringe.empty())
108.                 {
109.                         shared_ptr<Puzzle> current = fringe.top();
110.                         fringe.pop();
111.                         if (current->isSolved())
112.                         {
113.                                 solution = current;
114.                                 break;
115.                         }
116.                         else
117.                         {
118.                                 if (!closedlist.count(current->uniqueID())) //if not in closedlist
119.                                 {
120.                                         closedlist.insert(current->uniqueID());
121.                                         if (F(current) < Flimit) //if within F limit
122.                                         {
123.                                                 vector<shared_ptr<Puzzle> > successors = current->Successors();
124.                                                 vector<shared_ptr<Puzzle> >::iterator it;
125.                                                 for (it = successors.begin(); it != successors.end(); it++)
126.                                                 {
127.                                                         if (!closedlist.count((*it)->uniqueID()))
128.                                                         {
129.                                                                 if ((*it)->isSolved())
130.                                                                         return (*it);
131.                                                                 else
132.                                                                         fringe.push((*it)); //add successor if not in closedlist
133.                                                         }
134.                                                 }
135.                                         }
136.                                 }
137.                         }
138.                 }
139.         }
140.         return solution;
141. }
clone this paste RAW Paste Data
Top