I have searched the depths of the internet and I am yet to find a solution to my problem. I have implemented(I think) a BFS for the sliding tile game. However, It cannot solve a problem unless the state is a few steps away otherwise it just results in Out of Memory errors. So my question to you, where am I going wrong? AFAIK my code follows the BFS pseudo code.
EDIT/NOTE: I have stepped through with a debugger and have yet to find anything out of the ordinary to my eye but I am merely a novice programmer comparatively.
#include <ctime>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <deque>
#include <vector>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm: Breadth-First Search
//
// Move Generator:
//
////////////////////////////////////////////////////////////////////////////////////////////
class State{
public:
int state[9];
State(){
for (int i = 0; i < 9; i++){
state[i] = i;
}
}
State(string st){
for (int i = 0; i < st.length(); i++){
state[i] = st.at(i) - '0';
}
}
State(const State &st){
for (int i = 0; i < 9; i++){
state[i] = st.state[i];
}
}
bool operator==(const State& other) {
for (int i = 0; i < 9; i++){
if (this->state[i] != other.state[i]){return false;}
}
return true;
}
bool operator!=(const State& other) {
return !(*this == other);
}
void swap(int x, int y){
// State b; // blank state
// for (int i = 0; i < 9; i++) // fill blank state with current state
// b.state[i] = state[i];
int t = this->state[x]; // saves value of the value in position x of the state
this->state[x] = this->state[y]; // swaps value of position x with position y in the state
this->state[y] = t; // swaps value of position y with saved position x in the state
}
int findBlank(){ // finds position in 3x3 of blank tile
for (int i=0; i<9; i++){
if (state[i]==0) return i;
}
}
vector<State> blankExpand(){
int pos = this->findBlank();
vector<State> vecStates;
if (pos != 0 && pos != 1 && pos != 2){ // swaps the tile above it
State newState = State(*this);
newState.swap(pos,pos - 3);
vecStates.push_back(newState);
}
if (pos != 6 && pos != 7 && pos != 8){ // swaps the tile above it
State newState = State(*this);
newState.swap(pos,pos + 3);
vecStates.push_back(newState);
}
if (pos != 0 && pos != 3 && pos != 6){ // swaps the tile above it
State newState = State(*this);
newState.swap(pos,pos - 1);
vecStates.push_back(newState);
}
if (pos != 2 && pos != 5 && pos != 8){ // swaps the tile above it
State newState = State(*this);
newState.swap(pos,pos + 1);
vecStates.push_back(newState);
}
return vecStates;
}
};
string breadthFirstSearch_with_VisitedList(string const initialState, string const goalState){
string path;
clock_t startTime;
startTime = clock();
deque<State> nodesToVisit;
vector<State> visitedList;
int maxQLength = 0;
//Init
State init(initialState);
State goal(goalState);
nodesToVisit.push_back(init);
int count = 0;
int numOfStateExpansions = 0 ;
//
while (!nodesToVisit.empty()){
if(maxQLength < nodesToVisit.size()){maxQLength = nodesToVisit.size();}
State cur = nodesToVisit.front();
nodesToVisit.pop_front();
//remove front
if (cur == goal){
//solution found
cout << "solved!";
break;
}
//Get children
vector<State> children = cur.blankExpand();
numOfStateExpansions += children.size();
//For each child
for (State& child : children) {
for (int i = 0 ; i < 9;i++){
cout << child.state[i];
}
cout << " child" << endl;
//If already visited ignore
if (std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end()) {
// cout << "duplicate" << endl;
continue;
}
//If not in nodes to Visit
else if (std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()) {
//Add child
nodesToVisit.push_back(child);
}
}
visitedList.push_back(cur);
}
//***********************************************************************************************************
clock_t actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);
return path;
}
int main(){
breadthFirstSearch_with_VisitedList("042158367", "123804765");
//042158367
}
// 0 4 2
// 1 5 8
// 3 6 7
There are a number of inneficiencies in your code that are slowing it down. I'm actually surprised you had the patience to wait for it to reach an out-of-memory condition.
The main culprits are the searches:
std::find(visitedList.begin(), visitedList.end(), child) != visitedList.end()
//and
std::find(nodesToVisit.begin(), nodesToVisit.end(), child) == nodesToVisit.end()
Both of these execute in O(N), which sounds fine, but since you execute them on every node, that results in a O(N2).
You can fix this by using a std::unordered_set<> for the visitedList. Also, you could add nodes to the visited_list as soon as you queue them (instead of when you dequeue them). This way, you would only have a single lookup to do.
N.B. You will have to specialize std::hash<State> in order to use std::unordered_set.
One more hint: these cout << ... in your main loop really slow you down because they force a flush and sync with the OS by default, commenting these out will make your program run a lot faster.
There's actually quite a few more improvements that could be made in your code, but that's a topic for another day. Fixing the algorithmic complexity will bring it in the non-broken realm of things.