N -queen's problem ( or Eight queen's problem ) using backtracking in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:#include<stdio.h> #include<math.h> int board[20],count; int main() { int n,i,j; void Queen(int row,int n); printf("\nEnter Number of Queen's: "); scanf("%d",&n); Queen(1,n);//trace using backtrack return 0; } /* This function is for printing the solution to n-queen's problem */ void print_board(int n) { int i,j; printf("\n\nSolution %d : \n\n",++count); //number of solution for(i=1;i<=n;i++) { printf("\t%d",i); } for(i=1;i<=n;i++) { printf("\n\n%d\t",i); for(j=1;j<=n;j++)// for board { if(board[i]==j) printf("Q\t");//Queen at i,j position else printf("-\t");// empty slot } } } /*This function is for checking for the conflicts.If there is no conflict for the desired position it returns 1 otherwise it returns 0*/ int place(int row,int column) { int i; for(i=1;i<=row-1;i++) { //checking for column and diagonal conflicts if(board[i] == column) return 0; else if(abs(board[i] - column) == abs(i - row)) return 0; } return 1;//no conflicts hence Queen can be placed } /* By this function we try the next free slot and check for proper positioning of queen*/ void Queen(int row,int n) { int column; for(column=1;column<=n;column++) { if(place(row,column)) { board[row] = column;//no conflict so place queen if(row==n)//dead end print_board(n); //printing the board configuration else //try next queen with next position Queen(row+1,n); } } }output:-
Enter Number of Queen's: 4 Solution 1 : 1 2 3 4 1 - Q - - 2 - - - Q 3 Q - - - 4 - - Q - Solution 2 : 1 2 3 4 1 - - Q - 2 Q - - - 3 - - - Q 4 - Q - - --------------------------------
0 comments: