locked
Evaluate this program (Knight's Tour )... RRS feed

  • Question

  • One more program from for you guys to evaluate...

     

    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

     

    Code Snippet

    #include<conio.h>

    #include<stdio.h>

     

    int chessBoard[8][8],c=0,d=1,code,flag=0,returnt=0;

    float del=1;

    double sim=0,solution=0.0;

    int acc[8][8]={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};

    char str[100];

     

    void print(int type);

    void mnuMain();

    void mnu();

    void mnu1();

    void revert(int e,int f);

    void delay();

    void mnuTour(int s[]);

    void placeKnight(int e,int f);

    int findPos(int i,int j,int avbPos[8][2]);

    int num();

    void revert(int e,int f);

    void delay();

     

    void main()

    {

    int a=0,b=0,s[2]={0,0};

    c=0;

    d=1;

    flag=0;

    returnt=0;

    del=1;

    sim=solution=0.0;

    mnuMain();

    if(returnt==1)

    return;

    clrscr();

    mnuTour(s);

    for(a=s[0];a<8;a++)

    for(b=s[1];b<8;b++)

    {

    if(returnt==1)

    return;

    placeKnight(a,b);

    }

    if(solution==0.0)

    printf("\n\n\nNo solution exists for the selection\n");

    getch();

    }

     

     

    void mnuTour(int s[])

    {

    int tour;

    char ch;

    clrscr();

    printf("\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s",str);

    printf("\n\n\n1. All tours \n2. Tours from specific location\n\n");

    printf("Enter the option : ");

    get:

    ch=getche();

    if(!(ch==49||ch==50))

    {

    printf("\b \b");

    goto get;

    }

    else

    tour=ch-48;

    if(tour==2)

    {

    printf("\nEnter the x-coordinate of the position (0 to 7): ");

    startx:

    ch=getche();

    if(!(ch>=48&&ch<=55))

    {

    printf("\b \b");

    goto startx;

    }

    else

    s[0]=ch-48;

    printf("\nEnter the y-coordinate of the position (0 to 7): ");

    starty:

    ch=getche();

    if(!(ch>=48&&ch<=55))

    {

    printf("\b \b");

    goto startx;

    }

    else

    s[1]=ch-48;

    }

    return;

    }

     

     

    void mnuMain()

    {

    char ch;

    clrscr();

    printf("\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t");

    printf("\n\nSelect a option \n\n1. All tours \n2. Closed tours\n3. Open tours\n4. Exit\n\n\n");

    printf("Enter the option : ");

    st1:

    ch=getche();

    if(!(ch>48&&ch<53))

    {

    printf("\b \b");

    goto st1;

    }

    else

    code=ch-48;

    switch(code)

    {

    case 1:

    strcpy(str,"ALL KNIGHT'S TOURS");

    break;

    case 2:

    strcpy(str,"CLOSED KNIGHT'S TOURS");

    break;

    case 3:

    strcpy(str,"OPEN KNIGHT'S TOURS");

    break;

    case 4:

    returnt=1;

    }

    }

     

     

    void mnu()

    {

    int x,y,i,j,fl=1;

    for(x=0;x<8&&fl==1;x++)

    {

    for(y=0;y<8&&fl==1;y++)

    {

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

    {

    i=x;

    j=y;

    fl=0;

    }

    }

    }

    if((i>1 && j<7 && chessBoard[i-2][j+1]==64)|(i>1 && j>0 && chessBoard[i-2][j-1]==64)|(i>0 && j<6 && chessBoard[i-1][j+2]==64)|(i>0 && j>1 && chessBoard[i-1][j-2]==64)|(i<6 && j<7 && chessBoard[i+2][j+1]==64)|(i<6 && j>0 && chessBoard[i+2][j-1]==64)|(i<7 && j<6 && chessBoard[i+1][j+2]==64)|(i<7 && j>1 && chessBoard[i+1][j-2]==64))

    fl=1;

    else

    fl=0;

    switch(code)

    {

    case 1:

    mnu1();

    break;

    case 2:

    if(fl==1)

    mnu1();

    break;

    case 3:

    if(fl==0)

    mnu1();

    break;

    }

    }

     

     

    void mnu1()

    {

    char ch;

    int type;

    printf("\n\nDo you want to view as \n\n1. Complete Solution \n2. Step by Step moves (Automated) \n3. Step by Step moves (Keypress)\n\n ");

    printf("\nEnter your option : ");

    st2:

    ch=getche();

    if(!(ch>48&&ch<52))

    {

    printf("\b \b");

    goto st2;

    }

    else

    type=ch-48;

    if(type==2)

    {

    printf("\nEnter the delay between successive steps in seconds : ");

    scanf("%f",&del);

    }

    print(type);

    gotoxy(20,35);

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

    st:

    ch=getche();

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

    {

    printf("\b \b");

    goto st;

    }

    if(ch=='y'||ch=='Y')

    return;

    else

    returnt=1;

    }

     

     

    void placeKnight(int e,int f)

    {

    int g,l,n,avbPos[8][2];

    if(c==0)

    {

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

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

    chessBoard[g][l]=0;

    c=1;

    }

    n=findPos(e,f,avbPos);

    if(n==0)

    {

    if(d==64)

    {

    chessBoard[e][f]=d;

    mnu();

    if(returnt==1)

    return;

    sim++;

    return;

    }

    else

    return;

    }

    else

    {

    chessBoard[e][f]=num();

    d++;

    }

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

    {

    if(returnt==1)

    return;

    placeKnight(avbPos[g][0],avbPos[g][1]);

    }

    if(returnt==1)

    return;

    revert(e,f);

    chessBoard[e][f]=0;

    d--;

    return;

    }

     

     

    int findPos(int i,int j,int avbPos[8][2])

    {

    int k=0,Pos[8][2],x,y,n=0;

    if(i>1 && j<7 && chessBoard[i-2][j+1]==0)

    {

    Pos[k][0]=i-2;

    Pos[k][1]=j+1;

    k++;

    }

    if(i>1 && j>0 && chessBoard[i-2][j-1]==0)

    {

    Pos[k][0]=i-2;

    Pos[k][1]=j-1;

    k++;

    }

    if(i>0 && j<6 && chessBoard[i-1][j+2]==0)

    {

    Pos[k][0]=i-1;

    Pos[k][1]=j+2;

    k++;

    }

    if(i>0 && j>1 && chessBoard[i-1][j-2]==0)

    {

    Pos[k][0]=i-1;

    Pos[k][1]=j-2;

    k++;

    }

    if(i<6 && j<7 && chessBoard[i+2][j+1]==0)

    {

    Pos[k][0]=i+2;

    Pos[k][1]=j+1;

    k++;

    }

    if(i<6 && j>0 && chessBoard[i+2][j-1]==0)

    {

    Pos[k][0]=i+2;

    Pos[k][1]=j-1;

    k++;

    }

    if(i<7 && j<6 && chessBoard[i+1][j+2]==0)

    {

    Pos[k][0]=i+1;

    Pos[k][1]=j+2;

    k++;

    }

    if(i<7 && j>1 && chessBoard[i+1][j-2]==0)

    {

    Pos[k][0]=i+1;

    Pos[k][1]=j-2;

    k++;

    }

    y=acc[Pos[0][0]][Pos[0][1]];

    for(x=1;x<k;x++)

    if(y>acc[Pos[x][0]][Pos[x][1]])

    y=acc[Pos[x][0]][Pos[x][1]];

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

    if(y==acc[Pos[x][0]][Pos[x][1]])

    {

    avbPos[n][0]=Pos[x][0];

    avbPos[n][1]=Pos[x][1];

    n++;

    }

    return n;

    }

    int num()

    {

    return d;

    }

     

     

    void revert(int e,int f)

    {

    int i,j,k;

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

    {

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

    {

    if(chessBoard[i][j]>chessBoard[e][f])

    chessBoard[i][j]=0;

    }

    }

    }

     

     

    void delay()

    {

    int i,j;

    gotoxy(1,1);

    j=2*del;

    for(;j>=0;j--)

    for(i=16000;i>0;i--)

    printf(" \b");

    printf("\b");

    }

     

     

    void print(int type)

    {

    int x,y,i;

    solution++;

    clrscr();

    printf("\n\n\t\t\t\tKNIGHT'S TOUR PUZZLE \n");

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

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

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

    printf("\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s\n\n",str);

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

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

    printf("-");

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

    switch(type)

    {

    case 1:

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

    {

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

    {

    if(y==7)

    printf("|%4d ",chessBoard[x][y]);

    else

    printf("|%3d ",chessBoard[x][y]);

    }

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

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

    printf("----|");

    printf("-----|");

    if(x!=7)

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

    else

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

    }

    break;

    case 2:

    case 3:

    for(i=1;i<=64;i++)

    {

    clrscr();

    printf("\n");

    printf("\n\n\t\t\t\tKNIGHT'S TOUR PUZZLE \n");

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

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

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

    printf("\n\n\t\t\t\tKNIGHT'S TOUR\t\t\t\t\t\n\nType Selected : %s",str);

    printf("\n\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(chessBoard[x][y]<=i)

    {

    if(y==7)

    printf("|%4d ",chessBoard[x][y]);

    else

    printf("|%3d ",chessBoard[x][y]);

    }

    else

    {

    if(y==7)

    printf("| ",chessBoard[x][y]);

    else

    printf("| ",chessBoard[x][y]);

    }

    }

    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 \n");

    }

    if(type==2)

    delay();

    else

    getch();

    }

    break;

    }

    }

     

    Tuesday, June 5, 2007 12:52 PM

Answers

  • A knight's tour of a chessboard  is a sequence of moves by a knight chess  piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the graphs consisting of vertices corresponding to the chessboard squares and edges corresponding to legal knight moves. If the final position of such a tour is a knight's move away from the initial position of the knight, the tour is called re-entrant or closed, and is therefore a Hamiltonian circuit. Else the tour is called a open tour.

     

    Tuesday, June 5, 2007 12:53 PM
  • I have seen a whitepaper of this same puzzle posted by someone else. Dont remember name. I dont know why  people wont even bother to change the contents, and replace their names.
    Wednesday, June 6, 2007 2:15 PM
  • Yes... If they don't even know what they post in the in their papers, how blindly are these persons rushing for points??

    I really wonder...

    Thursday, June 7, 2007 2:32 AM
  • The admins should take care of them Stick out tongue
    Thursday, June 7, 2007 6:05 AM

All replies

  • A knight's tour of a chessboard  is a sequence of moves by a knight chess  piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the graphs consisting of vertices corresponding to the chessboard squares and edges corresponding to legal knight moves. If the final position of such a tour is a knight's move away from the initial position of the knight, the tour is called re-entrant or closed, and is therefore a Hamiltonian circuit. Else the tour is called a open tour.

     

    Tuesday, June 5, 2007 12:53 PM
  • I have seen a whitepaper of this same puzzle posted by someone else. Dont remember name. I dont know why  people wont even bother to change the contents, and replace their names.
    Wednesday, June 6, 2007 2:15 PM
  • Yes... If they don't even know what they post in the in their papers, how blindly are these persons rushing for points??

    I really wonder...

    Thursday, June 7, 2007 2:32 AM
  • The admins should take care of them Stick out tongue
    Thursday, June 7, 2007 6:05 AM