# Sliding block puzzle, A*

I'm a beginner programmer and I'm hoping someone would be willing to take a look at my code and tell me how to improve my coding style and development approach. Sorry about not commenting, I will try to get into the habit of commenting.

board.h

#include <iostream>
#include <vector>

using namespace std;

class board{
int values[5][5], blankX, blankY, parent, index, manhattan;

public:

board(int _values[5][5], int _blankX, int _blankY, int _index, int _parent);

void printBoard();
bool checkUp();
bool checkDown();
bool checkLeft();
bool checkRight();
void createChild(vector<board> &_children, int &_index, int &_count);
void exchangeUp();
void exchangeDown();
void exchangeLeft();
void exchangeRight();
int nextLevel(vector<board> &_children, int &_index, board _goal, int &parentCount);
void findSolution(vector<board> &_vector, int &_index, board _goal);
bool compare(board _goal);
int getParent(){return parent;};
void moveUp(){blankX--;};
void moveDown(){blankX++;};
void moveLeft(){blankY--;};
void moveRight(){blankY++;};
int getBlankX(){return blankX;};
int getBlankY(){return blankY;};
void setManhattan(board _goal);
int getManhattan(){return manhattan;};
};


board.cpp

#include "board.h"
#include <vector>

board::board(int _values[5][5], int _blankX, int _blankY, int _index, int _parent){
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
values[i][j]=_values[i][j];
}
}
blankX = _blankX;
blankY = _blankY;
index = _index;
parent = _parent;
}

void board::printBoard(){
for (int i=1; i<4; i++) {
for (int j=1; j<4; j++) {
cout << values[i][j]<<' ';
}
cout << '\n';
}
}

bool board::checkUp(){
if (values[blankX-1][blankY]==-1) {
return false;
}else {
return true;
}
}

bool board::checkDown(){
if (values[blankX+1][blankY]==-1) {
return false;
}else {
return true;
}
}

bool board::checkLeft(){
if (values[blankX][blankY-1]==-1) {
return false;
}else {
return true;
}
}

bool board::checkRight(){
if (values[blankX][blankY+1]==-1) {
return false;
}else {
return true;
}
}

void board::createChild(vector<board>& _children, int& _index, int & _count){
_children.push_back(board(values, blankX, blankY, index, _index));
_count++;
}

void board::exchangeUp(){
values[blankX][blankY]=values[blankX-1][blankY];
values[blankX-1][blankY]=0;
}

void board::exchangeDown(){
values[blankX][blankY]=values[blankX+1][blankY];
values[blankX+1][blankY]=0;
}

void board::exchangeLeft(){
values[blankX][blankY]=values[blankX][blankY-1];
values[blankX][blankY-1]=0;
}

void board::exchangeRight(){
values[blankX][blankY]=values[blankX][blankY+1];
values[blankX][blankY+1]=0;
}

int board::nextLevel(vector<board> &_vector, int &_index, board _goal, int &parentCount){

if(_vector[parentCount].checkUp()){
createChild(_vector, parentCount, _index);
_vector[_index].exchangeUp();
_vector[_index].moveUp();
_vector[_index].setManhattan(_goal);
board temp = _vector[_index];
board parent = _vector[getParent()];
if (temp.compare(_vector[parent.getParent()])) {
_vector.pop_back();
_index--;
}else if (temp.getManhattan()>parent.getManhattan()) {
_vector.pop_back();
_index--;
}
}

if(_vector[parentCount].checkDown()){
createChild(_vector, parentCount, _index);
_vector[_index].exchangeDown();
_vector[_index].moveDown();
_vector[_index].setManhattan(_goal);
board temp = _vector[_index];
board parent = _vector[getParent()];
if (temp.compare(_vector[parent.getParent()])) {
_vector.pop_back();
_index--;
}else if (temp.getManhattan()>parent.getManhattan()) {
_vector.pop_back();
_index--;
}
}

if(_vector[parentCount].checkLeft()){
createChild(_vector, parentCount, _index);
_vector[_index].exchangeLeft();
_vector[_index].moveLeft();
_vector[_index].setManhattan(_goal);
board temp = _vector[_index];
board parent = _vector[getParent()];
if (temp.compare(_vector[parent.getParent()])) {
_vector.pop_back();
_index--;
}else if (temp.getManhattan()>parent.getManhattan()) {
_vector.pop_back();
_index--;
}
}

if(_vector[parentCount].checkRight()){
createChild(_vector, parentCount, _index);
_vector[_index].exchangeRight();
_vector[_index].moveRight();
_vector[_index].setManhattan(_goal);
board temp = _vector[_index];
board parent = _vector[getParent()];
if (temp.compare(_vector[parent.getParent()])) {
_vector.pop_back();
_index--;
}else if (temp.getManhattan()>parent.getManhattan()) {
_vector.pop_back();
_index--;
}
}
return _index;
}

bool board::compare(board _goal){
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
if(values[i][j]!=_goal.values[i][j]){
return false;
}
}
}
return true;
}

void board::setManhattan(board _goal){
int manhatCounter = 0;
for (int i=1; i<4; i++) {
for (int j=1; j<4; j++) {
if(values[i][j]!=_goal.values[i][j]){
manhatCounter++;
}
}
}
manhattan = manhatCounter;
manhatCounter = 0;
}


main.cpp

#include <iostream>
#include <sstream>
#include <vector>
#include "board.h"

using namespace std;

int main (int argc, char * const argv[]) {
stringstream ss;
string initialState, goalState, test;
int tempStore, blankXstate, blankYstate;
vector<int> initialList;
vector<int> goalList;
int count = 0;
int count2 = 0;
int parentIndexCounter=0;
vector<board> tree;
int indexCount = 0;
int counter = 0;
vector<int> final;

cout << "Please enter the initial state with a number followed by a comma (0,1,2,3,4,5,6,7,8), no spaces.\n";
getline(cin, initialState);

ss << initialState;

while (ss >> tempStore) {
initialList.push_back(tempStore);

if(ss.peek() == ','){
ss.ignore();
}
}

ss.str("");
ss.clear();

cout << "Please enter the goal state with a number followed by a comma (0,1,2,3,4,5,6,7,8), no spaces.\n";
getline(cin, goalState);

ss << goalState;

while (ss >> tempStore) {
goalList.push_back(tempStore);

if(ss.peek() == ','){
ss.ignore();
}
}

int initialBoard[5][5];
int goalBoard[5][5];

for (int i=0; i<5; i++) {
if (i==0 || i==4) {
for (int j=0; j<5; j++) {
initialBoard[i][j] = -1;
}
}else {
initialBoard[i][0] = -1;
initialBoard[i][4] = -1;
}

}

for (int i=1; i<4; i++) {
for (int j=1; j<4; j++) {
initialBoard[i][j]=initialList[count];
if (initialBoard[i][j]==0) {
blankXstate = i;
blankYstate = j;
}
count++;
}
}

for (int i=0; i<5; i++) {
if (i==0 || i==4) {
for (int j=0; j<5; j++) {
goalBoard[i][j] = -1;
}
}else {
goalBoard[i][0] = -1;
goalBoard[i][4] = -1;
}

}

for (int i=1; i<4; i++) {
for (int j=1; j<4; j++) {
goalBoard[i][j]=goalList[count2];
count2++;
}
}
board firstCreatedBoard(initialBoard, blankXstate, blankYstate, 0, NULL);
board goalCreateBoard(goalBoard, NULL, NULL, NULL, NULL);
tree.push_back(firstCreatedBoard);
tree[0].setManhattan(goalCreateBoard);

vector <int> nodes;

for (int i=0; !(tree[i].compare(goalCreateBoard)); i++) {
tree[i].nextLevel(tree, indexCount, goalCreateBoard, parentIndexCounter);
parentIndexCounter++;
cout << "Generated " << parentIndexCounter - 1 << " states." << '\n';
counter = i + 1;
}

while (counter != -1) {
final.push_back(counter);
counter = tree[counter].getParent();
if (counter == 0) {
counter = -1;
}
}

final.push_back(0);
reverse(final.begin(),final.end());

for (int i = 0; i < final.size(); i++) {
cout << "Step " << i << '\n';
tree[final[i]].printBoard();
}
return 0;
}

• I am curious. Why do you use _parameter names? I have usually seen Object._member convention, (The given reason is that object members are from a non-local scope, and hence need to stand out). Jun 8, 2012 at 16:43
• Best not to use a leading underscore in identifier names: stackoverflow.com/a/228797/14065 Jun 8, 2012 at 18:33
• so should variables of board been declared with an _? Jun 10, 2012 at 17:42
• Would yall of went a different way about designing this program, I have a very weak concept of pointers, so instead of using them, I had every possible move pushed into a vector with their current index value and their parent index value. This made things a lot more complex as I had to depend on keeping very careful track of this index. As far as i know about pointers, you can find address location of a variable, but what good does knowing where it is in the memory do. Can someone give some examples of how to use pointers and cool pointers tricks? Thanks again everyone who answered Jun 10, 2012 at 17:59

### Style:

Why to many get/set (ers).
Your methods should be actions that perform actions on your object and mutate state. You should not expose your state (even through getters) as this binds your implementation (tightly couples) your implementation to that interface.

### Code:

This:

bool board::checkUp(){
if (values[blankX-1][blankY]==-1) {
return false;
}else {
return true;
}
}


Is easier to write (and read) as:

bool board::checkUp() { return values[blankX-1][blankY] != -1;}


And this:

void board::exchangeUp(){
values[blankX][blankY]=values[blankX-1][blankY];
values[blankX-1][blankY]=0;
}


void board::exchangeUp()
{
std::swap(values[blankX][blankY], values[blankX-1][blankY]);
--blankX;
}


But why are you allowing an external entity to blindly change your state. You need to validate that the move is good. You should never trust the code using you to blindly always be correct. Validate the move.

### Exposing State

void board::createChild(vector<board>& _children, int& _index, int & _count){
_children.push_back(board(values, blankX, blankY, index, _index));
_count++;
}


To me the vector<board> should be a private member (or method member) of the board used for solving the problem. You should not be passing this in from the outside. Also the count variable seems redundant. The count will be equivalent to size() of the vector.

### Printing

It's ok to have a print method. But you should pass it the stream you want to print too.

void board::printBoard(std::ostream& out) const


I would also add your own custom operator<< to make sure your object can be printed like other objects. It also helps with standard algorithms where you can use the operator<< in a standard way for printing serialization etc.

std::ostream& operator<<(std::ostream& stream, board const& data)
{
data.printBaord(stream);
return stream;
}

• So is it bad in coding to have unnecessary public functions/objects? This is not something that I've actively tried to hide, but I will from now on. Also the rewriting of the code makes sense. The exchange of the state is only called later on when the checkUp is true I.E. checkUP -> true then exchange up. So I've broken up some steps that could have been combined. Would it of been best to rewrote it to where check and exchange are the same functions? Lastly, I've heard of overloading? operators but have never really fully understood how to use them. Thank you for taking the time and helping Jun 10, 2012 at 17:50
• Yes. Minimize your exposed public interface (public interface are all the methods in public/protected). Never put member variables anywhere but private. Always validate untrusted data. operator overloading is when you write your owne version of +/-/*/ etc. It is not recommended. Unless you are writing a new class that represents a number. function overloading may be what you mean. This is where you have multiple functions with the same name (buf different parameters). Jun 10, 2012 at 18:17

Just a few things I noticed which may be of use in the future. All these items come from the amazing book by Scott Meyers' Effective C++ which I recommend you get if you want to improve your coding standards!

# Use const whenever possible

This not only allows you a semantic constraint (item within this cannot be modified), but allows you to communicate to both to compiler and any other programmer who may use your code!

So for example, a lot of your methods could use the following:

void PrintBoard() const;


This particular example doesn't really effect anything, but will generally help the compiler. You can see a better example when looking at inspectors or mutators (get/sets):

void Mutator(const int val)       { _memberVal = val; }
int Inspector()             const { return _memberVal; }


Mutator: Not only does it tell the programmer that the inputted value does not change within the method, but with the lack of const at the end of the method it tells us that there will a change of data within the class

Inspector: With the const at the end of the method, it tells not only the programmer but also the compiler that there will be no change to the data within the class.

# Make sure that objects are initialized before they're used

It's good to see that inside your constructor that you have initialized all the items, including the array, but there is another, more efficient, way of doing this with the use of initialization lists. For example:

board::board(int _values[5][5], int _blankX, int _blankY, int _index, int _parent)
: blankX(_blankX), blankY(_blankY), parent(_parent), index(_index)
{
// Initialize the array here
}


The reason this is more efficient is mainly due to how the different types of constructors work with assignments.

If anything else pops into mind I will post again!

• +1. But had to fixe your usage of const. Note there is no point in const when returning by value. Jun 8, 2012 at 18:34
• Avoid get/set (ers) they tightly couple your code to a particular implementation. In OO you ask the object to mutate its own state by asking it to perform an action (ie your methods should be verbs). You should not be providing state for sombody else to act on you that is very close to breaking encapsulation (but is tightly coupling). Jun 8, 2012 at 18:36
• There is no point from what can see but does help the compiler. Also, it stops silly errors like... (ab) = c, or even better example... if(ab = c) when doing comparison Jun 8, 2012 at 19:31
• @D Hansen: You are misreading "Scott's Book". Your comments are correct if the result was returned by reference. But in this case they are not (they are returned by value). Thus the result of the method call is not an r-value and thus not susceptible to the assignment problem. Jun 8, 2012 at 19:50
• @LokiAstari My mistake haha, Not having a good thinking day today :) Jun 8, 2012 at 20:14