骑士漫游和八皇后

/******************************qishi *****************************/

#include <stdio.h>
#include <conio.h>

struct memory
{int sence[8][8] ;
 int board[8][8] ;
 int mem[8] ;
 int last ;
} mem[64] ;

int h[8]={2,1,-1,-2,-2,-1,1,2} ;
int v[8]={-1,-2,-2,-1,1,2,2,1} ;
int board[8][8]={0} ;
int sence[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}} ;

int row, col,hty=0 ;

int comeon(void) ;
void goback(void) ;
int findmin(int[]) ;
void savemem(int) ;
void altsence(void) ;
void print() ;
void printmem(int) ;

/* PREPARE */

void prepare(void)
{int i, j, ha[8],va[8] ;
 for(i=0; i<64; i++)
   { mem[i].last=-1 ;
     for(j=0; j<8; j++)
        mem[i].mem[j]=0 ;
   }

 printf("Input  Begin Point :\n") ;
 scanf("%d%d",row,col) ;
 board[row][col]=1 ;

 for(i=0; i<8; i++)
   {ha[i]=row + h[i] ;
    va[i]=col + v[i] ;
    if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
        sence[ha[i>[va[i>-- ;
   }

 savemem(0) ;
 /*print(hty) ;  */
 hty++ ;
}

/* COMEON!! */

int comeon(void)
{int i, ha[8], va[8], b[8]={9,9,9,9,9,9,9,9}, info=0 ;
 for(i=0; i<8; i++)
  { ha[i]=row+h[i] ;
    va[i]=col+v[i] ;
    if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
      if( board[ha[i>[va[i>==0  && mem[hty].mem[i]!=1 )
         b[i]=sence[ha[i>[va[i>  ;
  }

 i=findmin(b) ;
 if( b[i]!=9 ) ;
   {row=ha[i] ;
    col=va[i] ;
    board[ha[i>[va[i>=1 ;
    altsence() ;
    savemem(i) ;
    /*printmem(hty) ; */
    hty++ ;
    info=1 ;
   }

 return (info) ;
}

/* GOBACK~~ */

void goback(void)
{int i,j ;
 hty--;
 board[row][col]=0 ;
 row = row - h[mem[hty].last] ;
 col = col - v[mem[hty].last] ;
 mem[hty].mem[mem[hty+1].last] = 1 ;
 for(i=0; i<8; i++)
   for(j=0; j<8; j++)
     sence[i][j]=mem[hty].sence[i][j] ;
}

/* PRINT */

void print(void)
{int i;

 for(i=0; i<64; i++)
   {clrscr();
    printmem(i) ;
    getchar() ;
   }
}

/* PRINTMEM */

void printmem(int ht)
{int i, j;
 printf("No.%d Step;\n",ht) ;

 for(i=0; i<8; i++)
   {for(j=0; j<8; j++)
       if( mem[ht].board[i][j]==0)
	   printf("O ") ;
       else
	   printf("H ") ;

    printf("\n") ;
   }
}

/* ALTSENCE */

void altsence(void)
{int i, ha[8], va[8] ;

  for(i=0; i<8; i++)
   {ha[i]=row + h[i] ;
    va[i]=col + v[i] ;
    if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
        sence[ha[i>[va[i>-- ;
   }
}

/* SAVEMEM */

void savemem(int lt)
{int i,j ;
 mem[hty].last=lt ;

  for(i=0; i<8; i++)
     for(j=0; j<8; j++)
      {mem[hty].sence[i][j] = sence[i][j] ;
       mem[hty].board[i][j] = board[i][j] ;
      }
}

/* FINDMIN */

int findmin(int c[8])
{int i,j=0 ;

 for(i=0; i<8; i++)
    if( c[i] < c[j] )
        j=i ;
 return (j) ;
}

/* MAIN */

main()
{int i;
 prepare() ;
 i=comeon();
 while( hty<64 )
  { if(i)
       i=comeon() ;
    else
      {goback() ;
       i=1;
      }
  }
 print();
}


/*************************** 8 queen *********************************/

#include <stdio.h>

int col[8] , temp=0 ;

void qu(int n)
{
 int  pan(int) ;
 void  pri(void) ;

 int t;

 if(n==0)
   t=4 ;
 else
   t=8 ;

 for(col[n]=0; col[n]<t; col[n]++ )
  {if(pan(n)) continue ;
     if (n!=7)
       qu(n+1);
     else
       pri() ;
  }

}

void pri(void)
{
int i, j;

for (i=0; i<8; i++)
 {for (j=0; j<8; j++)
   {if( col[i]==j )
      printf("Q ") ;
    else
      printf("X ") ;
   }
  printf("\n") ;
 }

temp++ ;
printf("\n%d\n",temp) ;
getchar();
}

int pan(int t)
{
 int i,n=0 ;

 for(i=0; i<t; i++)
   {if (col[i]==col[t])
     {n=1; break;}
    if( (col[t]+t) == (col[i]+i) )
     {n=1; break;}
    if( (col[t]-t) == (col[i]-i) )
     {n=1; break;}
   }

 return(n);
}

main()
{
 printf("\n") ;
 qu(0);
 printf("%dEnd\n",temp) ;
}