honglinhgambit
New member
## 8 Nữ hoàng trong C ++
Vấn đề 8 Queens là một vấn đề kinh điển trong khoa học máy tính.Đó là một vấn đề hoàn thành NP, có nghĩa là không có thuật toán thời gian đa thức được biết đến để giải quyết nó.Tuy nhiên, có một số thuật toán hiệu quả có thể được sử dụng để tìm giải pháp cho vấn đề.
Trong bài viết này, chúng tôi sẽ chỉ ra cách giải quyết vấn đề 8 nữ hoàng bằng C ++.Chúng tôi sẽ sử dụng thuật toán quay lại, đây là một thuật toán đơn giản nhưng hiệu quả để giải quyết các vấn đề hoàn thành NP.
Thuật toán quay lại hoạt động bằng cách bắt đầu với một bảng trống và sau đó cố gắng đặt nữ hoàng lên bảng từng cái.Ở mỗi bước, thuật toán kiểm tra xem Nữ hoàng có thể được đặt trên quảng trường hiện tại mà không bị tấn công bởi bất kỳ nữ hoàng nào khác không.Nếu nó có thể, thuật toán đặt nữ hoàng trên quảng trường và sau đó chuyển sang quảng trường tiếp theo.Nếu không thể, thuật toán quay lại và cố gắng đặt nữ hoàng trên một hình vuông khác.
Thuật toán quay lại tiếp tục theo cách này cho đến khi nó tìm thấy một giải pháp cho vấn đề hoặc cho đến khi nó cạn kiệt tất cả các giải pháp có thể.Trong trường hợp của 8 vấn đề Nữ hoàng, có chính xác 92 giải pháp.
Mã sau đây cho thấy cách thực hiện thuật toán quay lại trong C ++:
`` `C ++
#include <Istream>
sử dụng không gian tên STD;
// Xác định kích thước bảng.
const int board_size = 8;
// Xác định một chức năng để kiểm tra xem một nữ hoàng có thể được đặt trên một hình vuông nhất định không.
bool is_safe (board int [board_size] [board_size], int row, int col) {
// Kiểm tra xem có nữ hoàng trong cùng một hàng không.
for (int i = 0; i <col; i ++) {
if (board [hàng] == 1) {
trả lại sai;
}
}
// Kiểm tra xem có nữ hoàng trong cùng một cột không.
for (int i = 0; i <row; i ++) {
if (board [col] == 1) {
trả lại sai;
}
}
// Kiểm tra xem có nữ hoàng trong các đường chéo không.
for (int i = row-1, j = col-1; i> = 0 && j> = 0; i--, j--) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row+1, j = col+1; i <board_size && j <board_size; i ++, j ++) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row-1, j = col+1; i> = 0 && j <board_size; i--, j ++) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row+1, j = col-1; i <board_size && j> = 0; i ++, j--) {
if (board [j] == 1) {
trả lại sai;
}
}
// Nữ hoàng có thể được đặt trên quảng trường đã cho.
trả lại đúng;
}
// Xác định một hàm để giải quyết vấn đề 8 Nữ hoàng.
void giải quyết (board int [board_size] [board_size], int row) {
// Trường hợp cơ sở: Nếu chúng tôi đã đạt đến hàng cuối cùng, chúng tôi đã tìm thấy một giải pháp.
if (hàng == board_size) {
// In giải pháp.
for (int i = 0; i <board_size; i ++) {
for (int j = 0; j <board_size; j ++) {
cout << board [j] << "";
}
cout << endl;
}
=======================================
## 8 Queens in C++
The 8 queens problem is a classic problem in computer science. It is an NP-complete problem, meaning that there is no known polynomial-time algorithm to solve it. However, there are a number of efficient algorithms that can be used to find a solution to the problem.
In this article, we will show how to solve the 8 queens problem using C++. We will use a backtracking algorithm, which is a simple but efficient algorithm for solving NP-complete problems.
The backtracking algorithm works by starting with an empty board and then trying to place queens on the board one by each. At each step, the algorithm checks to see if the queen can be placed on the current square without being attacked by any of the other queens. If it can, the algorithm places the queen on the square and then moves on to the next square. If it cannot, the algorithm backtracks and tries to place the queen on a different square.
The backtracking algorithm continues in this way until it finds a solution to the problem, or until it exhausts all possible solutions. In the case of the 8 queens problem, there are exactly 92 solutions.
The following code shows how to implement the backtracking algorithm in C++:
```c++
#include <iostream>
using namespace std;
// Define the board size.
const int BOARD_SIZE = 8;
// Define a function to check if a queen can be placed on a given square.
bool is_safe(int board[BOARD_SIZE][BOARD_SIZE], int row, int col) {
// Check if there is a queen in the same row.
for (int i = 0; i < col; i++) {
if (board[row] == 1) {
return false;
}
}
// Check if there is a queen in the same column.
for (int i = 0; i < row; i++) {
if (board[col] == 1) {
return false;
}
}
// Check if there is a queen in the diagonals.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[j] == 1) {
return false;
}
}
for (int i = row + 1, j = col + 1; i < BOARD_SIZE && j < BOARD_SIZE; i++, j++) {
if (board[j] == 1) {
return false;
}
}
for (int i = row - 1, j = col + 1; i >= 0 && j < BOARD_SIZE; i--, j++) {
if (board[j] == 1) {
return false;
}
}
for (int i = row + 1, j = col - 1; i < BOARD_SIZE && j >= 0; i++, j--) {
if (board[j] == 1) {
return false;
}
}
// The queen can be placed on the given square.
return true;
}
// Define a function to solve the 8 queens problem.
void solve(int board[BOARD_SIZE][BOARD_SIZE], int row) {
// Base case: if we have reached the last row, we have found a solution.
if (row == BOARD_SIZE) {
// Print the solution.
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
cout << board[j] << " ";
}
cout << endl;
}
Vấn đề 8 Queens là một vấn đề kinh điển trong khoa học máy tính.Đó là một vấn đề hoàn thành NP, có nghĩa là không có thuật toán thời gian đa thức được biết đến để giải quyết nó.Tuy nhiên, có một số thuật toán hiệu quả có thể được sử dụng để tìm giải pháp cho vấn đề.
Trong bài viết này, chúng tôi sẽ chỉ ra cách giải quyết vấn đề 8 nữ hoàng bằng C ++.Chúng tôi sẽ sử dụng thuật toán quay lại, đây là một thuật toán đơn giản nhưng hiệu quả để giải quyết các vấn đề hoàn thành NP.
Thuật toán quay lại hoạt động bằng cách bắt đầu với một bảng trống và sau đó cố gắng đặt nữ hoàng lên bảng từng cái.Ở mỗi bước, thuật toán kiểm tra xem Nữ hoàng có thể được đặt trên quảng trường hiện tại mà không bị tấn công bởi bất kỳ nữ hoàng nào khác không.Nếu nó có thể, thuật toán đặt nữ hoàng trên quảng trường và sau đó chuyển sang quảng trường tiếp theo.Nếu không thể, thuật toán quay lại và cố gắng đặt nữ hoàng trên một hình vuông khác.
Thuật toán quay lại tiếp tục theo cách này cho đến khi nó tìm thấy một giải pháp cho vấn đề hoặc cho đến khi nó cạn kiệt tất cả các giải pháp có thể.Trong trường hợp của 8 vấn đề Nữ hoàng, có chính xác 92 giải pháp.
Mã sau đây cho thấy cách thực hiện thuật toán quay lại trong C ++:
`` `C ++
#include <Istream>
sử dụng không gian tên STD;
// Xác định kích thước bảng.
const int board_size = 8;
// Xác định một chức năng để kiểm tra xem một nữ hoàng có thể được đặt trên một hình vuông nhất định không.
bool is_safe (board int [board_size] [board_size], int row, int col) {
// Kiểm tra xem có nữ hoàng trong cùng một hàng không.
for (int i = 0; i <col; i ++) {
if (board [hàng] == 1) {
trả lại sai;
}
}
// Kiểm tra xem có nữ hoàng trong cùng một cột không.
for (int i = 0; i <row; i ++) {
if (board [col] == 1) {
trả lại sai;
}
}
// Kiểm tra xem có nữ hoàng trong các đường chéo không.
for (int i = row-1, j = col-1; i> = 0 && j> = 0; i--, j--) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row+1, j = col+1; i <board_size && j <board_size; i ++, j ++) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row-1, j = col+1; i> = 0 && j <board_size; i--, j ++) {
if (board [j] == 1) {
trả lại sai;
}
}
for (int i = row+1, j = col-1; i <board_size && j> = 0; i ++, j--) {
if (board [j] == 1) {
trả lại sai;
}
}
// Nữ hoàng có thể được đặt trên quảng trường đã cho.
trả lại đúng;
}
// Xác định một hàm để giải quyết vấn đề 8 Nữ hoàng.
void giải quyết (board int [board_size] [board_size], int row) {
// Trường hợp cơ sở: Nếu chúng tôi đã đạt đến hàng cuối cùng, chúng tôi đã tìm thấy một giải pháp.
if (hàng == board_size) {
// In giải pháp.
for (int i = 0; i <board_size; i ++) {
for (int j = 0; j <board_size; j ++) {
cout << board [j] << "";
}
cout << endl;
}
=======================================
## 8 Queens in C++
The 8 queens problem is a classic problem in computer science. It is an NP-complete problem, meaning that there is no known polynomial-time algorithm to solve it. However, there are a number of efficient algorithms that can be used to find a solution to the problem.
In this article, we will show how to solve the 8 queens problem using C++. We will use a backtracking algorithm, which is a simple but efficient algorithm for solving NP-complete problems.
The backtracking algorithm works by starting with an empty board and then trying to place queens on the board one by each. At each step, the algorithm checks to see if the queen can be placed on the current square without being attacked by any of the other queens. If it can, the algorithm places the queen on the square and then moves on to the next square. If it cannot, the algorithm backtracks and tries to place the queen on a different square.
The backtracking algorithm continues in this way until it finds a solution to the problem, or until it exhausts all possible solutions. In the case of the 8 queens problem, there are exactly 92 solutions.
The following code shows how to implement the backtracking algorithm in C++:
```c++
#include <iostream>
using namespace std;
// Define the board size.
const int BOARD_SIZE = 8;
// Define a function to check if a queen can be placed on a given square.
bool is_safe(int board[BOARD_SIZE][BOARD_SIZE], int row, int col) {
// Check if there is a queen in the same row.
for (int i = 0; i < col; i++) {
if (board[row] == 1) {
return false;
}
}
// Check if there is a queen in the same column.
for (int i = 0; i < row; i++) {
if (board[col] == 1) {
return false;
}
}
// Check if there is a queen in the diagonals.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[j] == 1) {
return false;
}
}
for (int i = row + 1, j = col + 1; i < BOARD_SIZE && j < BOARD_SIZE; i++, j++) {
if (board[j] == 1) {
return false;
}
}
for (int i = row - 1, j = col + 1; i >= 0 && j < BOARD_SIZE; i--, j++) {
if (board[j] == 1) {
return false;
}
}
for (int i = row + 1, j = col - 1; i < BOARD_SIZE && j >= 0; i++, j--) {
if (board[j] == 1) {
return false;
}
}
// The queen can be placed on the given square.
return true;
}
// Define a function to solve the 8 queens problem.
void solve(int board[BOARD_SIZE][BOARD_SIZE], int row) {
// Base case: if we have reached the last row, we have found a solution.
if (row == BOARD_SIZE) {
// Print the solution.
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
cout << board[j] << " ";
}
cout << endl;
}
