get2jawa
BAN USERHere given Brute force algorithm.... Done a long time back... So sorry for so many switches... Given here is solution for knights tour prob....
This will run for nearly one hour to generate the 1st solution...
#include <stdio.h>
#include <conio.h>
#define FREE 1
#define NOT_FREE 0
#define NOT_EXIST 0
#define EXIST 1
int nok = 0; // number of knights placed!!!
int pos = 0;
int knight[8][8] = {0};
void fill() {
//gotoxy(18,6);
//printf("K");
int ctr1, ctr2;
int c,r;
for( ctr1 = 0 ; ctr1 < 8 ; ctr1++ )
for( ctr2 = 0 ; ctr2 < 8 ; ctr2++ ) {
if( knight[ ctr1 ][ ctr2 ] != 0 ) {
c = 18 + ( ctr2 * 6 );
r = 6 + ( ctr1 * 2 );
gotoxy(c,r);
printf("%d", knight[ ctr1 ][ ctr2 ]);
}
}
}
int isitfree( int row, int col ) {
if( knight[ row ][ col ] != 0 ) {
return NOT_FREE;
}
else {
return FREE;
}
}
int doesitexist( int row, int col ) {
if( row < 0 || col < 0 || row > 7 || col > 7 )
return NOT_EXIST;
else
return EXIST;
}
int whatsnext( int row, int col, int comb) {
int r,c;
int ctr;
for( ctr = comb ; ctr < 8 ; ctr++ ) {
switch( ctr ) {
case 0: r = row - 2;
c = col - 1;
break;
case 1: r = row - 2;
c = col + 1;
break;
case 2: r = row - 1;
c = col - 2;
break;
case 3: r = row - 1;
c = col + 2;
break;
case 4: r = row + 1;
c = col - 2;
break;
case 5: r = row + 1;
c = col + 2;
break;
case 6: r = row + 2;
c = col - 1;
break;
case 7: r = row + 2;
c = col + 1;
break;
}
if( doesitexist(r,c) == EXIST ) {
if( isitfree( r , c ) == FREE )
return ctr;
}
}
return -1;
}
void place( int row, int col ) {
knight[row][col] = ++nok;
gotoxy( 18 + ( col * 6 ), 6 + ( row * 2 ) );
printf(" ");
gotoxy( 18 + ( col * 6 ), 6 + ( row * 2 ) );
printf("%d", knight[ row ][ col ] );
}
void whereis( int num, int *row, int *col ) {
int ctr1, ctr2;
for( ctr1 = 0 ; ctr1 < 8 ; ctr1++ ) {
for( ctr2 = 0 ; ctr2 < 8 ; ctr2++ ) {
if( knight[ ctr1 ][ ctr2 ] == num ) {
*row = ctr1;
*col = ctr2;
}
}
}
}
int whichcomb( int r, int c, int row, int col ) {
if( r == row - 2 && c == col - 1 )
return 0;
else if( r == row - 2 && c == col + 1 )
return 1;
else if( r == row - 1 && c == col - 2 )
return 2;
else if( r == row - 1 && c == col + 2 )
return 3;
else if( r == row + 1 && c == col - 2 )
return 4;
else if( r == row + 1 && c == col + 2 )
return 5;
else if( r == row + 2 && c == col - 1 )
return 6;
else if( r == row + 2 && c == col + 1 )
return 7;
return -1;
}
void play() {
int row = 0, col = 0;
unsigned long int ctr = 0;
int where;
int r,c;
int comb;
gotoxy(55,24);
printf("Counter : ");
if( isitfree( row, col ) == FREE ) {
place( row, col );
}
while( nok < 65 ) {
ctr++;
gotoxy( 66, 24 );
printf("%lu", ctr );
//
where = whatsnext(row, col,0);
while( where == -1 ) {
r = row;
c = col;
whereis( knight[ row ][ col ] - 1 , &row, &col );
comb = whichcomb(r,c,row,col);
comb++;
knight[ r ][ c ] = 0;
gotoxy( 18 + ( c * 6), 6 + ( r * 2 ));
printf(" ");
nok--;
where = whatsnext(row,col,comb);
}
switch( where ) {
case 0: r = row - 2;
c = col - 1;
break;
case 1: r = row - 2;
c = col + 1;
break;
case 2: r = row - 1;
c = col - 2;
break;
case 3: r = row - 1;
c = col + 2;
break;
case 4: r = row + 1;
c = col - 2;
break;
case 5: r = row + 1;
c = col + 2;
break;
case 6: r = row + 2;
c = col - 1;
break;
case 7: r = row + 2;
c = col + 1;
break;
}
place( r , c );
if( nok == 64 ) {
getch();
}
row = r;
col = c;
}
}
void main() {
clrscr();
play();
getch();
}
Here size of int is 2 bytes.... so i started pos from 15( left to right )
#define isOne(num,pos) (( num & ( 1 << pos ) ) ? TRUE : FALSE )
int flipCounter( int num1, int num2 ) {
for( pos = 15 ; pos != -1 ; pos-- )
if( isOne(num1,pos) != isOne(num2,pos) ) count++;
return count;
}
This is another version......
#include<stdio.h>
void main()
{
unsigned int num = 12345;
unsigned char rmb, lmb, ctr;
for(ctr=1; ctr<(sizeof(num) * 8)/2; ctr++) {
rmb = (num & (1<<((sizeof(num) * 8) - ctr ))) == 0 ? 0 : 1;
lmb = (num & (1<< (ctr-1))) > 0 ? 1 :0;
if(rmb!=lmb) break;
}
if(rmb==lmb) printf("Pali");
else printf("! Pali");
}
Method 1:
Method 2:
Method 3:
- get2jawa July 23, 2013