Share backtracking c++,

[trantuongphuoc.binh]

..

Backtracking là một thuật toán đệ quy có thể được sử dụng để tìm tất cả các giải pháp có thể xảy ra cho một vấn đề.Nó hoạt động bằng cách khám phá tất cả các đường dẫn có thể qua một không gian tìm kiếm và quay lại khi đạt đến ngõ cụt.Backtracking thường được sử dụng để giải quyết các vấn đề trong lý thuyết đồ thị, chẳng hạn như tìm tất cả các đường dẫn có thể trong biểu đồ hoặc tìm đường dẫn ngắn nhất giữa hai đỉnh.

** Backtracking trong C ++ **

Sau đây là một ví dụ về thuật toán quay lại trong C ++ tìm thấy tất cả các giải pháp có thể cho vấn đề N-Queens.Vấn đề N-Queens là một vấn đề kinh điển trong khoa học máy tính yêu cầu đặt N Queens trên bàn cờ NXN sao cho không có nữ hoàng nào có thể tấn công một nữ hoàng khác.

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

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

// Một chức năng để kiểm tra xem nữ hoàng có thể được đặt ở (hàng, col)
Bool Issafe (Vector <Vector <int >> & board, 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 <row; i ++) {
if (board [col] == 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 <col; i ++) {
if (board [hàng] == 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 [0] .size (); i ++, j ++) {
if (board [j] == 1) {
trả lại sai;
}
}

// Không có nữ hoàng trong cùng một hàng, cột hoặc đường chéo
trả lại đúng;
}

// một chức năng để in tất cả các giải pháp có thể cho vấn đề N-Queens
void PrintSolution (Vector <Vector <int >> & board) {
for (int i = 0; i <board.size (); i ++) {
for (int j = 0; j <board [0] .size (); j ++) {
cout << board [j] << "";
}
cout << endl;
}
}

// Chức năng quay lại để tìm tất cả các giải pháp có thể cho vấn đề N-Queens
void Backtrack (Vector <Vector <int >> & board, 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 (row == board.size ()) {
in ấn (bảng);
trở lại;
}

// Cố gắng đặt một nữ hoàng trong mỗi cột của hàng hiện tại
for (int col = 0; col <board [0] .size (); col ++) {
// Kiểm tra xem có an toàn không khi đặt nữ hoàng tại (hàng, col)
if (iSSafe (board, hàng, col)) {
// Đặt một nữ hoàng tại (hàng, col)
Bảng [hàng] [col] = 1;

// gọi lại đệ quy Backtrack để tìm tất cả các giải pháp có thể
Backtrack (bảng, hàng + 1);

// Backtrack và loại bỏ nữ hoàng khỏi (hàng, col)
Bảng [hàng] [col] = 0;
}
}
}

int main () {
// Xác định kích thước của bàn cờ
int n = 4;

// Tạo một vectơ vectơ để biểu diễn bàn cờ
vector <vector <int
=======================================
#backtracking, #C++, #AlGorithM, #Programming, #datastructures **Backtracking in C++**

Backtracking is a recursive algorithm that can be used to find all possible solutions to a problem. It works by exploring all possible paths through a search space, and backtracking when a dead end is reached. Backtracking is often used to solve problems in graph theory, such as finding all possible paths in a graph or finding the shortest path between two vertices.

**Backtracking in C++**

The following is an example of a backtracking algorithm in C++ that finds all possible solutions to the N-queens problem. The N-queens problem is a classic problem in computer science that asks for the placement of N queens on an NxN chessboard such that no queen can attack another queen.

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

using namespace std;

// A function to check if a queen can be placed at (row, col)
bool isSafe(vector<vector<int>> &board, int row, int col) {
// Check if there is a queen in the same row
for (int i = 0; i < row; i++) {
if (board[col] == 1) {
return false;
}
}

// Check if there is a queen in the same column
for (int i = 0; i < col; i++) {
if (board[row] == 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[0].size(); i++, j++) {
if (board[j] == 1) {
return false;
}
}

// There is no queen in the same row, column, or diagonals
return true;
}

// A function to print all possible solutions to the N-queens problem
void printSolution(vector<vector<int>> &board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
cout << board[j] << " ";
}
cout << endl;
}
}

// A backtracking function to find all possible solutions to the N-queens problem
void backtrack(vector<vector<int>> &board, int row) {
// Base case: if we have reached the last row, we have found a solution
if (row == board.size()) {
printSolution(board);
return;
}

// Try to place a queen in each column of the current row
for (int col = 0; col < board[0].size(); col++) {
// Check if it is safe to place a queen at (row, col)
if (isSafe(board, row, col)) {
// Place a queen at (row, col)
board[row][col] = 1;

// Recursively call backtrack to find all possible solutions
backtrack(board, row + 1);

// Backtrack and remove the queen from (row, col)
board[row][col] = 0;
}
}
}

int main() {
// Define the size of the chessboard
int n = 4;

// Create a vector of vectors to represent the chessboard
vector<vector<int