Share 8 puzzle problem using an* algorithm in c++,

[trongchinh839]

#8puzz, #astar, #C ++, #AlGorithM
## 8 Vấn đề câu đố bằng thuật toán \* trong C ++

8 vấn đề câu đố là một vấn đề kinh điển trong khoa học máy tính.Đó là một câu đố trong đó bạn có một lưới gạch 3x3 và một trong các ô bị thiếu.Mục tiêu của câu đố là di chuyển các gạch xung quanh để chúng theo đúng thứ tự, với gạch trống ở góc dưới bên phải.

Thuật toán A \* là một thuật toán tìm kiếm heuristic có thể được sử dụng để giải quyết vấn đề 8 câu đố.Nó hoạt động bằng cách lặp đi lặp lại một cây gồm các quốc gia có thể và chọn trạng thái có khả năng dẫn đến một giải pháp.Thuật toán A \* được đảm bảo để tìm giải pháp cho 8 vấn đề câu đố, nếu một người tồn tại.

Mã sau đây cho thấy cách thực hiện thuật toán A \* trong C ++ để giải quyết vấn đề 8 câu đố:

`` `C ++
#include <Istream>
#include <Vector>

sử dụng không gian tên STD;

// Một cấu trúc dữ liệu để thể hiện trạng thái của 8 câu đố
struct state {
Gạch int [3] [3];
int blank_row;
int blank_col;
};

// một chức năng để kiểm tra xem một trạng thái có phải là trạng thái mục tiêu không
bool is_goal_state (const state & state) {
for (int i = 0; i <3; i ++) {
for (int j = 0; j <3; j ++) {
if (state.tiles [j]! = (i * 3) + j + 1) {
trả lại sai;
}
}
}
trả lại đúng;
}

// một chức năng để có được hàng xóm của một tiểu bang
Vector <tate> get_neighbors (const State & State) {
Vector <Tate> Hàng xóm;

// Nhận hàng và cột của gạch trống
int blank_row = state.blank_row;
int blank_col = state.blank_col;

// Nhận hàng xóm của gạch trống
if (blank_row> 0) {
hàng xóm.push_back (state {state.tiles, blank_row - 1, blank_col});
}
if (blank_row <2) {
hàng xóm.push_back (state {state.tiles, blank_row + 1, blank_col});
}
if (blank_col> 0) {
hàng xóm.push_back (state {state.tiles, blank_row, blank_col - 1});
}
if (blank_col <2) {
hàng xóm.push_back (state {state.tiles, blank_row, blank_col + 1});
}

trở về hàng xóm;
}

// một chức năng để tính giá trị heuristic của một trạng thái
int heuristic_value (const state & state) {
int h = 0;

// Đối với mỗi ô, hãy tính khoảng cách giữa vị trí hiện tại và vị trí mục tiêu của nó
for (int i = 0; i <3; i ++) {
for (int j = 0; j <3; j ++) {
int dự kiến_value = (i * 3) + j + 1;
int thực tế_value = state.tiles [j];
h += abs (dự kiến_value - thực tế_value);
}
}

trả lại h;
}

// Thuật toán A \*
Trạng thái a_star (const state & init_state) {
// Tạo hàng đợi ưu tiên để lưu trữ các trạng thái được mở rộng
ưu tiên_queue <state, vector <tate>, lớn hơn <state >> biên giới;

// Khởi tạo biên giới với trạng thái ban đầu
frontier.push (init_state);

// Tạo một bộ để lưu trữ các trạng thái đã truy cập
Đặt <Tate> đã truy cập;

// trong khi biên giới không trống
while (! frontier.empty ()) {
//
=======================================
#8puzzle, #astar, #C++, #AlGorithM
## 8 Puzzle Problem using A\* Algorithm in C++

The 8 puzzle problem is a classic problem in computer science. It is a puzzle where you have a 3x3 grid of tiles, and one of the tiles is missing. The goal of the puzzle is to move the tiles around so that they are in the correct order, with the blank tile in the bottom right corner.

The A\* algorithm is a heuristic search algorithm that can be used to solve the 8 puzzle problem. It works by iteratively expanding a tree of possible states, and choosing the state that is most likely to lead to a solution. The A\* algorithm is guaranteed to find a solution to the 8 puzzle problem, if one exists.

The following code shows how to implement the A\* algorithm in C++ to solve the 8 puzzle problem:

```c++
#include <iostream>
#include <vector>

using namespace std;

// A data structure to represent a state of the 8 puzzle
struct State {
int tiles[3][3];
int blank_row;
int blank_col;
};

// A function to check if a state is a goal state
bool is_goal_state(const State& state) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (state.tiles[j] != (i * 3) + j + 1) {
return false;
}
}
}
return true;
}

// A function to get the neighbors of a state
vector<State> get_neighbors(const State& state) {
vector<State> neighbors;

// Get the row and column of the blank tile
int blank_row = state.blank_row;
int blank_col = state.blank_col;

// Get the neighbors of the blank tile
if (blank_row > 0) {
neighbors.push_back(State{state.tiles, blank_row - 1, blank_col});
}
if (blank_row < 2) {
neighbors.push_back(State{state.tiles, blank_row + 1, blank_col});
}
if (blank_col > 0) {
neighbors.push_back(State{state.tiles, blank_row, blank_col - 1});
}
if (blank_col < 2) {
neighbors.push_back(State{state.tiles, blank_row, blank_col + 1});
}

return neighbors;
}

// A function to calculate the heuristic value of a state
int heuristic_value(const State& state) {
int h = 0;

// For each tile, calculate the distance between its current position and its goal position
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int expected_value = (i * 3) + j + 1;
int actual_value = state.tiles[j];
h += abs(expected_value - actual_value);
}
}

return h;
}

// The A\* algorithm
State a_star(const State& initial_state) {
// Create a priority queue to store the states to be expanded
priority_queue<State, vector<State>, greater<State>> frontier;

// Initialize the frontier with the initial state
frontier.push(initial_state);

// Create a set to store the visited states
set<State> visited;

// While the frontier is not empty
while (!frontier.empty()) {
//