Using BFS in a simple Rush Hour solver - why is my code not solving the board?

Question

UPDATE - The main problem was solved by a replier below (I had a '=' where I should have had a '=='), but now I am getting the wrong output. I thought I would provide some input/output examples as suggested so maybe someone out there can spot where I'm going wrong.

Say I enter the input:

......

......

xx....

......

......

......

This should produce the output:

4

x r

x r

x r

x r

to signify x got to the most right spot of the 3rd row in 4 moves, and x had to be moved right each move.

Instead, I get the output:

3

x r

x l

x r

In the code below, the program accepts a 6x6 block of characters to represent the game board. (periods are empty spaces, characters represent cars.) The work done in the board class and main function are correct, as I had it verified with my professor. However, I am trying to correct my output. I know my logic used in the solve function isn't the best approach for this, but I have to try and make it work so I can get points back without copying the professor's solution.

#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <list>

using namespace std;

class board
{
public:
board() {count = 0;}

bool isSolved()
{
    return currState[17] = 'x';
}

string currState;
string moveList;
int count;
};

bool operator < (const board& board1, const board& board2)
{
return board1.currState < board2.currState;
}

void solve (const board& curr, int i, list<board>& toTest, const set<board>& testedSet, bool vert)
{
board newMove(curr);

if (vert == false)
{
if (i % 6 == 0 && curr.currState[i] != '.')
{
    if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.')
    {
        newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
        newMove.currState[i+2] = newMove.currState[i];
        newMove.currState[i] = '.';
        newMove.count++;
    }

    if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.')
    {
        newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
        newMove.currState[i+3] = newMove.currState[i];
        newMove.currState[i] = '.';     
        newMove.count++;
    }
}

else if ((i + 1) % 6 == 0 && curr.currState[i] != '.')
{
    if (curr.currState[i] == curr.currState[i-1] && curr.currState[i-2] == '.')
    {
        newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
        newMove.currState[i-2] = newMove.currState[i];
        newMove.currState[i] = '.';
        newMove.count++;
    }

    if (curr.currState[i] == curr.currState[i-1] && curr.currState[i] == curr.currState[i-2] && curr.currState[i-3] == '.')
    {
        newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
        newMove.currState[i-3] = newMove.currState[i];
        newMove.currState[i] = '.';
        newMove.count++;
    }
}

else
{
    if (i % 2 != 0 && i % 3 != 0 && curr.currState[i] != '.')
    {
        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
            newMove.currState[i-1] = newMove.currState[i];
            newMove.currState[i+1] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
            newMove.currState[i+2] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i-1] == '.' && curr.currState[i+3] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
            newMove.currState[i-1] = newMove.currState[i];
            newMove.currState[i+2] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.' && curr.currState[i-1] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
            newMove.currState[i+3] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }
    }

    if (i % 2 == 0 && (i + 2) % 6 != 0 && curr.currState[i] != '.')
    {

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
            newMove.currState[i-1] = newMove.currState[i];
            newMove.currState[i+1] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
            newMove.currState[i+2] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.' && curr.currState[i-1] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
            newMove.currState[i+3] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }
    }

    if (i % 3 == 0 && curr.currState[i] != '.')
    {
        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
            newMove.currState[i-1] = newMove.currState[i];
            newMove.currState[i+1] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
            newMove.currState[i+2] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }
    }
}
}

if (vert == true)
{
    if (i < 17)
    {
        if (curr.currState[i] == curr.currState[i+6] && curr.currState[i] == curr.currState[i+12] && curr.currState[i+18] == '.')
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "d" + "\n";
            newMove.currState[i+18] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i+6] && curr.currState[i+12] == '.')
        {
            if (i < 6 || curr.currState[i] != curr.currState[i-6])
            {
                newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "d" + "\n";
                newMove.currState[i+12] = newMove.currState[i];
                newMove.currState[i] = '.';
                newMove.count++;
            }
        }
    }

    if (i > 17)
    {
        if (curr.currState[i] == curr.currState[i-6] && curr.currState[i] == curr.currState[i-12] && curr.currState[i-18] == '.')
        {
            newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "u" + "\n";
            newMove.currState[i-18] = newMove.currState[i];
            newMove.currState[i] = '.';
            newMove.count++;
        }

        if (curr.currState[i] == curr.currState[i-6] && curr.currState[i-12] == '.')
        {
            if (i > 29 || curr.currState[i] != curr.currState[i+6])
            {
                newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "u" + "\n";
                newMove.currState[i-12] = newMove.currState[i];
                newMove.currState[i] = '.';
                newMove.count++;
            }
        }
    }



}

if (testedSet.find(newMove) == testedSet.end())
    toTest.push_back(newMove);
}

int main()
{
list<board> toBeTested;
string input;
board current;
set<board> tested;
bool vertical = false;

for (int i = 0; i < 6; i++)
{
    getline(cin, input);
    current.currState += input;
}

toBeTested.push_back(current);

while (toBeTested.size() > 0 && current.isSolved() == false)
{
    current = toBeTested.front();
    toBeTested.pop_front();

    if (current.isSolved() == false && tested.find(current) == tested.end())
    {
        tested.insert(current);

        for (int i = 0; i < 36; i++)
        {
            solve(current, i, toBeTested, tested, vertical);
            vertical = true;
            solve(current, i, toBeTested, tested, vertical);
            vertical = false;
        }

    }
}

if (current.isSolved() == false)
    cout << current.count << endl << current.moveList;
else
    cout << -1 << endl;

return 0;
}

`return currState[17] = 'x';` should probably be `return currState[17] == 'x';` — Daniel Trebbien, Dec 09 '12 at 18:56
It would help if you can provide some sample input and output. — axiom, Dec 09 '12 at 18:58
Ok. Yes. That helped immensely. lol. Can't believe I'm that big of an idiot, but I guess it always helps to have someone spot mistakes like that. Thank you. Of course that solved the -1 problem, but now I'm getting straight up wrong answers. For instance, when I enter the grid with just two x's on the front of the 3rd row, the output should read "4" (it should take 4 moves to get x to spot 17) and "x r x r x r x r". Instead it reads 3 moves, and "x r x l x r" — The Rationalist, Dec 09 '12 at 19:03

score 0 · Accepted Answer · edited May 23 '17 at 12:00

It is difficult to figure out what you are trying to do here because many values are hard-coded and there is not a lot of abstraction used in the program.

I am guessing that you are trying to do something like http://www.theiling.de/projects/rushhour.html where the input is a board like:

aaobcc
..ob..
xxo...
deeffp
d..k.p
hh.k.p

If you make the correction to board::isSolved() from my comment:

bool isSolved()
{
    return currState[17] == 'x';
}

You will at least get something other than -1:

10
b d
c l
h r
p u
p u
p u
f r
k u
h l
h r

However, this is not a solution to the input problem.

It does not look like you are computing the next states correctly. There should be a loop to iterate over each piece of a vehicle after a vehicle is moved.

Definitely try abstracting more details. For example, perhaps you can add methods to board for (1) computing a list of valid moves and (2) applying a single move, returning a new board. Also, if you haven't learned how to use a debugger such as gdb, now would be an excellent time to start learning. See How do I use the MinGW gdb debugger to debug a C++ program in Windows?

You are correct, and I do apologize for the sloppy code. I guess I will trace the solve function to see where I went wrong. Thank you for your great suggestions. — The Rationalist, Dec 09 '12 at 19:14
@TheRationalist: By the way, there is an excellent free course from BerkeleyX (part of [edX](https://www.edx.org)) on artificial intelligence: [CS188.1x: Artificial Intelligence](https://www.edx.org/courses/BerkeleyX/CS188.1x/2012_Fall/about). The course has ended, but you can still register and learn the material. The first week is on search algorithms BFS, DFS, uniform cost, and A*. If you complete the first programming project, you will see a great example of abstracting away details in search problems. — Daniel Trebbien, Dec 09 '12 at 19:25

Using BFS in a simple Rush Hour solver - why is my code not solving the board?

1 Answers1