C++

Forum

 
Code Review - Sliding puzzle with A*

Gigemaggies123 (3)
Howdy,

I'm a beginner programmer and new to the board. I have recently wrote a program for school, and I was hoping someone can look through it and point out things that I should change to improve my coding style and structure.

TIA

board.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
/*
 *  board.h
 *  hw1pr1
 *
 *  6/3/12.
 *  Copyright 2012. All rights reserved.
 *
 */
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
/*
 *  board.cpp
 *  hw1pr1
 *
 *  6/3/12.
 *  Copyright 2012. All rights reserved.
 *
 */


#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#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;
}
Volatile Pulse (1543)
Welcome to the forums, and just looking over your code, you code very similar to myself. The one thing I'd point out is that when I do classes, I like to have the class handle all of the math, converting, etc. IMHO, main.cpp should be as small as you can make with only asking for the input from the user. Also try doing some options, allow the user to input the puzzle information, or allow the computer to randomly generate it. Allow for read in from a text file so you can share puzzles with friends. You're off to a great start and when I sit down in front of my computer, I'll have to look at this. Good job.

Edit: another thing to think about is using a dynamic solver, don't force it to only solve for a certain grid size, but use vectors to allow for a 10x10 grid or whatever. The best way to get ahead is to try to implement your code to be more versatile, allow as many possibilities until you're completely satisfied
Last edited on
Gigemaggies123 (3)
Thanks for the reply, I would of added some more features but ran out of time. I will try to minimize the main in future programs. Thanks again
Topic archived. No new replies allowed.