fork download
copy 
  1. /* C/C++ program to solve N Queen Problem using 
  2. backtracking */
  3. #define N 8 
  4. #include <stdbool.h> 
  5. #include <stdio.h>
  6.  
  7. /* This function prints the solution */
  8. void printSolution(int board[N][N]) { 
  9.  for (int i = 0; i < N; i++) { 
  10.   for (int j = 0; j < N; j++) 
  11.    printf(" %d ", board[i][j]); 
  12.   printf("\n"); 
  13.  }
  14. }
  15.  
  16. /* A function to check if a queen can 
  17. be placed on board[row][col]. */
  18. bool check(int board[N][N], int row, int col) { 
  19.  int i, j;
  20. /* Check this row on left side */
  21.  for (i = 0; i < col; i++) 
  22.   if (board[row][i]) 
  23.    return false;
  24. /* Check upper diagonal on left side */
  25.  for (i = row, j = col; i >= 0 && j >= 0; i--, j--) 
  26.   if (board[i][j]) 
  27.    return false;
  28. /* Check lower diagonal on left side */
  29.  for (i = row, j = col; j >= 0 && i < N; i++, j--) 
  30.   if (board[i][j]) 
  31.    return false;
  32. return true; 
  33. }
  34.  
  35.  
  36. /* A recursive function to solve N 
  37. Queen problem */
  38. bool solveUtil(int board[N][N], int col) 
  39. { 
  40.  /* base case: If all queens are placed 
  41.  then return true */
  42.  if (col >= N) 
  43.   return true;
  44.  for (int i = 0; i < N; i++) { 
  45.   /* Check if the queen can be placed on 
  46.   board[i][col] */
  47.   if (check(board, i, col)) { 
  48.    board[i][col] = 1;
  49. /* recur to place rest of the queens */
  50.    if (solveUtil(board, col + 1)) 
  51.     return true;
  52.    board[i][col] = 0; // BACKTRACK 
  53.   } 
  54.  }
  55.  return false; 
  56. }
  57.  
  58.  
  59. int main() { 
  60.  int board[N][N] = {0};
  61.  if (solveUtil(board, 0) == false) { 
  62.   printf("Solution does not exist");  
  63.  } else {
  64.   printf("Solution:\n");
  65.   printSolution(board); 
  66.  }
  67.  return 0;
  68. }
Success #stdin #stdout 0s 5432KB
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/yRWLH0
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!