locked
Evaluate this program (8 Queen Puzzle)... RRS feed

  • Question

  • This is my own program. Suggestions for improvements are welcome. Mail me at raghuramdcbe@gmail.com . Program Copyrighted. USE TurboC compiler for execution of the program.

     

     

    8 Queen Puzzle

    #include<stdio.h>

    #include<conio.h>

     

    int chessBoard[8][8];

    int a=0,b=0,ct=1;

     

    void placeQueen(int c,int d);

    void fillPos(int c,int d);

    void revert();

    int findPos(int d,int avbPos[7][2]);

    void print();

    void p();

     

    void main()

    {

    int c,d;

    a=0;

    b=0;

    ct=1;

    for(c=0,d=0;c<8;c++)

    {

    a=0;

    if(ct==0)

    return;

    placeQueen(c,d);

    }

    }

     

    void placeQueen(int c,int d)

    {

    int x,y,avbPos[7][2],n;

    if(a==0)

    {

    for(x=0;x<8;x++)

    for(y=0;y<8;y++)

    chessBoard[x][y]=0;

    a=1;

    }

    chessBoard[c][d]=2;

    fillPos(c,d);

    n=findPos(d,avbPos);

    if(n==0)

    {

    p();

    chessBoard[c][d]=0;

    revert();

    return;

    }

    for(x=0;x<n;x++)

    {

    if(ct==0)

    return;

    placeQueen(avbPos[x][0],avbPos[x][1]);

    }

    chessBoard[c][d]=0;

    revert();

    return;

    }

     

    void fillPos(int c,int d)

    {

    int i,j;

    for(i=c+1,j=d;i<8;i++)

    chessBoard[i][j]=1;

    for(i=0,j=d;i<c;i++)

    chessBoard[i][j]=1;

    for(i=c,j=d+1;j<8;j++)

    chessBoard[i][j]=1;

    for(i=c,j=0;j<d;j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d+1;i<8&&j<8;i++,j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d-1;i<8&&j>=0;i++,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d-1;i>=0&&j>=0;i--,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d+1;i>=0&&j<8;i--,j++)

    chessBoard[i][j]=1;

    }

     

    void revert()

    {

    int i,j,pos[7][2],k=0;

    for(i=0;i<8;i++)

    for(j=0;j<8;j++)

    {

    if(chessBoard[i][j]==2)

    {

    pos[k][0]=i;

    pos[k][1]=j;

    k++;

    }

    else

    chessBoard[i][j]=0;

    }

    for(i=0;i<k;i++)

    fillPos(pos[i][0],pos[i][1]);

    }

     

     

    int findPos(int d,int avbPos[7][2])

    {

    int x,y,k=0;

    for(x=0,y=d+1;x<8&&y<8;x++)

    {

    if(chessBoard[x][y]==0)

    {

    avbPos[k][0]=x;

    avbPos[k][1]=y;

    k++;

    }

    }

    return k;

    }

     

     

    void p()

    {

    int x,y,k=0;

    for(x=0;x<8;x++)

    for(y=0;y<8;y++)

    if(chessBoard[x][y]==2)

    k++;

    if(k==8)

    print();

    }

     

     

    void print()

    {

    int x,y;

    char ch;

    clrscr();

    printf("\n\n\t\t\t\tEIGHT QUEENS PUZZLE \n");

    printf("\n\nProgrammer : Raghuram Duraisamy\n\n");

    printf("Email ID : Raghuramdcbe@gmail.com ");

    printf(",raghusar_9000@hotmail.com");

    printf("\n\n\n\t\t\tCOMBINATION NUMBER : %d\n",++b);

    printf("\n\n\t\t");

    for(x=0;x<41;x++)

    printf("-");

    printf("\t\t \n\t\t");

    for(x=0;x<8;x++)

    {

    for(y=0;y<8;y++)

    {

    if(y==7)

    {

    if(chessBoard[x][y]==1)

    printf("|%4s ",".");

    else

    printf("|%4s ","Q");

    }

    else

    {

    if(chessBoard[x][y]==1)

    printf("|%3s ",".");

    else

    printf("|%3s ","Q");

    }

    }

    printf("\b|\t\t \n\t\t|");

    for(y=0;y<8;y++)

    printf("----|");

    if(x!=7)

    printf("\t\t \n\t\t");

    else

    printf("\t\t ");

    }

    if(b!=92)

    printf("\n\nDo you want to continue (Y/N): ");

    else

    {

    printf("\n\nAll the combinations are over\n");

    printf("Press any key to exit");

    getch();

    exit(0);

    }

    l2:

    ch=getch();

    if(!(ch=='Y'||ch=='y'||ch=='N'||ch=='n'))

    {

    printf("\b \b");

    goto l2;

    }

    if(ch=='n'||ch=='N')

    ct=0;

    }

     

     

     

     

    Saturday, June 2, 2007 7:46 AM

Answers

  • yaar Raghuram

     

    i tried ur program. hmmmm..... really nice logic man. there in the o/p the first row and first column the letter "q" changes after saying yes for nearly 10-12 times and it moves one step downwards and so on... after that, if we say no, it comes out of program.

    quite nice logic. i am really impressed

     

    Bye

    Saturday, June 2, 2007 11:23 AM
  • @ Sunil - Thank you.. There are totally 92 different combinations .. Thats is what displayed when you keep pressing the Y key...
    Saturday, June 2, 2007 3:52 PM
  • I'll  say a few words abt the 8 queen problem

     

    The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
    Saturday, June 2, 2007 5:22 PM
  • Can you work out on the general format for this?? I mean user give the input as how many queens are their or the block size of the board, both will be same.. I have seen some of the codes on net which gives the general form of the queen problem..

    Still nice work mate, I was not able to figure out the logic...
    Saturday, June 2, 2007 6:10 PM
  • The logic I followed here is a simple one. It is based on one queen per column algorithm.

    The working logic is as follows.

    Initially , the 2 dimensional array chessBoard is initialised to all zeros.

     

    1) A queen is placed in a square of the first column. To indicate this,  2 is stored in the corressponding array location.

    2) All the squares that are accessible by the queen are marked. To indicate this,  1 is stored in the corressponding array locations.(OCCUPANCY)

    3)The next column is checked for squares which have 0 stored in them and these positions are stored in a separate array.

    4) One of the squares is chosen and a queen is placed. Steps 2 and 3 are repeated. (This is done by recursive call in the program)

    5)When all columns have been placed with a queen,then the board position is printed.

    6)If a column does not have any vacant position for the placement of queen, then the queen that was placed in the previous column(in the previous step ) is removed and then placed in the next possible position in the same column (the next possible position is available from the stored array of available positions) and the occupancy is modified corresspondingly.

    Sunday, June 3, 2007 12:22 AM
  • Nice logic buddy, thankz a lot, now can you tell me how to calculate the precise number of combinations that is possible, is it possible to calculate the number of combinations ???
    Sunday, June 3, 2007 4:18 AM
  • It is possible to extend the program to solve  N queen puzzle. Just put "#define  size N"  at the top and replace every 8 with size

    and every 7 in the program as 'size-1' .  Note that the above said replacement technique will not work for  N=1 alone...

     

    Then the program would work fine for N queen puzzle , solving for the board positions. But the display would be a mess for N>10...But still if you are interested , the print() function can be modified as to write to a file..

     

    And I dont think there is any formula for finding the total number of combinations.. Only after you find all the possible combinations, you can say that there are this many possible combinations..

    Sunday, June 3, 2007 9:34 AM
  • @ Varun - I have now modified my program so as to solve for N queens. To look every combination you have to open the text file.

    I went for storing the ouput in file because, display on screen will be messed up for N>12. Also check that "Word wrap" in Notepad is Turned OFF.

     

    Rather than getting the board size as input , it is put as " #define size N" . Change the value of N , to view the output for different board sizes.. The program will not work for N=1.

     

    Also, be sure to change the macro path to the path where the output file is to be stored...

     

    Program modified to solve for N Queen puzzle

    #include<stdio.h>

    #include<conio.h>

     

    #define path "E:\\NQueen.txt"

    #define size 29

     

    int chessBoard[size][size];

    int a=0,b=0,ct=1,cnt=0;

    FILE *fp;

     

    void placeQueen(int c,int d);

    void fillPos(int c,int d);

    void revert();

    int findPos(int d,int avbPos[size-1][2]);

    void print();

    void p();

     

    void main()

    {

    int c,d;

    a=0;

    b=0;

    ct=1;

    clrscr();

    printf("\n\n\t\tN QUEENS PUZZLE \n");

    printf("\n\nProgrammer : Raghuram Duraisamy\n\n");

    printf("Email ID : Raghuramdcbe@gmail.com ");

    printf(",raghusar_9000@hotmail.com");

    for(c=0,d=0;c<size;c++)

    {

    a=0;

    if(ct==0)

    return;

    placeQueen(c,d);

    }

    if(cnt==0)

    {

    printf("\n\n No solution exists for BoardSize= %d",size);

    getch();

    }

    }

     

    void placeQueen(int c,int d)

    {

    int x,y,avbPos[size-1][2],n;

    if(a==0)

    {

    for(x=0;x<size;x++)

    for(y=0;y<size;y++)

    chessBoard[x][y]=0;

    a=1;

    }

    chessBoard[c][d]=2;

    fillPos(c,d);

    n=findPos(d,avbPos);

    if(n==0)

    {

    p();

    chessBoard[c][d]=0;

    revert();

    return;

    }

    for(x=0;x<n;x++)

    {

    if(ct==0)

    return;

    placeQueen(avbPos[x][0],avbPos[x][1]);

    }

    chessBoard[c][d]=0;

    revert();

    return;

    }

     

    void fillPos(int c,int d)

    {

    int i,j;

    for(i=c+1,j=d;i<size;i++)

    chessBoard[i][j]=1;

    for(i=0,j=d;i<c;i++)

    chessBoard[i][j]=1;

    for(i=c,j=d+1;j<size;j++)

    chessBoard[i][j]=1;

    for(i=c,j=0;j<d;j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d+1;i<size&&j<size;i++,j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d-1;i<size&&j>=0;i++,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d-1;i>=0&&j>=0;i--,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d+1;i>=0&&j<size;i--,j++)

    chessBoard[i][j]=1;

    }

     

    void revert()

    {

    int i,j,pos[size-1][2],k=0;

    for(i=0;i<size;i++)

    for(j=0;j<size;j++)

    {

    if(chessBoard[i][j]==2)

    {

    pos[k][0]=i;

    pos[k][1]=j;

    k++;

    }

    else

    chessBoard[i][j]=0;

    }

    for(i=0;i<k;i++)

    fillPos(pos[i][0],pos[i][1]);

    }

    int findPos(int d,int avbPos[size-1][2])

    {

    int x,y,k=0;

    for(x=0,y=d+1;x<size&&y<size;x++)

    {

    if(chessBoard[x][y]==0)

    {

    avbPos[k][0]=x;

    avbPos[k][1]=y;

    k++;

    }

    }

    return k;

    }

     

     

    void p()

    {

    int x,y,k=0;

    for(x=0;x<size;x++)

    for(y=0;y<size;y++)

    if(chessBoard[x][y]==2)

    k++;

    if(k==size)

    print();

    }

     

     

    void print()

    {

    int x,y;

    char ch;

    clrscr();

    cnt=1;

    fp=fopen(path,"w");

    fprintf(fp,"\n\n\t\tN QUEENS PUZZLE \n");

    fprintf(fp,"\n\nProgrammer : Raghuram Duraisamy\n\n");

    fprintf(fp,"Email ID : Raghuramdcbe@gmail.com ");

    fprintf(fp,",raghusar_9000@hotmail.com");

    fprintf(fp,"\n\n$ - Queen and * Blank spaces");

    fprintf(fp,"\n\t\t\tCOMBINATION NUMBER : %d\n",++b);

    fprintf(fp,"\n");

    for(x=0;x<((size)*5)-(size-1)/2;x++)

    fprintf(fp,"-");

    fprintf(fp,"\n");

    for(x=0;x<size;x++)

    {

    for(y=0;y<size;y++)

    {

    if(chessBoard[x][y]==1)

    fprintf(fp,"|%3s ","*");

    else

    fprintf(fp,"|%3s ","$");

    }

    fprintf(fp,"|\n|");

    for(y=0;y<size;y++)

    {

    if((y%8)==0&&y!=0)

    fprintf(fp,"---|");

    else

    fprintf(fp,"----|");

    }

    fprintf(fp,"\n");

    }

    fflush(stdin);

    printf("\n\n\t\t\t\tN QUEENS PUZZLE \n");

    printf("\n\nProgrammer : Raghuram Duraisamy\n\n");

    printf("Email ID : Raghuramdcbe@gmail.com ");

    printf(",raghusar_9000@hotmail.com");

    printf("\n\n\n\t\t\tCOMBINATION NUMBER : %d\n Open ",b);

    printf(path);

    printf(" to view the board position\n\n");

    printf("NOTE : The file will be over written with the new position when you press Y \n");

    printf("\nDo you want to continue (Y/N): ");

    l2:

    ch=getch();

    if(!(ch=='Y'||ch=='y'||ch=='N'||ch=='n'))

    {

    printf("\b \b");

    goto l2;

    }

    if(ch=='n'||ch=='N')

    ct=0;

    }

     

     

     

    Sunday, June 3, 2007 11:07 AM
  • Great work man..thankz a lot...
    Sunday, June 3, 2007 11:28 AM
  • Nice code Raghuram.
    I had this problem in my last semester. But i think the code can be decreased a but. I dont remember byheart each steps, but the algo was given in the book, ill try finding the book, an make a code snippet for it. so that you can have a idea.
    Sunday, June 3, 2007 2:39 PM

All replies

  • yaar Raghuram

     

    i tried ur program. hmmmm..... really nice logic man. there in the o/p the first row and first column the letter "q" changes after saying yes for nearly 10-12 times and it moves one step downwards and so on... after that, if we say no, it comes out of program.

    quite nice logic. i am really impressed

     

    Bye

    Saturday, June 2, 2007 11:23 AM
  • @ Sunil - Thank you.. There are totally 92 different combinations .. Thats is what displayed when you keep pressing the Y key...
    Saturday, June 2, 2007 3:52 PM
  • I'll  say a few words abt the 8 queen problem

     

    The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
    Saturday, June 2, 2007 5:22 PM
  • Can you work out on the general format for this?? I mean user give the input as how many queens are their or the block size of the board, both will be same.. I have seen some of the codes on net which gives the general form of the queen problem..

    Still nice work mate, I was not able to figure out the logic...
    Saturday, June 2, 2007 6:10 PM
  • The logic I followed here is a simple one. It is based on one queen per column algorithm.

    The working logic is as follows.

    Initially , the 2 dimensional array chessBoard is initialised to all zeros.

     

    1) A queen is placed in a square of the first column. To indicate this,  2 is stored in the corressponding array location.

    2) All the squares that are accessible by the queen are marked. To indicate this,  1 is stored in the corressponding array locations.(OCCUPANCY)

    3)The next column is checked for squares which have 0 stored in them and these positions are stored in a separate array.

    4) One of the squares is chosen and a queen is placed. Steps 2 and 3 are repeated. (This is done by recursive call in the program)

    5)When all columns have been placed with a queen,then the board position is printed.

    6)If a column does not have any vacant position for the placement of queen, then the queen that was placed in the previous column(in the previous step ) is removed and then placed in the next possible position in the same column (the next possible position is available from the stored array of available positions) and the occupancy is modified corresspondingly.

    Sunday, June 3, 2007 12:22 AM
  • Nice logic buddy, thankz a lot, now can you tell me how to calculate the precise number of combinations that is possible, is it possible to calculate the number of combinations ???
    Sunday, June 3, 2007 4:18 AM
  • It is possible to extend the program to solve  N queen puzzle. Just put "#define  size N"  at the top and replace every 8 with size

    and every 7 in the program as 'size-1' .  Note that the above said replacement technique will not work for  N=1 alone...

     

    Then the program would work fine for N queen puzzle , solving for the board positions. But the display would be a mess for N>10...But still if you are interested , the print() function can be modified as to write to a file..

     

    And I dont think there is any formula for finding the total number of combinations.. Only after you find all the possible combinations, you can say that there are this many possible combinations..

    Sunday, June 3, 2007 9:34 AM
  • @ Varun - I have now modified my program so as to solve for N queens. To look every combination you have to open the text file.

    I went for storing the ouput in file because, display on screen will be messed up for N>12. Also check that "Word wrap" in Notepad is Turned OFF.

     

    Rather than getting the board size as input , it is put as " #define size N" . Change the value of N , to view the output for different board sizes.. The program will not work for N=1.

     

    Also, be sure to change the macro path to the path where the output file is to be stored...

     

    Program modified to solve for N Queen puzzle

    #include<stdio.h>

    #include<conio.h>

     

    #define path "E:\\NQueen.txt"

    #define size 29

     

    int chessBoard[size][size];

    int a=0,b=0,ct=1,cnt=0;

    FILE *fp;

     

    void placeQueen(int c,int d);

    void fillPos(int c,int d);

    void revert();

    int findPos(int d,int avbPos[size-1][2]);

    void print();

    void p();

     

    void main()

    {

    int c,d;

    a=0;

    b=0;

    ct=1;

    clrscr();

    printf("\n\n\t\tN QUEENS PUZZLE \n");

    printf("\n\nProgrammer : Raghuram Duraisamy\n\n");

    printf("Email ID : Raghuramdcbe@gmail.com ");

    printf(",raghusar_9000@hotmail.com");

    for(c=0,d=0;c<size;c++)

    {

    a=0;

    if(ct==0)

    return;

    placeQueen(c,d);

    }

    if(cnt==0)

    {

    printf("\n\n No solution exists for BoardSize= %d",size);

    getch();

    }

    }

     

    void placeQueen(int c,int d)

    {

    int x,y,avbPos[size-1][2],n;

    if(a==0)

    {

    for(x=0;x<size;x++)

    for(y=0;y<size;y++)

    chessBoard[x][y]=0;

    a=1;

    }

    chessBoard[c][d]=2;

    fillPos(c,d);

    n=findPos(d,avbPos);

    if(n==0)

    {

    p();

    chessBoard[c][d]=0;

    revert();

    return;

    }

    for(x=0;x<n;x++)

    {

    if(ct==0)

    return;

    placeQueen(avbPos[x][0],avbPos[x][1]);

    }

    chessBoard[c][d]=0;

    revert();

    return;

    }

     

    void fillPos(int c,int d)

    {

    int i,j;

    for(i=c+1,j=d;i<size;i++)

    chessBoard[i][j]=1;

    for(i=0,j=d;i<c;i++)

    chessBoard[i][j]=1;

    for(i=c,j=d+1;j<size;j++)

    chessBoard[i][j]=1;

    for(i=c,j=0;j<d;j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d+1;i<size&&j<size;i++,j++)

    chessBoard[i][j]=1;

    for(i=c+1,j=d-1;i<size&&j>=0;i++,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d-1;i>=0&&j>=0;i--,j--)

    chessBoard[i][j]=1;

    for(i=c-1,j=d+1;i>=0&&j<size;i--,j++)

    chessBoard[i][j]=1;

    }

     

    void revert()

    {

    int i,j,pos[size-1][2],k=0;

    for(i=0;i<size;i++)

    for(j=0;j<size;j++)

    {

    if(chessBoard[i][j]==2)

    {

    pos[k][0]=i;

    pos[k][1]=j;

    k++;

    }

    else

    chessBoard[i][j]=0;

    }

    for(i=0;i<k;i++)

    fillPos(pos[i][0],pos[i][1]);

    }

    int findPos(int d,int avbPos[size-1][2])

    {

    int x,y,k=0;

    for(x=0,y=d+1;x<size&&y<size;x++)

    {

    if(chessBoard[x][y]==0)

    {

    avbPos[k][0]=x;

    avbPos[k][1]=y;

    k++;

    }

    }

    return k;

    }

     

     

    void p()

    {

    int x,y,k=0;

    for(x=0;x<size;x++)

    for(y=0;y<size;y++)

    if(chessBoard[x][y]==2)

    k++;

    if(k==size)

    print();

    }

     

     

    void print()

    {

    int x,y;

    char ch;

    clrscr();

    cnt=1;

    fp=fopen(path,"w");

    fprintf(fp,"\n\n\t\tN QUEENS PUZZLE \n");

    fprintf(fp,"\n\nProgrammer : Raghuram Duraisamy\n\n");

    fprintf(fp,"Email ID : Raghuramdcbe@gmail.com ");

    fprintf(fp,",raghusar_9000@hotmail.com");

    fprintf(fp,"\n\n$ - Queen and * Blank spaces");

    fprintf(fp,"\n\t\t\tCOMBINATION NUMBER : %d\n",++b);

    fprintf(fp,"\n");

    for(x=0;x<((size)*5)-(size-1)/2;x++)

    fprintf(fp,"-");

    fprintf(fp,"\n");

    for(x=0;x<size;x++)

    {

    for(y=0;y<size;y++)

    {

    if(chessBoard[x][y]==1)

    fprintf(fp,"|%3s ","*");

    else

    fprintf(fp,"|%3s ","$");

    }

    fprintf(fp,"|\n|");

    for(y=0;y<size;y++)

    {

    if((y%8)==0&&y!=0)

    fprintf(fp,"---|");

    else

    fprintf(fp,"----|");

    }

    fprintf(fp,"\n");

    }

    fflush(stdin);

    printf("\n\n\t\t\t\tN QUEENS PUZZLE \n");

    printf("\n\nProgrammer : Raghuram Duraisamy\n\n");

    printf("Email ID : Raghuramdcbe@gmail.com ");

    printf(",raghusar_9000@hotmail.com");

    printf("\n\n\n\t\t\tCOMBINATION NUMBER : %d\n Open ",b);

    printf(path);

    printf(" to view the board position\n\n");

    printf("NOTE : The file will be over written with the new position when you press Y \n");

    printf("\nDo you want to continue (Y/N): ");

    l2:

    ch=getch();

    if(!(ch=='Y'||ch=='y'||ch=='N'||ch=='n'))

    {

    printf("\b \b");

    goto l2;

    }

    if(ch=='n'||ch=='N')

    ct=0;

    }

     

     

     

    Sunday, June 3, 2007 11:07 AM
  • Great work man..thankz a lot...
    Sunday, June 3, 2007 11:28 AM
  • Nice code Raghuram.
    I had this problem in my last semester. But i think the code can be decreased a but. I dont remember byheart each steps, but the algo was given in the book, ill try finding the book, an make a code snippet for it. so that you can have a idea.
    Sunday, June 3, 2007 2:39 PM