fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #define N 8
  5.  
  6. using namespace std;
  7.  
  8. int y, x;
  9.  
  10. bool isSafe(const vector<string> &board, int row, int col)
  11. {
  12.     /* Check this row on left side */
  13.     for (int i = 0; i < col; ++i) {
  14.         if (board[row][i] == 'w') return false;
  15.     }
  16.     /* Check upper diagonal on left side */
  17.     for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
  18.         if (board[i][j] == 'w') return false;
  19.     }
  20.     /* Check lower diagonal on left side */
  21.     for (int i = row + 1, j = col - 1; i < N && j >= 0; ++i, --j) {
  22.         if (board[i][j] == 'w') return false;
  23.     }
  24.     return true;
  25. }
  26. // Place all the kings suitably before col x
  27. bool SolveNQueenB(vector<string> &board, int col = 0)
  28. {
  29.     // Solution found!
  30.     if (col == x) {
  31.         board[y][x] = 'w';
  32.         return true;
  33.     }
  34.     for (int i = 0; i < N; ++i) {
  35.         // Found a square for queen[i][col]
  36.         if (isSafe(board, i, col)) {
  37.             board[i][col] = 'w';
  38.             if (SolveNQueenB(board, col + 1))
  39.                 return true;
  40.             board[i][col] = '.'; // backtrack
  41.         }
  42.     }
  43.     return false;
  44. }
  45. // Place all the kings suitably after col x
  46. bool SolveNQueenA(vector<string> &board, int col = x + 1)
  47. {
  48.     // Solution found!
  49.     if (col == N) {
  50.         return true;
  51.     }
  52.     for (int i = 0; i < N; ++i) {
  53.         // Found a square for queen[i][col]
  54.         if (isSafe(board, i, col)) {
  55.             board[i][col] = 'w';
  56.             if (SolveNQueenA(board, col + 1))
  57.                 return true;
  58.             board[i][col] = '.'; // backtrack
  59.         }
  60.     }
  61.     return false;
  62. }
  63.  
  64. int main()
  65. {
  66.     // print all solutions to N-Queen problem.
  67.     vector<string> board(N);
  68.     for (int i = 0; i < N; ++i)
  69.         board[i].resize(N, '.');
  70.     cin >> y >> x;
  71.     --y; --x; // set to the right indexes
  72.     SolveNQueenB(board);
  73.     SolveNQueenA(board);
  74.     for (int i = 0; i < N; ++i) {
  75.         cout << board[i] << endl;
  76.     }
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
3 2
stdout 
w.......
........
.w......
........
........
........
........
........
https://ideone.com/U1BE2N
language:
C++ (gcc 8.3)
created:
7 years 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!