fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. // Các mảng kiểm tra cột và đường chéo
  8. vector<bool> cols, diagA, diagB;
  9. vector<vector<string>> results;
  10.  
  11. // Hàm kiểm tra xem có thể đặt hậu tại (x, y) không
  12. bool isValid(int x, int y, int n) {
  13.     return !cols[y] && !diagA[n - 1 + x - y] && !diagB[x + y];
  14. }
  15.  
  16. // Lưu kết quả khi tìm được cách đặt hậu
  17. void saveResult(int n, vector<int>& pos) {
  18.     vector<string> board(n, string(n, '.'));
  19.     for (int i = 0; i < n; ++i) {
  20.         board[i][pos[i]] = 'Q';
  21.     }
  22.     results.push_back(board);
  23. }
  24.  
  25. // Hàm quay lui để đặt hậu
  26. void placeQueens(int row, int n, vector<int>& pos) {
  27.     for (int col = 0; col < n; ++col) {
  28.         if (isValid(row, col, n)) {
  29.             pos[row] = col;          // Đặt hậu tại (row, col)
  30.             cols[col] = true;        // Đánh dấu cột
  31.             diagA[n - 1 + row - col] = true;  // Đánh dấu đường chéo chính
  32.             diagB[row + col] = true;          // Đánh dấu đường chéo phụ
  33.  
  34.             if (row == n - 1) {
  35.                 saveResult(n, pos); // Nếu đặt đủ n hậu, lưu kết quả
  36.             } else {
  37.                 placeQueens(row + 1, n, pos); // Đặt tiếp hậu ở hàng tiếp theo
  38.             }
  39.  
  40.             // Hoàn tác để thử các khả năng khác
  41.             pos[row] = -1;
  42.             cols[col] = false;
  43.             diagA[n - 1 + row - col] = false;
  44.             diagB[row + col] = false;
  45.         }
  46.     }
  47. }
  48.  
  49. int main() {
  50.     int n;
  51.     cin >> n;
  52.  
  53.     // Khởi tạo các mảng kiểm tra
  54.     cols.resize(n, false);
  55.     diagA.resize(2 * n - 1, false);
  56.     diagB.resize(2 * n - 1, false);
  57.     vector<int> pos(n, -1);
  58.  
  59.     // Gọi hàm quay lui
  60.     placeQueens(0, n, pos);
  61.  
  62.     // In kết quả
  63.     cout << results.size() << endl; // Số cách đặt hậu
  64.     for (const auto& board : results) {
  65.         for (const string& row : board) {
  66.             cout << row << endl;
  67.         }
  68.         cout << endl; // Cách nhau bởi một dòng trống
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
4
stdout
copy 
2
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
https://ideone.com/vNhrwV
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!