I'm learning AI and tried to make simple solver for 8-puzzle with A* search. The structure of the program is very simple. I have state structure and priority_queue where I keep unexplored states in order and closed_list that is a vector of lists (index i contains those explored states that have Manhattan distance equal to i so we can tighten the search). For some reason, all initial states seem to be impossible to solve. This makes me to believe that there is something vital i'm missing. Any help would be useful!
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <list>
#include <assert.h>
#define N 9 // number of squares in the board
#define WIDTH 3 // width of 3x3 8-puzzle board
#define UB 35 // upper bound for estimate
typedef struct state {
unsigned board[N]; // flattened 3x3 board
unsigned moves; // accumulated cost of current state (g(n))
unsigned heur; // h(n)
unsigned estimate; // f(n) = g(n) + h(n)
unsigned empty_sqr; // location (index) of the empty square
struct state *prev; // the previous state
/* Checks if the board configuration matches the goal */
bool at_goal() const noexcept //
{
return (board[0] == 1 && board[1] == 2 && board[2] == 3 \
&& board[3] == 4 && board[4] == 5 && board[5] == 6 \
&& board[6] == 7 && board[7] == 8 && board[8] == 0);
}
/* Checks if this board configuration already been expanded */
bool already_visited(std::vector<std::list<state*>> &closed_list) const noexcept
{
if (closed_list[heur].empty()) return false; // if there are no entries in this list return false (=> new state)
// Iterate over all previously expanded states and see if there is
for(auto it = closed_list[heur].begin(); it != closed_list[heur].end(); ++it) {
if(this->compare_boards((*it)->board) && this->moves >= (*it)->moves) return true;
}
return false;
}
/* Compares two boards, returns true if they match and false otherwise */
bool compare_boards(const unsigned B[]) const noexcept
{
return (board[0] == B[0] && board[1] == B[1] && board[2] == B[2] \
&& board[3] == B[3] && board[4] == B[4] && board[5] == B[5] \
&& board[6] == B[6] && board[7] == B[7] && board[8] == B[8]);
}
} state;
/* This function decides if given board configuration has a solution */
bool is_solvable(const unsigned board[]) {
unsigned row[(WIDTH*WIDTH)-1];
unsigned rowIndex = 0;
for (unsigned i = 0; i < WIDTH; ++i) {
for (unsigned j = 0; j < WIDTH; ++j) {
if (board[WIDTH*i + j]) {
row[rowIndex] = board[WIDTH*i + j];
rowIndex++;
}
}
}
unsigned inversions = 0;
for (unsigned x = 0; x < (WIDTH*WIDTH-1); ++x) {
for (unsigned y = x; y < (WIDTH*WIDTH-1); ++y)
if (row[x] > row[y]) {
inversions++;
}
}
return (inversions % 2 == 0);
}
/* Overloaded comparison operator for for our priority queue (non-decreasing order) */
struct comparator {
bool operator() (const state *a, const state *b) {return (a->estimate > b->estimate);}
};
/* This function computes the manhattan distance of a given board configuration */
unsigned manhattan_dist(const unsigned board[])
{
unsigned val = 0;
for(unsigned i = 0; i < N; ++i) {
if(board[i]) {
val += (abs((board[i] - 1) / 3 - i / 3) + abs((board[i] - 1) % 3 - i % 3));
}
}
return val;
}
/* This function generates new state, given the parent and the move action */
void generate_state(unsigned new_idx, unsigned old_idx, state *curr, std::priority_queue<state* , std::vector<state*>, comparator> &Q, std::vector<state*> &memory)
{
state *temp = new state; // generate new state
temp->prev = curr; // set the predecessor state to point this state
temp->empty_sqr = new_idx; // change the position of the empty square
memcpy(temp->board, curr->board, sizeof(curr->board)); // copy old board to new state
temp->board[old_idx] = curr->board[new_idx]; // swap numbered tile to previous position of the empty sqr
temp->board[new_idx] = 0; // set the empty sqr to the new move position
temp->moves = curr->moves + 1; // increment the num of moves
temp->heur = manhattan_dist(temp->board); // heuristic value for given board configuration
temp->estimate = temp->moves + temp->heur; // compute new estimate to goal
Q.push(temp); // push to priority queue
memory.push_back(temp); // add pointer to memory database
}
void find_neighbours(state* curr, std::priority_queue<state* , std::vector<state*>, comparator> &Q, std::vector<state*> memory)
{
unsigned new_row, new_col, new_idx; // Initialized variables for new positions of the empty square
unsigned empty_square = curr->empty_sqr; // extract the position of the empty square
unsigned row = empty_square / 3; // in what row (0, 1 or 2) the empty square is
unsigned col = empty_square % 3; // in what column (0, 1 or 2) the empty square is
/* Possible new states are are found when we more up, down, left or right the empty square.
* We must check if these moves are valid in each case (i.e. moving empty square out of board bounds must be prohibited)
* CASE 1
* Move empty square up i.e. row number of empty sqr := row number of empty sqr - 1 */
if (row) {
new_row = row-1;
new_col = col;
new_idx = new_row*WIDTH + new_col;
generate_state(new_idx, empty_square, curr, Q, memory);
}
/* CASE 2
* Move empty square down i.e. row number of empty sqr := row number of empty sqr + 1 */
if (row < 2) {
new_row = row+1;
new_col = col;
new_idx = new_row*WIDTH + new_col;
generate_state(new_idx, empty_square, curr, Q, memory);
}
/* CASE 3
* Move empty square right i.e. column number of empty sqr := column number of empty sqr + 1 */
if (col < 2) {
new_row = row;
new_col = col+1;
new_idx = new_row*WIDTH + new_col;
generate_state(new_idx, empty_square, curr, Q, memory);
}
/* CASE 4
* Move empty square left i.e. column number of empty sqr := column number of empty sqr - 1 */
if (col) {
new_row = row;
new_col = col-1;
new_idx = new_row*3 + new_col;
generate_state(new_idx, empty_square, curr, Q, memory);
}
}
state* solver(state* initial, std::vector<state*> &memory)
{
std::priority_queue<state* , std::vector<state*>, comparator> Q; // priority queue for board state pointers
std::vector<std::list<state*>> closed_list(UB, std::list<state*>()); // vector of lists that hold those states that has been expanded
state *best_state = NULL; // holder for the current best state that has reached the goal
state *current_state; // temporary holder for board states
Q.push(initial); // push the initial state into the priority queue
unsigned iter = 0;
while(!Q.empty()) {
current_state = Q.top(); // remove the current best state based on the f-value
Q.pop(); // remove it from the priority queue
if(current_state->at_goal()) { // If we have reached the goal, return the path to goal
best_state = current_state;
return best_state;
}
if(current_state->already_visited(closed_list)) // If board has already visited, with better score, continue
continue;
assert(current_state->heur <= UB && current_state->heur >= 0);
closed_list[current_state->heur].push_back(current_state); // push current state to "seen" list at the position of its manhattan distance
find_neighbours(current_state, Q, memory); // Find neighbouring (up,down,right,left) states of this configuration.
iter++;
}
return best_state;
}
void print_board(const unsigned board[])
{
for(unsigned i = 0; i < WIDTH; ++i) {
for(unsigned j=0; j < WIDTH; ++j) {
printf("%d ", board[i*WIDTH + j]);
}
printf("\n");
}
printf("\n");
}
void print_path(state *s)
{
while(s) {
print_board(s->board);
s = s->prev;
}
}
int main() {
std::vector<state*> memory;
unsigned arr[9] = {4,5,0,6,8,7,1,2,3};
state *s1 = new state;
memory.push_back(s1);
s1->prev = NULL;
s1->empty_sqr = 0;
memcpy(s1->board, arr, sizeof(arr));
s1->moves = 0;
s1->heur = manhattan_dist(s1->board);
s1->estimate = s1->moves + s1->heur;
state *best = solver(s1, memory);
if(best) {
std::cout << "Solution found in " << best->moves << " moves" << std::endl;
print_path(best);
}
else
std::cout << "No solution found..." << std::endl;
for(auto iter = memory.begin(); iter != memory.end(); ++iter)
delete(*iter);
return 0;
};
What happens is that the open_list runs empty before we find the optimal solution.
Aucun commentaire:
Enregistrer un commentaire