fork download
  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. /* A utility function to print solution.
  8. It prints 1 where Queen is placed */
  9. void printSolution(int board[N][N]) {
  10. for (int i = 0; i < N; i++) {
  11. for (int j = 0; j < N; j++)
  12. printf(" %d ", board[i][j]);
  13. printf("\n");
  14. }
  15. }
  16. /* A utility 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. /* A recursive utility function to solve N
  35. Queen problem */
  36. bool solveUtil(int board[N][N], int col)
  37. {
  38. /* base case: If all queens are placed
  39.  then return true */
  40. if (col >= N)
  41. return true;
  42. /* Consider this column and try placing
  43.  this queen in all rows one by one */
  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. int main() {
  59. int board[N][N] = {0};
  60. if (solveUtil(board, 0) == false) {
  61. printf("Solution does not exist");
  62. } else {
  63. printf("Solution:\n");
  64. printSolution(board);
  65. }
  66. return 0;
  67. }
Success #stdin #stdout 0s 4196KB
stdin
Standard input is empty
stdout
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