I happened to try find the total number of ways a horse can cover all 64 squares in a chess board without visiting a square more than once starting from one corner.
All I was able to do was to use a brute force algorithm which run for a whole day just to find about 400000 answers.
Can any one please help to improve the programs performance.
Google for "knights tour".
thanks a lot
On second thoughts, I did not find any logical resons to limit combinations.
Could you help a little bit more.
And thanks too, I am finding even intersting problem in google
"help a little more"
how can we help you if you dont give us any thing to work with.
you cant plop down the description of a problem, and say "help me fix my program to work better" and then not even show us WTF you've been doing?
post your program here.
and use [code] tags. if you dont know what [code] tags are, find out before you post.
I have copied the code below. The problem I face is It never seems to end. Thats why I want to start from scratch with better algorithm.
#include<stdlib.h>
#include <stdio.h>
#include <conio.h>
#include<string.h>
/* Defination of all moves */
#define TL 0x01 // top left i.e., 2 squares up & 1 square left
#define TR 0x02
#define RT 0x04
#define RB 0x08
#define BR 0x10
#define BL 0x20
#define LB 0x40
#define LT 0x80
// stack which holds the position
typedef struct visited {
char place ; // varies from 0 to 63 representing a square
char moves ; // availabe moves -> every bit represents a possible move
struct visited *next ; // link to previous move
} VISIT ;
VISIT *head ; // contains the latest move made by the horse
#define removMov(mov) head->moves &= ~(mov) // removes an available move
#define isMove(mov) (head->moves&(mov)) // checks if the move is available
unsigned int number = 0 ; // number of answers written in the current file
unsigned int fno = 0 ; // file number
int count ; // number of places the horse has covered at any point
FILE *sol ; /* pointer to the file in which the answer is written
"SOLXXXXX.txt" where XXXXX is an unsigned integer */
void newPlace ( char ) ;// pushes a new move to the stack VISIT
void undo ( void ) ;// pops the stack i.e., undos the last move
char isKnown ( char ) ;// checks if a place has been visited by the horse
void copystack ( void ) ;// copies the answer to the sol file
void initProg ( void ) ;// resumes from previous run
char availability( char ) ;// checks if it is possible to move to a square
void newPlace ( char place ) {// push onto the stack
struct visited *new ;
new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
new -> place = place ;
new -> moves = availability ( place ) ; // compute availability and store
new -> next = head ;
head = new ;
count ++ ; // increment count, as a new move has been made
}
void undo ( ) { // pops the stack
VISIT *temp ;
if ( head == NULL ) // check if the stack is already empty
return ;
temp = head ;
head = head -> next ;
free ( temp ) ;
count -- ; // decrement count
}
char isKnown ( char place ) {
VISIT *temp = head ;
while ( temp ) { // surf through the stack to check if the place is visited
if ( temp -> place == place ) return 1 ;
temp = temp -> next ;
}
return 0 ; // executes only if place is not found
}
void copystack ( void ) { // executes when an answer is found
char move[64], i ; // to store the moves in order
VISIT *temp = head ;
for ( i = 63 ; i >= 0 ; i-- ) {
move[i] = temp -> place ;
temp = temp -> next ;
}
for ( i = 0 ; i < 64 ; i++ )
fprintf ( sol, "%d ", move[i] ) ;
fprintf ( sol, "\n" ) ;
}
void initProg ( ) {
FILE *recover ;
count = 0 ;
head = NULL ;
recover = fopen ( "Recover.txt", "rt" ) ;
/*
this file contains the no of last file opened say 1 (for sol1.txt)
number of answers stored in this file
count of the moves that are to be in the stack
data that are to be stored in the stack
*/
if ( recover != NULL ) {
char temp[10], fname[15] = "Sol", i, j ; // initialize fname
fscanf ( recover, "%u %u %d", &fno, &number, &count ) ;
// This block opens the last file created by the application
itoa ( fno, temp, 10 ) ;
strcat ( fname, temp ) ; // add sufix
strcat ( fname, ".txt" ) ; // add extenstion
sol = fopen ( fname, "a+" ) ; // open the fname
for ( i = 0 ; i < count ; i ++ ) {
// This block resumes the movements made
VISIT *new ;
int p, m ;
fscanf ( recover, "%d %d", &p, &m ) ; // data of a node
// push the data on to the stack
new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
new -> place = p ;
new -> moves = m ;
new -> next = head ;
head = new ;
}
fclose ( recover ) ;
}
else { // start from scrach
sol = fopen ( "SOL0.TXT", "wt" ) ;
newPlace ( 0 ) ; // place the horse in the top left corner on the board
}
gotoxy ( 2, 10 ) ;
puts ( "Press Space or Esc or Enter Key to pause after next result" ) ;
puts ( " Program will resume on next run with the help of recover.txt" ) ;
gotoxy ( 1, 1 ) ;
cprintf ( "File No: %u Solution No: %-5u", fno, number ) ;
}
// saves the current state in recover.txt
void savestate ( ) {
FILE *recover ;
char i, m[64], p[64], c ;
recover = fopen ( "Recover.txt", "wt" ) ;
// stores the file no, no of answers writen & count of moves in stack
fprintf ( recover, " %u %u %d ", fno, number, c=count );
// stores the moves in reverse order for ( LIFO of stack )
for ( i = count-1 ; i>-1 ; i-- ) {
p[i] = head->place;
m[i] = head->moves;
undo();
}
// stores data in file
for ( i = 0; i < c ; i++ )
fprintf ( recover, "\n %d %d",(int) p[i],(int) m[i] ) ;
fclose ( recover ) ;
}
main ( ) {
char filename[15] = "sol", temp[10] ;
void savestate ( void ) ;
clrscr ( ) ;
initProg ( ) ;
while ( head ) { // till the horse has no where left to go
char moves, c ; // c checks user input
if ( count == 64 ) { // if an answer is found
number ++ ;
// increment the number of answer in the current file
copystack ( ) ;
// save to file
cprintf ( "\rFile No: %u Solution No: %-5u", fno, number ) ;
// update screen
if ( number == 0x8000 ) { // if 0x8000 answers are writen goto next file
// Creates a unique file name on which the next result will be stored
number = 0 ;
// reset number of answers in the new file
fclose ( sol ) ;
// close the old file & open a new one
itoa( ++fno, temp , 10) ;
strcat ( filename, temp ) ;
strcat ( filename, ".txt" ) ;
sol = fopen ( filename, "wt" ) ;
printf ( "\a" ); // to notify that a multiple of 0x8000 answers have been found
}
if ( kbhit()) {// if user want to stop the prg then save its state
c = getch ( ) ;
if ( c == ' ' || c == '\x1B' || c == '\r' || c == '\n' )
savestate () ;
}
}
// Move horse if there is an availability
if ( isMove ( TL ) ) {
removMov ( TL ) ;
newPlace ( head->place - 17 ) ;
}
else if ( isMove ( TR ) ) {
removMov ( TR ) ;
newPlace ( head->place - 15 ) ;
}
else if ( isMove ( RT ) ) {
removMov ( RT ) ;
newPlace ( head->place - 6 ) ;
}
else if ( isMove ( RB ) ) {
removMov ( RB ) ;
newPlace ( head->place + 10 ) ;
}
else if ( isMove ( BR ) ) {
removMov ( BR ) ;
newPlace ( head->place + 17 ) ;
}
else if ( isMove ( BL ) ) {
removMov ( BL ) ;
newPlace ( head->place + 15 ) ;
}
else if ( isMove ( LB ) ) {
removMov ( LB ) ;
newPlace ( head->place + 6 ) ;
}
else if ( isMove ( LT ) ) {
removMov ( LT ) ;
newPlace ( head->place - 10 ) ;
}
else undo ( ) ;
}
}
char availability ( char place ) {
char moves = 0 ;
/*Check Boundary condition*/ /*Check if visited*/
if( place % 8!=0 && place >15 && !isKnown( place - 17))
moves |= TL ;
if( place % 8!=7 && place >15 && !isKnown( place - 15))
moves |= TR ;
if( place % 8<=5 && place >7 && !isKnown( place - 6 ))
moves |= RT ;
if( place % 8>=2 && place >7 && !isKnown( place - 10))
moves |= LT ;
if( place % 8!=0 && place <48 && !isKnown( place + 15))
moves |= BL ;
if( place % 8!=7 && place <48 && !isKnown( place + 17))
moves |= BR ;
if( place % 8>=2 && place <56 && !isKnown( place + 6 ))
moves |= LB ;
if( place % 8<=5 && place <56 && !isKnown( place + 10))
moves |= RB ;
/* The following may lead to losing some answers
but it speeds up the process!!*/
/* If the horse is near to the corner then visit the corner since there are just 2 ways to reach a corner '1 way in 1 way out'.*/
switch ( place ) {
case 41: if ( !isKnown( 56 ) ) moves &= BL ; break ;
case 50: if ( !isKnown( 56 ) ) moves &= LB ; break ;
case 53: if ( !isKnown( 63 ) ) moves &= RB ; break ;
case 46: if ( !isKnown( 63 ) ) moves &= BR ; break ;
case 13: if ( !isKnown( 07 ) ) moves &= RT ; break ;
case 22: if ( !isKnown( 07 ) ) moves &= TR ; break ;
}
return moves ;
}i want to help you, but youre using non-standard C that wont compile on either GCC or MS Visual C
you should never use Borland's CONIO functions.
so im either forced to port your code to something the rest of the world can use, or ignore it entirely and move along.
That's ok Should'nt be much of a problem, I'll Change the code and post agin.
I have never used bios.h much but I hope bioskey(1) will work the same way as kbhit()
#include<stdlib.h>
#include <stdio.h>
#include <bios.h>
#include<string.h>
/* Defination of all moves */
#define TL 0x01 // top left i.e., 2 squares up & 1 square left
#define TR 0x02
#define RT 0x04
#define RB 0x08
#define BR 0x10
#define BL 0x20
#define LB 0x40
#define LT 0x80
// stack which holds the position
typedef struct visited {
char place ; // varies from 0 to 63 representing a square
char moves ; // availabe moves -> every bit represents a possible move
struct visited *next ; // link to previous move
} VISIT ;
VISIT *head ; // contains the latest move made by the horse
#define removMov(mov) head->moves &= ~(mov) // removes an available move
#define isMove(mov) (head->moves&(mov)) // checks if the move is available
unsigned int number = 0 ; // number of answers written in the current file
unsigned int fno = 0 ; // file number
int count ; // number of places the horse has covered at any point
FILE *sol ; /* pointer to the file in which the answer is written
"SOLXXXXX.txt" where XXXXX is an unsigned integer */
void newPlace ( char ) ;// pushes a new move to the stack VISIT
void undo ( void ) ;// pops the stack i.e., undos the last move
char isKnown ( char ) ;// checks if a place has been visited by the horse
void copystack ( void ) ;// copies the answer to the sol file
void initProg ( void ) ;// resumes from previous run
char availability( char ) ;// checks if it is possible to move to a square
void newPlace ( char place ) {// push onto the stack
struct visited *new ;
new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
new -> place = place ;
new -> moves = availability ( place ) ; // compute availability and store
new -> next = head ;
head = new ;
count ++ ; // increment count, as a new move has been made
}
void undo ( ) { // pops the stack
VISIT *temp ;
if ( head == NULL ) // check if the stack is already empty
return ;
temp = head ;
head = head -> next ;
free ( temp ) ;
count -- ; // decrement count
}
char isKnown ( char place ) {
VISIT *temp = head ;
while ( temp ) { // surf through the stack to check if the place is visited
if ( temp -> place == place ) return 1 ;
temp = temp -> next ;
}
return 0 ; // executes only if place is not found
}
void copystack ( void ) { // executes when an answer is found
char move[64], i ; // to store the moves in order
VISIT *temp = head ;
for ( i = 63 ; i >= 0 ; i-- ) {
move[i] = temp -> place ;
temp = temp -> next ;
}
for ( i = 0 ; i < 64 ; i++ )
fprintf ( sol, "%d ", move[i] ) ;
fprintf ( sol, "\n" ) ;
}
void initProg ( ) {
FILE *recover ;
count = 0 ;
head = NULL ;
recover = fopen ( "Recover.txt", "rt" ) ;
/*
this file contains the no of last file opened say 1 (for sol1.txt)
number of answers stored in this file
count of the moves that are to be in the stack
data that are to be stored in the stack
*/
if ( recover != NULL ) {
char temp[10], fname[15] = "Sol", i, j ; // initialize fname
fscanf ( recover, "%u %u %d", &fno, &number, &count ) ;
// This block opens the last file created by the application
itoa ( fno, temp, 10 ) ;
strcat ( fname, temp ) ; // add sufix
strcat ( fname, ".txt" ) ; // add extenstion
sol = fopen ( fname, "a+" ) ; // open the fname
for ( i = 0 ; i < count ; i ++ ) {
// This block resumes the movements made
VISIT *new ;
int p, m ;
fscanf ( recover, "%d %d", &p, &m ) ; // data of a node
// push the data on to the stack
new = ( VISIT * ) malloc ( sizeof ( VISIT ) ) ;
new -> place = p ;
new -> moves = m ;
new -> next = head ;
head = new ;
}
fclose ( recover ) ;
}
else { // start from scrach
sol = fopen ( "SOL0.TXT", "wt" ) ;
newPlace ( 0 ) ; // place the horse in the top left corner on the board
}
puts ( "\n Press Space or Esc or Enter Key to pause after next result" ) ;
puts ( " \n Program will resume on next run with the help of recover.txt" ) ;
printf ( "\n File No: %u Solution No: %-5u", fno, number ) ;
}
// saves the current state in recover.txt
void savestate ( ) {
FILE *recover ;
char i, m[64], p[64], c ;
recover = fopen ( "Recover.txt", "wt" ) ;
// stores the file no, no of answers writen & count of moves in stack
fprintf ( recover, " %u %u %d ", fno, number, c=count );
// stores the moves in reverse order for ( LIFO of stack )
for ( i = count-1 ; i>-1 ; i-- ) {
p[i] = head->place;
m[i] = head->moves;
undo();
}
// stores data in file
for ( i = 0; i < c ; i++ )
fprintf ( recover, "\n %d %d",(int) p[i],(int) m[i] ) ;
fclose ( recover ) ;
}
main ( ) {
char filename[15] = "sol", temp[10] ;
void savestate ( void ) ;
initProg ( ) ;
while ( head ) { // till the horse has no where left to go
char moves, c ; // c checks user input
if ( count == 64 ) { // if an answer is found
number ++ ;
// increment the number of answer in the current file
copystack ( ) ;
// save to file
printf ( "\rFile No: %u Solution No: %-5u", fno, number ) ;
// update screen
if ( number == 0x8000 ) { // if 0x8000 answers are writen goto next file
// Creates a unique file name on which the next result will be stored
number = 0 ;
// reset number of answers in the new file
fclose ( sol ) ;
// close the old file & open a new one
itoa( ++fno, temp , 10) ;
strcat ( filename, temp ) ;
strcat ( filename, ".txt" ) ;
sol = fopen ( filename, "wt" ) ;
printf ( "\a" ); // to notify that a multiple of 0x8000 answers have been found
}
if ( bioskey(1)) {// if user want to stop the prg then save its state
c = bioskey ( 0 ) ;
if ( c == ' ' || c == '\x1B' || c == '\r' || c == '\n' )
savestate () ;
}
}
// Move horse if there is an availability
if ( isMove ( TL ) ) {
removMov ( TL ) ;
newPlace ( head->place - 17 ) ;
}
else if ( isMove ( TR ) ) {
removMov ( TR ) ;
newPlace ( head->place - 15 ) ;
}
else if ( isMove ( RT ) ) {
removMov ( RT ) ;
newPlace ( head->place - 6 ) ;
}
else if ( isMove ( RB ) ) {
removMov ( RB ) ;
newPlace ( head->place + 10 ) ;
}
else if ( isMove ( BR ) ) {
removMov ( BR ) ;
newPlace ( head->place + 17 ) ;
}
else if ( isMove ( BL ) ) {
removMov ( BL ) ;
newPlace ( head->place + 15 ) ;
}
else if ( isMove ( LB ) ) {
removMov ( LB ) ;
newPlace ( head->place + 6 ) ;
}
else if ( isMove ( LT ) ) {
removMov ( LT ) ;
newPlace ( head->place - 10 ) ;
}
else undo ( ) ;
}
}
char availability ( char place ) {
char moves = 0 ;
/*Check Boundary condition*/ /*Check if visited*/
if( place % 8!=0 && place >15 && !isKnown( place - 17))
moves |= TL ;
if( place % 8!=7 && place >15 && !isKnown( place - 15))
moves |= TR ;
if( place % 8<=5 && place >7 && !isKnown( place - 6 ))
moves |= RT ;
if( place % 8>=2 && place >7 && !isKnown( place - 10))
moves |= LT ;
if( place % 8!=0 && place <48 && !isKnown( place + 15))
moves |= BL ;
if( place % 8!=7 && place <48 && !isKnown( place + 17))
moves |= BR ;
if( place % 8>=2 && place <56 && !isKnown( place + 6 ))
moves |= LB ;
if( place % 8<=5 && place <56 && !isKnown( place + 10))
moves |= RB ;
/* The following may lead to losing some answers
but it speeds up the process!!*/
/* If the horse is near to the corner then visit the corner since there are just 2 ways to reach a corner '1 way in 1 way out'.*/
switch ( place ) {
case 41: if ( !isKnown( 56 ) ) moves &= BL ; break ;
case 50: if ( !isKnown( 56 ) ) moves &= LB ; break ;
case 53: if ( !isKnown( 63 ) ) moves &= RB ; break ;
case 46: if ( !isKnown( 63 ) ) moves &= BR ; break ;
case 13: if ( !isKnown( 07 ) ) moves &= RT ; break ;
case 22: if ( !isKnown( 07 ) ) moves &= TR ; break ;
}
return moves ;
}i wouldnt use bios.h either. it's just as bad.
why are you using such non-standard libraries, anyhow? is there a reason?
if you were maintaining mountains legacy code, say, on old crusty Win98 machines, i could see the reason behind sticking with it. (i had the misfortune of being in that situation a few years back...)
but if not, you should really drop these borland/windows archaic libraries like a bad habit.
....
Upon further review, i was able to extract your <conio.> dependent code and everything compiled okay.
ive since written an entirely new program from scratch, just to satisfy my curiosity. its not quite bug free, but i did it only using the STDIO and STRING libraries.
I understand a little. And also, could you help me with your code please
I use conio.h because thats what I have learned so far. Help me please, what is the better, how do I learn it & where do I get the compiler for it
for windows development, i use the Microsoft Visual C compiler. The "Express Edition" is completely free, and its the industry standard if you're developing PC apps. you can get previous versions (like 2005) if the 2008 doesnt work with your machine.
GCC would be the one for linux/unix
i mean, but hey, if you've got a project due, and you're allowed to use non-portable non-standard libraries like CONIO and BIOS... and you're used to workign with them, then dont change right now
just be aware, that these libraries will continue to haunt you and eat your soul until you exorcise them from your life.
as for my code, its working now just fine. and solves the Knight's Tour from any position on an 8x8 board in a few seconds .. would be a lot faster, but i display the board and moves to a terminal display, and that slows it down a lot.
but i can't just go and give it to you. that would defeat the point of you learning how to write your own code to solve problems.
all i did was use the old Warnsdorff's Algorithm. the algorithm itself is pretty simple, and has been around for some 200 years, to solve this exact problem.
.
its hard for me to understand exaclty what you're doing.
are you trying to solve the knight's tour, once for each of the 64 starting positions?
does it matter whether the solution is open or closed? what exactly are you storing and recovering in the text files?
because there are literally trillions (million-millions) of closed solutions. i cant imagine you needing to provide more than one solution for each starting square.
if it helps any, each 64-round "tour" should be easily solved by the computer program in less than 5 seconds, and thats just overhead for various I/O. without printing to screen, should be much less than 1 second.
if it's hanging on you, you've got some major problem(s) somewhere, probably an infinite loop.
I find the algorithm Interesting, thank you.
I'll soon work with it after my semester exams are over.
Just now I have installed Win XP after the virus attack. I learned my lesson. Ill never download softwares in college. I will install Visual studio soon & learn visual C.
About recover.txt, I was tempted to find answers exhaustively, & I knew, there must be lots & lots of answers, So I used recover.txt to save the progress of the program & then when I run it back, it would continue with next answers.
theres no "learning" visual c. if you're using the free MSVC compiler, it's still just C...
MS compiler and libraries still has non-ANSI portability problems compared to GCC (linux) but given MS history, it could be a lot worse.
it at least doesnt introduce addtional problems such as what Borland does.
sorry about your virus problems. i doubt it has anything to do with college.
i still don't quite understand what you were trying to do... were you trying to solve "EVERY" possible solution from each of the 64 squares? the closed solutions alone number around 26,000,000,000,000 solutions.
i dont think you're going to get that accomplished anytime soon on your old Dell PC.
Thank you, for those details. And then we download softwares during lab hours and take it home with our pen drive. Recently, some viruses and trojan horses spreaded all over the lan & to my pen drive. Thats how it happened. Anyway now the lab incharge is fixing it.
o i see. that's gotta suck. i guess i remember now, back in early 2000's, when a particularly nasty virus went around our university (a major state research institution) .... it really wreaked havoc on everyone for a good month or so. the good thing was, they finally got some competent security people in the sys admin department after that.
so this exercise of yours wasn't a homework assignement? just a personal project?
oh, and thanks for the comment. :)
.
hey prabkar
i posted my attempt at solving the Knights Tour. code and Windows-based executable are here
I read the program & I understood. It is a nice & Thanks a lot.
I want to write the same in windows based, and I will try & soon after I finish, I will ask for improvements. Ofcourse this would be my first windows based program.
And also I have never ever used enum before because I dint know where to use it. you have just shown me a way of using it, thanks for that too.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.