C Progran to Implement N Queen’s Problem using Backtracking
Program : C Progran to Implement N Queen’s Problem using Backtracking
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include<stdio.h> #include<math.h> char a[10][10]; int n; void printmatrix() { int i, j; printf("\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) printf("%c\t", a[i][j]); printf("\n\n"); } } int getmarkedcol(int row) { int i; for (i = 0; i < n; i++) if (a[row][i] == 'Q') { return (i); break; } } int feasible(int row, int col) { int i, tcol; for (i = 0; i < n; i++) { tcol = getmarkedcol(i); if (col == tcol || abs(row - i) == abs(col - tcol)) return 0; } return 1; } void nqueen(int row) { int i, j; if (row < n) { for (i = 0; i < n; i++) { if (feasible(row, i)) { a[row][i] = 'Q'; nqueen(row + 1); a[row][i] = '.'; } } } else { printf("\nThe solution is:- "); printmatrix(); } } int main() { int i, j; printf("\nEnter the no. of queens:- "); scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) a[i][j] = '.'; nqueen(0); return (0); } |
Output :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Enter the no. of queens:- 4 The solution is:- . Q . . . . . Q Q . . . . . Q . The solution is:- . . Q . Q . . . . . . Q . Q . . |