Code to solve a http://en.wikipedia.org/wiki/15-puzzle (specific assignment (pdf)) using informed search techniques.
Easy explanation:
Solves puzzle by looking at current state's neighbors, picking the best (aka closest to solution, ranked by a particular function [total manhattan distance of the puzzle or # of tiles misplaced in the puzzle]) of the set of {current state's neighbors and the neighbors of other states we looked at previously} and if goal stop otherwise repeat. Thought it was neat.
Algorithms implemented:
http://en.wikipedia.org/wiki/A*
http://en.wikipedia.org/wiki/Best-first_search
Employing, for heuristics: http://en.wikipedia.org/wiki/Heuristics ... er_science [weights to determine what direction to try]
http://en.wikipedia.org/wiki/Manhattan_distance
# of misplaced tiles
Maybe more detail later. I haven't slept yet, and it's 730 AM. I get this way when I am working on something (and making progress).
Probably like 12 hours of work here (had to do a bit of finangling to figure out how the heap worked, wasn't sure if the answers all over the board was right, but I can't find any more errors). That and as you can see my operator== has some funky syntax, that's cause I was using pointer containers and I used STL's find() =p.
Would have (should have) used a priority_queue except I can't iterate through it to see if I've already added something. The vectors as heaps should act as a PQ.
http://www.sgi.com/tech/stl/make_heap.html
http://en.wikipedia.org/wiki/Heapsort
http://www.sgi.com/tech/stl/priority_queue.html
http://www.sgi.com/tech/stl/Vector.html
graph.h
Code: Select all
#ifndef GRAPH_H
#define GRAPH_H
#include "puzzle.h"
#include <vector>
using namespace std;
class Graph {
public:
//Employed using push_heap, pop_heap so they act as a PQ.
//STL priority_queue does not allow iterating through elements, which A* requires.
vector<PuzzleState*> openNodes;
vector<PuzzleState*> closedNodes;
bool Open(PuzzleState& p);
bool Close(PuzzleState* p);
PuzzleState* top();
Graph();
~Graph();
};
#endifCode: Select all
#include "puzzle.h"
#include "graph.h"
#include <vector>
#include <algorithm>
using namespace std;
/***Graph::Open(PuzzleState* p)***
If p is not in the 'open' list, it is added and true is returned.
Otherwise, if it is found, parent is set to p's parent if necessary,
depth is fixed, and false is returned.
****************************/
bool Graph::Open(PuzzleState& p) {
vector<PuzzleState*>::iterator found;
//Loop prevention
//(Generating its set of neighbors that are not on C)
found = find(closedNodes.begin(), closedNodes.end(), p);
if (found != closedNodes.end()) {
delete &p;
return false;
}
//For each element that IS on O, if the path through x to N is
//better than the currently known path, update g(x) := g(n) + d(n, x)
//and associate the pointer to N with X, update f^(x) = g(x) + h(x)
found = find(openNodes.begin(), openNodes.end(), p);
if (found != openNodes.end()) {
if ((*found)->getDepth() > p.getDepth()) {
(*found)->setParent(p.getParent());
(*found)->setDepth(p.getDepth());
(*found)->CalculateHeuristic();
}
delete (&p);
//Reorder O according to updated values of f^
make_heap(openNodes.begin(), openNodes.end(), PSGreater);
return false;
}
//For each node on M that is not on O, establish a pointer to N (constructor),
//set g(x) := g(n) + d(n,x) [constructor],
//set f^(x) = g(x) + h(x) [calculateHeuristic was called on generation (moveBlank)]
//Add our new one (or replace the old one)
openNodes.push_back(&p);
//Reorder O according to updated values of f^
push_heap(openNodes.begin(), openNodes.end(), PSGreater);
return true;
}
/***Graph::Close(PuzzleState* p)***
If p is not in the 'closed' list, it is added and true is returned.
Otherwise, false is returned.
*****************************/
bool Graph::Close(PuzzleState* p) {
vector<PuzzleState*>::iterator found;
pop_heap(openNodes.begin(), openNodes.end(), PSGreater);
found = find(openNodes.begin(), openNodes.end(), p);
openNodes.erase(found);
//make_heap(openNodes.begin(), openNodes.end(), PSGreater);
if (find(closedNodes.begin(), closedNodes.end(), p) != closedNodes.end())
return false;
closedNodes.push_back(p);
push_heap(closedNodes.begin(), closedNodes.end(), PSGreater);
return true;
}
//Returns top of openNodes (lowest f^ value)
PuzzleState* Graph::top() {
return *(openNodes.begin());
}
Graph::Graph() {
//Don't think this is necessary, but...
make_heap(openNodes.begin(), openNodes.end(), PSGreater);
make_heap(closedNodes.begin(), closedNodes.end(), PSGreater);
}
//Deallocates everything
Graph::~Graph() {
for (vector<PuzzleState*>::iterator i = openNodes.begin();i != openNodes.end();++i) {
delete (*i);
*i = NULL;
}
for (vector<PuzzleState*>::iterator i = closedNodes.begin();i != closedNodes.end();++i) {
delete (*i);
*i = NULL;
}
}Code: Select all
#ifndef PUZZLE_H
#define PUZZLE_H
#include <string>
using namespace std;
enum DIRECTION { NODIR = -1, UP, DOWN, LEFT, RIGHT, MAXDIR };
DIRECTION& operator++(DIRECTION& dir);
class Piece {
public:
int number;
Piece* neighbors[4];
Piece();
};
class PuzzleState {
const static int BOARD_WIDTH = 4;
const static int BOARD_HEIGHT = 4;
Piece board[BOARD_WIDTH][BOARD_HEIGHT]; //PuzzleState board, 0 == blank
int blankX, blankY; //Current coordinates of the blank tile
int heuristic;
int depth;
PuzzleState* parent;
void Swap(int x, int y);
int CalculateManhattan();
int CalculateMisplaced();
public:
bool useManhattan; //Determines what fn CalculateHeuristic() uses
//[ CalculateManhattan() vs CalculateMisplaced() ]
bool useAStar; //If false, then depth is ignored, making this into Best-First
PuzzleState();
PuzzleState(const PuzzleState& rhs);
bool MoveBlank(DIRECTION dir);
void Scramble(int moves);
int CalculateHeuristic();
string generateOutput();
//Accessors -----------
void setParent(PuzzleState* pparent) { parent = pparent; }
void setDepth(int pdepth) { depth = pdepth; }
PuzzleState* getParent() const { return parent; }
int getDepth() const { return depth; }
int getHeuristic() const { return heuristic; }
const int getBoardHeight() const { return BOARD_HEIGHT; }
const int getBoardWidth() const { return BOARD_WIDTH; }
friend bool operator==(const PuzzleState* lhs, const PuzzleState& rhs);
};
bool PSGreater(const PuzzleState* lhs, const PuzzleState* rhs);
#endif
Code: Select all
#include "puzzle.h"
#include <cstdlib> //rand, abs
#include <ctime> //time for rand
#include <string> //for puzzlestate::generateoutput
#include <sstream> //for puzzlestate::generateoutput
#include "graph.h" //for Scramble()...
#include <vector> //for Scramble()...
#include <algorithm> //for Scramble()...
#include <iostream>
using namespace std;
DIRECTION& operator++(DIRECTION& dir) {
return dir = (dir == MAXDIR) ? UP : DIRECTION(dir + 1);
}
/***Piece() [constructor]***
Sets piece to a blank
***************************/
Piece::Piece() {
number = 0;
}
/***PuzzleState() [constructor]***
Initializes PuzzleState board to ascending numerical order, blank tile at
bottom-right. Initializes relevant variables.
****************************/
PuzzleState::PuzzleState() {
Piece curPiece;
curPiece.number = 1;
for (int y = 0; y < BOARD_HEIGHT;y++) {
for (int x = 0; x < BOARD_WIDTH;x++) {
if (curPiece.number >= BOARD_HEIGHT * BOARD_WIDTH)
curPiece.number = 0;
board[x][y] = curPiece;
curPiece.number++;
}
}
parent = NULL;
blankX = BOARD_WIDTH-1;
blankY = BOARD_HEIGHT-1;
depth = 0;
useManhattan = true;
useAStar = true;
}
/***PuzzleState(const PuzzleState& rhs)***
Copies all members from rhs to *this
*****************************************/
PuzzleState::PuzzleState(const PuzzleState& rhs) {
for (int curY = 0; curY < BOARD_HEIGHT;curY++)
for (int curX = 0; curX < BOARD_WIDTH;curX++)
board[curX][curY].number = rhs.board[curX][curY].number;
//Establish a pointer to N,
//set g(x) := g(n) + d(n,x),
//set f^(x) = g(x) + h(x)
blankX = rhs.blankX;
blankY = rhs.blankY;
useAStar = rhs.useAStar;
useManhattan = rhs.useManhattan;
if (useAStar)
depth = rhs.depth+1; //g(x) := g(n) + d(n,x),
else
depth = 0;
parent = const_cast<PuzzleState*>(&rhs);
heuristic = rhs.heuristic;
CalculateHeuristic(); //f^(x) = g(x) + h(x), although a Move should be called or we have a duplicate, deeper state.
}
bool operator==(const PuzzleState* lhs, const PuzzleState& rhs) {
for (int curY = 0; curY < lhs->BOARD_HEIGHT; curY++) {
for (int curX = 0; curX < lhs->BOARD_WIDTH; curX++)
if (lhs->board[curX][curY].number != rhs.board[curX][curY].number)
return false;
}
return true;
}
bool PSGreater(const PuzzleState* lhs, const PuzzleState* rhs) {
return lhs->getHeuristic() > rhs->getHeuristic();
};
/***Swap(int x, int y)***
Swaps board[x][y] & board[blankX][blankY] whether the move is legal or not
************************/
void PuzzleState::Swap(int x, int y) {
Piece blank;
board[blankX][blankY] = board[x][y];
board[x][y] = blank;
blankX = x;
blankY = y;
CalculateHeuristic();
}
/***MoveBlank(DIRECTION dir)***
Swaps blank tile with the tile to its DIRECTION
Returns true on success.
******************************/
bool PuzzleState::MoveBlank(DIRECTION dir) {
if (dir == UP && blankY == 0)
return false;
if (dir == DOWN && blankY == BOARD_HEIGHT-1)
return false;
if (dir == LEFT && blankX == 0)
return false;
if (dir == RIGHT && blankX == BOARD_WIDTH-1)
return false;
int x = blankX;
int y = blankY;
if (dir == RIGHT)
x++;
else if (dir == LEFT)
x--;
else if (dir == UP)
y--;
else if (dir == DOWN)
y++;
else //NODIR
return false;
Swap(x, y);
return true;
}
/***isAdjacent(int x, int y)***
Returns direction to blank tile if blank is adjacent to board[x][y]
***************************/
/*DIRECTION PuzzleState::isAdjacent(int x, int y) {
for (int direction = 0;direction < (int)MAXDIR;direction++) {
if (board[x][y].neighbors[direction]->number == 0)
return (DIRECTION)direction;
}
return NODIR;
}*/
/***Scramble(int moves)***
Scrambles the PuzzleState by randomly moving the blank tile 'moves' spaces.
Records this amount in PuzzleState::scrambleMoves
Returns scrambleMoves.
*************************/
void PuzzleState::Scramble(int moves) {
int scrambleMoves = 0;
//Keep from getting same random # more than once
srand((unsigned int)time(NULL));
unsigned int lastRand = rand();
PuzzleState* test;
vector<PuzzleState*> states;
test = new PuzzleState(*this); //Initialize our test space
states.push_back(new PuzzleState(*this)); //Push a copy of the start state
cout << this->generateOutput();
while (scrambleMoves < moves) {
srand(lastRand + (unsigned int)time(NULL));
lastRand = rand();
//Don't move if the movement is already on the state list
//In other words, make sure the movments are contiguous.
//Guarantee that the move is legal
if (test->MoveBlank((DIRECTION)(lastRand % 4))) {
//Guarantee nonrepeating scramble
if (find(states.begin(), states.end(), *test) == states.end()) {
//Now that we have a move that wasn't on the state list, do the move
MoveBlank((DIRECTION)(lastRand % 4));
scrambleMoves++;
states.push_back(new PuzzleState(*this)); //Push a copy onto the state listing
cout << this->generateOutput();
}
}
//Reset test state to either 1) the not moved version or 2) the moved version of 'this'
delete test;
test = new PuzzleState(*this);
}
delete test;
test = NULL;
cout << "--------------" << endl;
for (vector<PuzzleState*>::iterator i = states.begin(); i != states.end(); ++i) {
delete (*i);
*i = NULL;
}
}
int PuzzleState::CalculateManhattan() {
// 1 2 3 4 % 4: 1 2 3 0, -1: 0 1 2 -1
// 5 6 7 8 % 4: 1 2 3 0
// 9 10 11 12 % 4
//13 14 15 00
int properx, propery;
int xdist, ydist;
heuristic = 0;
for (int y = 0;y < BOARD_HEIGHT;y++) {
for (int x = 0;x < BOARD_WIDTH;x++) {
properx = (board[x][y].number % BOARD_WIDTH)-1;
if (properx == -1)
properx = BOARD_WIDTH-1;
xdist = abs(x-properx);
if (board[x][y].number == 0)
propery = BOARD_HEIGHT-1;
else
propery = int( (board[x][y].number-1) / BOARD_HEIGHT);
ydist = abs(y-propery);
heuristic += xdist + ydist;
}
}
heuristic += depth;
return heuristic;
}
int PuzzleState::CalculateMisplaced() {
int curNumber = 1;
int misplaced = 0;
for (int curY = 0;curY < BOARD_HEIGHT;curY++) {
for (int curX = 0;curX < BOARD_WIDTH;curX++) {
if (board[curX][curY].number != curNumber)
misplaced++;
curNumber++;
if (curNumber == 16)
curNumber = 0;
}
}
heuristic = misplaced + depth;
return heuristic;
}
int PuzzleState::CalculateHeuristic() {
if (useManhattan)
return CalculateManhattan();
else
return CalculateMisplaced();
}
string PuzzleState::generateOutput() {
string retval;
for (int y = 0; y < BOARD_HEIGHT;y++) {
for (int x = 0; x < BOARD_WIDTH;x++) {
stringstream conv;
if (board[x][y].number < 10)
conv << " ";
conv << board[x][y].number;
retval += conv.str() + " ";
conv.clear();
}
retval += "\n";
}
retval += "---\n";
return retval;
}
Code: Select all
#include "puzzle.h"
#include "graph.h"
#include <vector>
#include <algorithm> //for make_heap, sort_heap, push_heap, pop_heap...
#include <iostream>
#include <string>
using namespace std;
int main() {
//Create lists Open & Closed
Graph g;
PuzzleState* start = new PuzzleState(); //Gets scrambled later
PuzzleState goal; //Unmodified PuzzleState, used to test for goal state
start->useAStar = true; //if false, best-first search is used
start->useManhattan = true; //if false, misplaced tiles is used
start->Scramble(5);//change this to change how many moves we scramble (you probably want to do <= 10)
//Put initial node on O
g.Open(*start);
//O can't be empty. If it could be, we would test for it & exit w/ fail here
PuzzleState* current;
PuzzleState* neighbor;
unsigned int examined = 0;
while (!g.openNodes.empty()) {
//Take 1st node, remove it from O, put it on C.
current = g.top();
g.Close(current);
examined++;
//If current is a goal, exit with success
if (current == goal) {
cout << "====" << endl;
int steps = -1;
string output = "";
PuzzleState* state = current;
while (state != NULL) {
steps++;
output = (state->generateOutput() + output);
state = state->getParent();
}
cout << output << endl;
cout << "Goal reached in " << steps << " moves." << endl;
cout << "There were " << examined << " states examined." << endl;
if (current->useAStar)
cout << "And a maximum depth of " << current->getDepth() << endl;
#ifdef _WIN32
system("pause");
#endif
return 0;
}
//Expand N, generating the set of its neighbors that are not on C, call it M.
//Add all neighbors to heap
for (DIRECTION dir = DIRECTION(NODIR+1);dir < MAXDIR;++dir) {
//For each node not in O, establish a pointer to N, ...
//Constructor: establish a pointer to N, g(x) := g(n) + d(n,x)
neighbor = new PuzzleState(*current);
if (neighbor->MoveBlank(dir)) //gen. child and f^(x) = g(x) + h(x)
g.Open(*neighbor);
else
delete neighbor;
}
}
cout << "No goal." << endl;
#ifdef _WIN32
system("pause");
#endif
return 1;
}Conclusions:
A* with misplaced tiles seems to be the best search method out of these, but if one wants to use best-first, Manhattan distance should be used to make it usable. Apparently, adding depth considerations to total Manhattan distance, as A* does, stops its effectiveness in general. Best-first using misplaced tiles is essentially useless, as it has a good chance of examining an unnecessarily large number of states, making it prohibitive on both time and memory constraints, and while best-first with Manhattan distance makes best-first usable, it is still not as consistently good as A* is.
-Alex (signing this in case my prof does a google search and my own post shows up ;) )
