fork download
copy 
  1. //
  2. //  main.cpp
  3. //  N Queen
  4. //
  5. //  Created by Himanshu on 22/04/22.
  6. //
  7.  
  8. #include <iostream>
  9. #include <cstdio>
  10. #define N 8
  11.  
  12.  
  13. // This function prints the solution
  14. void printSolution(int board[N][N]) {
  15.     for (int i = 0; i < N; i++) {
  16.         for (int j = 0; j < N; j++) {
  17.             printf(" %d ", board[i][j]);
  18.         }
  19.         printf("\n");
  20.     }
  21. }
  22.  
  23. // A function to check if a queen can
  24. // be placed on board[row][col].
  25. bool check(int board[N][N], int row, int col) {
  26.     int i, j;
  27.  
  28.     // Check this row on left side
  29.     for (i = 0; i < col; i++) {
  30.         if (board[row][i]) {
  31.             return false;
  32.         }
  33.     }
  34.  
  35.     // Check upper diagonal on left side
  36.     for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
  37.         if (board[i][j]) {
  38.             return false;
  39.         }
  40.     }
  41.  
  42.     // Check lower diagonal on left side
  43.     for (i = row, j = col; j >= 0 && i < N; i++, j--) {
  44.         if (board[i][j]) {
  45.             return false;
  46.         }
  47.     }
  48.  
  49.     return true;
  50. }
  51.  
  52.  
  53. // A recursive function to solve N Queen problem
  54. bool solveUtil(int board[N][N], int col)
  55. {
  56.     // Base case: If all queens are placed then return true
  57.     if (col >= N) {
  58.         return true;
  59.     }
  60.  
  61.     for (int i = 0; i < N; i++) {
  62.  
  63.         // Check if the queen can be placed
  64.         if (check(board, i, col)) {
  65.             board[i][col] = 1;
  66.  
  67.             // recur to place rest of the queens
  68.             if (solveUtil(board, col + 1)) {
  69.                 return true;
  70.             }
  71.  
  72.             board[i][col] = 0; // BACKTRACK
  73.         }
  74.     }
  75.  
  76.     return false;
  77. }
  78.  
  79.  
  80. int main() {
  81.     int board[N][N] = {0};
  82.  
  83.     if (solveUtil(board, 0) == false) {
  84.         printf("Solution does not exist");
  85.     } else {
  86.         printf("Solution:\n");
  87.         printSolution(board);
  88.     }
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 5552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution:
 1  0  0  0  0  0  0  0 
 0  0  0  0  0  0  1  0 
 0  0  0  0  1  0  0  0 
 0  0  0  0  0  0  0  1 
 0  1  0  0  0  0  0  0 
 0  0  0  1  0  0  0  0 
 0  0  0  0  0  1  0  0 
 0  0  1  0  0  0  0  0
https://ideone.com/63luPU
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

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!