Knight tour (working... I think... but inefficient) help.

Elsydeon · #1 21-Sep-2005, 07:25

It handles 5x5 & 6x6 board inputs fine. I get to 7x7 and it goes infinitely. I haven't managed to sit through and get an output yet. Is it a logic error in the code I'm missing that just doesn't happen to hit until that point, or is it just horribly inefficient? If so, is there any tweaking I can do to make it better?

Semi-urgent, heh. Due soon, I've been up all night struggling with this little problem. Any help is appreciated.

I just don't get why it isn't able to eventually find a solution. To me it seems like it should work..... slowly, but work nonetheless.

CPP / C++ / C Code:

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>


class knightTour {
  //Handles logic problem of Knight's tour
  //Maximum board size 20x20
public:
  bool validMove(int row, int col, int size);
  void printBoard(int size);
  void recurAlg(int row, int col, int size, int count);
  int checkBoard(int size);

};//class knightTour

const maxSize=20;//Boards size
int boardType[maxSize][maxSize];//Declares array representing board
int count=1;

void main(){
  knightTour check;
  int row, col, size;
  row=0, col=0, size=8;

/*
  cout<<"Please enter the size of the board you wish to use between 5x5 and 20x20(5 for 5x5 20 for 20x20)."<<endl;
  cin>>size;
  size;

  if(size<=maxSize){
  for(int a=0;a<=maxSize;a++){//Sets board to clear (all 0's) with for loops
	  for(int b=0;b<=maxSize;b++){
		  boardType[a][b]=0;
	  }
  }
  //Take input
cout<<"Please enter the start location of the knight:"<<endl;
cout<<"Starting row: ";
cin>>row;
cout<<endl<<"Starting col: ";
cin>>col;
check.validMove(row, col, size);

  //Output results
  	}*/
  check.recurAlg(row, col, size, count);
  check.printBoard(size);
}

bool knightTour::validMove(int row, int col, int size){
  if(row>=size || col>=size ||  row<0 || col<0){//Test for chosen location being within board dimensions
    return 1;
    
  }
  else{//Check to see if location was not previously visited
    if((boardType[row][col]) == 0){
      return 0;
      
    }
    else{//returns 1 if location previously visited
      return 1;
      
    }
    }
}

void knightTour::printBoard(int size){
  for(int c=0;c<size;c++){//Sets board to clear (all 0's) with for loops
	  for(int d=0;d<size;d++){
		  if(d==size-1){
			cout<<"| "<<boardType[c][d]<<" |"<<endl;
		  }
		  else{
			cout<<"| "<<boardType[c][d]<<" ";
		  }
	  }
  }
	
}

int knightTour::checkBoard(int size){
	int rows, cols, checker;
			for(rows=0;rows<size;rows++){
				for(cols=0;cols<size;cols++){
					if(validMove(rows,cols,size)!=1){
						checker=0;
					}
				}
			}
			return(checker);
}

void knightTour::recurAlg(int row, int col, int size, int count){
	//8 potential space
int checked;
boardType[row][col]=count;
		if(validMove(row+2, col+1, size)!=1){
			count++;
			recurAlg(row+2, col+1, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row+2][col+1]=0;
				count--;
			}
		}
		if(validMove(row+2, col-1, size)!=1){
			count++;
			recurAlg(row+2, col-1, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row+2][col-1]=0;
				count--;
			}
		}
		if(validMove(row+1, col+2, size)!=1){
			count++;
			recurAlg(row+1, col+2, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row+1][col+2]=0;
				count--;
			}
		}
		if(validMove(row+1, col-2, size)!=1){
			count++;
			recurAlg(row+1, col-2, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row+1][col-2]=0;
				count--;
			}
		}
		if(validMove(row-2, col+1, size)!=1){
			count++;
			recurAlg(row-2, col+1, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row-2][col+1]=0;
				count--;
			}
		}
		if(validMove(row-2, col-1, size)!=1){
			count++;
			recurAlg(row-2, col-1, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row-2][col-1]=0;
				count--;
			}
		}
		if(validMove(row-1, col+2, size)!=1){
			count++;
			recurAlg(row-1, col+2, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row-1][col+2]=0;
				count--;
			}
		}
		if(validMove(row-1, col-2, size)!=1){
			count++;
			recurAlg(row-1, col-2, size, count);
			checked=checkBoard(size);
			if(checked==0){
				boardType[row-1][col-2]=0;
				count--;
			}
		}

			checked=checkBoard(size);
			if(checked==0){
				boardType[row][col]=0;
				count--;
			}
}

maprich · #2 21-Sep-2005, 11:01

Generally your code seems good to me. You mention it working well with 5x5 and 6x6 boards. I think that by using iteration instead of recursion you could make your code more effective.

Loop solution may be a bit complicated too but I would imagine that it could have some array to keep track of the sequence of moves and then modify the the array gradually as the loop goes around. Hard to explain but basically you can linearize every iteration problem by thinking how your (single) processor actually executes your program. By iteration you avoid the overhead of multiple function calls required in recursion.

Mathematical shortcut to this problem would be really cool. I calculated for my amusement that the amount of paths that the program has to check is somewhere below 49*8^48 ~= 10^45 for 7x7 board. Because only solutions are full length paths it follows that most paths are much shorter ending in a "blind alley". Therefore the amount must be much less.

Interesting idea that comes to mind is a possibility of fractal solutions for modulo 2 boards. E.g. you have 8x8 board. Then if you have solution to a 4x4 board such that the horse can move legally from one 4x4 tile to the next 4x4 tile then you have solution to the 8x8 board.

davekw7x · #3 21-Sep-2005, 11:56

Quote:

Originally Posted by Elsydeon

It handles 5x5 & 6x6 board inputs fine. I get to 7x7 and it goes infinitely. I haven't managed to sit through and get an output yet.

CPP / C++ / C Code:


int knightTour::checkBoard(int size){
	int rows, cols, checker;
			for(rows=0;rows<size;rows++){
				for(cols=0;cols<size;cols++){
					if(validMove(rows,cols,size)!=1){
						checker=0;
					}
				}
			}
			return(checker);
}

There is a bug here: you don't initialize checker.

CPP / C++ / C Code:

.
    int rows, cols, checker;
    checker = 1;

However, this doesn't solve your problem.

In fact your backtracking needs some work. If you give it a starting position for which there is no path, it hangs up rather than bailing out.

A couple of tests:

with initial row = 0, col=0, size = 6 it finds a path with 1,553,272 recursive calls to recurAlg()

with inital row = 2, col = 1, size = 6 it hangs up (I stopped it after several hundred million recursive calls)

with initial row = 0, col = 0, size = 7 it hangs up (I stopped it after several hundred million recursive calls)

with initial row = 3, col = 3, size = 7 it finds a path with 46,253,900 recursive calls to recurAlg()

As for efficiency: there are a number of places that the code can be made to run faster, but I think the first task is to make it work.

Regards,

Dave

davekw7x · #4 22-Sep-2005, 10:49

Quote:

Originally Posted by davekw7x

There is a bug here: you don't initialize checker.

However, this doesn't solve your problem.

In fact your backtracking needs some work.

with initial row = 0, col=0, size = 6 it finds a path with 1,553,272 recursive calls to recurAlg()

with inital row = 2, col = 1, size = 6 it hangs up (I stopped it after several hundred million recursive calls)

with initial row = 0, col = 0, size = 7 it hangs up (I stopped it after several hundred million recursive calls)

with initial row = 3, col = 3, size = 7 it finds a path with 46,253,900 recursive calls to recurAlg()

As for efficiency: there are a number of places that the code can be made to run faster, but I think the first task is to make it work.

Seeing no further response from the original poster (I guess the deadline for assignment submission has passed), I will indulge myself in responding to my own post, in case others might be interested:

I had hoped that my post would give some motivation for investigating what's really happening. The comment about hanging up when there is no path wasn't intended to be misleading, but, in fact, doesn't really describe the problem.

First of all: There was basically nothing wrong with the approach in the original post, and is a pretty good example of appropriate use of recursion. But, as I said, a little work might be in order. Look at what you are really doing with the backtracking: When should count be incremented? What is the meaning of the value of the variable count? How do you know when you are through?

Anyhoe, I didn't want to do any dramatic changes; I wanted to see what I could learn using this basic approach.

I cleaned up the program a little and ran it with a few fixed starting values, for example size = 6, row = 0, column = 0. I had placed a statement in the beginning of recurAlg():

CPP / C++ / C Code:

globalcount++;

Where globalcount is a global variable that I had initialized to 0. Now, I used gcc, which has the variable type "long long" that is a 64-bit number.

When (if) the program completed, it printed out the value of global count, but if it ran too long, I hit ctrl-c to terminate it. In order to see its progress, I put the following so that I would know how far it got before I lost patience.

CPP / C++ / C Code:

globalcount++;
if (globalcount % 1000000 == 0) {
  cout << "globalcount = " << globalcount << endl;
}

(Old-time hardware guys, in particular, call this "instrumenting" the program. That is, some special "probe" is put in place to give some visibility. In particular, this operation at the beginning of the recursive function slows down the program somewhat, and I will take it out of the "production" release.)

The good news is that, for the tough cases, the counter continues to increment, showing me that at least the program is continuing to execute and not going off into "never-never land" where some programs end up (an infinite loop or stack overflow or something).

Now: the program seems to work for 4x4 matrices (no solution is found, and the maximum number of recursive calls seems to be something like 2,223 for various starting points).

For 5x5 matrices, I tried a few different starting points, and I always got results. The maximum number of recursive calls seems to be something like 1,829,421.

Hmmm: it goes from a couple of thousand to a couple of million? I wonder how many calls are really required for a 6x6 board for various starting points.

At this point, it may be time to do a little research (on the web, of course). Just how many different moves are there for a knight starting in a given square in attempting to get to visit all squares on a 6x6 board? Lots, it turns out. So, I fired up the program with size = 6, row = 2, col = 1, and went out to have a nice vegetarian dinner. (Now, if you thought you saw me in a bar at dinnertime last night, I would like to point out that beer is made from grain, and potato chips are vegetables --- right?) As it turned out, it only took about 10 minutes to go through the approximately 561,707,725 recursive calls to find a solution. (Later, after cleaning up the code a little more, I found that that isn't even the worst case: a starting point of (0, 3) required 2,333,012,685 recursive calls to find a solution with this method for a 6x6 board.)

Note that from a given starting position, there may be more than one solution (I made sure that the program would quit after it found one complete path that would cover the board for a given starting position.)

Bottom line: The number of possible board positions that would have to be tested may be much larger than the 2x10 to the ninth power that I observed with this program. The number for a 7x7 board: well, there aren't enough microseconds from now until the next ice age to try all possible solutions with this method.

A few notes about efficiency:

Since the variable "size" doesn't change anywhere once the program has started, It seems wasteful to pass it as an argument everywhere. C programmers could use a global variable here. Now, I usually recommend against global variables, but since the only place that it is given a value is in main(), it doesn't present a risk in this case. Now, in this C++ program, since we are using a class, maybe just letting size be a member variable would be better than passing it as an argument in every function call. You can test the efficiency by doing something like the following:

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  time_t time1, time2;
.
.
.
      time1 = time(0);
      globalcount = 0;
//    set up row, col, size, etc. and call recurArg()
      time2 = time(0);
      cout << "Elapsed time = " << difftime(time2, time1) << endl;
      cout << "globalcount = " << globalcount << endl;

Now, once you get this working, pick a size and starting point that takes a minute or so. You might try size=6, row=2, col=1, for example.

Now try to find places to speed things up:

Is it really necessary to test the entire board every time? It seems to me that if you enter recursArg with its "count" argument equal to size*size, that you are through! (If you do it right, you only call recursArg when its row,col arguments represent a legal move. If you do it right, its count argument tells what value you want to store in that cell. If the count value for a 5x5 matrix is equal to 25, then that's the last one, and you are through.) Maybe we could make recursArg return a bool value (true if it found a path, false if not).

By the way: Why did you declare validMove to be a bool type function, then made it return a value of 0 (same as boolean false) when it's a valid move and a value of 1 (same as boolean true) when it's invalid? Bad nomenclature; bad use of boolean data type for C++. This doesn't affect the efficiency, but it seems particularly obnoxious to me as a guy who is frequently called in to debug code from some long-departed (or recently-departed) colleague who left things "almost working except sometimes gives the wrong answer."

Anyhow: once you get things to "almost working", and you decide to try size = 7, initial (row,col) = (0,0), you might find that it takes something like 3,728,696,695 recursive calls (about 538 seconds on my modest Athlon 2400 system). As you are waiting for the result with initial (row,col) = (0, 1), you might browse the web and see why people have gone to some trouble to find more efficient methods.

It's sobering to look at numbers like 10 to the power 17 and 10 to the power 19 when they talk about the number of possible moves, and may give some insight as to how a seemingly straightforward problem, that isn't really very difficult to program, may not be very practical.

You might want to fall back to smaller boards and try other methods for speeding things up. Some people have said that C++ things like classes slow things down. You could try to eliminate the class, and just use regular functions and variables. You could even make it a pure C program (Printf instead of cout is about the only other thing to change, other than using int instead of bool.) Didn't seem to make much difference for me. Other search strategies?

Other considerations: My globalcount variable only shows the total number of recursive calls. It doesn't show the maximum depth of recursion. In some cases this might be a limiting factor and might cause the program to terminate prematurely. If you increment some global variable every time you enter the recursive function and decrement it when you return, you can keep track of the maximum depth (at the cost of slowing down program execution, of course).

What's the point? Insight.

Regards,

Dave

"The purpose of computing is insight, not numbers."
---Richard W. Hamming

WaltP · #5 22-Sep-2005, 12:07

Interesting analysis. Makes me want to program the solution myself. Maybe two different versions:
Depth-first version to compute the first good path from a given starting point
Breadth-first to compute all good paths from a given starting point.

Unfortunately, I think I'd need a few terragigs and long long long long's for the breadth first...

Elsydeon · #6 25-Sep-2005, 20:23

I'm still around. I actually just got my home internet hooked up. The due date passed and I turned in something similar (a few tweaks) to what I posted.

I wanted to use a global, but had little choice. Professor refuses to accept them. There was probably a better way to go about it within that restriction, but by the time I noticed it would be a problem I was too far in to bother changing it.

My main concern (beyond grades) is whether or not I understand recursion in general. If my approach was sound and all that. We were told to do a brute force recursion approach... from what I'm getting I didn't do a horrible job with it at least. It worked, if slowly.

As for the bool thing and 1 vs 0... I'm just new. None of my programming classes made much use of bools in the labs, so I didn't know what the standard was, I just wanted the thing to work.

My mind was put at ease when I went to the lab and the rest of the class had programs on par with mine so far as speed went. I was nervous thinking I just had a bad program.

I appreciate the responses. And of course I'm probably about to post another one if I don't figure out where I'm going with it (program to keep track of stocks) so you may see me soon.

davekw7x · #7 26-Sep-2005, 08:15

Quote:

Originally Posted by Elsydeon

I wanted to use a global, but had little choice. Professor refuses to accept them.

If your professor doesn't allow globals, he/she is doing you a favor. In certain cases, manifest "constants" (or global variables whose value doesn't change during program execution) can be justified, but I think it's generally something to avoid. After you have more experience, you may have enough insight to know what these special cases are, but for now, don't do it. (Kind of like goto statements: just say, "No!")

Quote:

Originally Posted by Elsydeon

My main concern (beyond grades) is whether or not I understand recursion in general. If my approach was sound and all that. We were told to do a brute force recursion approach... from what I'm getting I didn't do a horrible job with it at least. It worked, if slowly.

You posted a good effort, and I learned a lot by sneaking a peek inside your routines and probing around. It's kind of interesting to try to figure out just what is the maximum number of operations required to find a path for a given size board (and a little sobering to come up with numbers like 10 to the power 17). Simple little things (like putting a counter to see how many recursive calls were required to come up with a solution) can be used in debugging all kinds of programs.

Quote:

Originally Posted by Elsydeon

so you may see me soon.

It has been a pleasure.

Regards,

Dave

cable_guy_67 · #8 26-Sep-2005, 08:25

I too have been lurking along following this thread. It is quite an eye opener when orders of magnitude start ramping numbers up and has made me think a little harder about storage sizes.

This has been a much needed walk down recursion lane for me as my few attempts have been very limited.

It's always a good day when I learn something new...Thanks!

Mark

kobi_hikri · #9 26-Sep-2005, 16:19

Hey guys.

I found this thread very interesting too. Dave's responses always make me think, and this time isn't different.

When I studied algorithmics I encountered two approaches that might help solve this given problem in a more efficint way :

1. Dynamic programming.
We could create two arrays of bool in the memory with sizes NxN.
Than, in one array we track the current position of the knight and on the other we mark "visited" or "not visited".
I programed a solution for the "stain size" problem (if you want, I'll explain about this problem) which used Dynamic programing and was very fast.

2. Reduction to graph theory.
We could create NxN nodes in the memory.Each node represents a square on the board.
Now, We could have a counter that counts the number of nodes in the graph.
We start with NxN nodes and 0 arcs.
Each time we add a node, it means we found a move (I'm not referring to the way we find the next move here).
We will stop when the number of nodes in the graph is NxN.

Those are just basic ideas and need to be elaborated.

Best regards,
Kobi Hikri.

P.S

Here is an interesting link : Knight Tour problem

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Re: Still working on the BBCodes...	admin	GIDNetwork™	2	11-May-2005 22:28
knight tour (chess program)	kai85	C++ Forum	10	25-Mar-2005 06:12
Knight tour (arrays help needed)	dilmv	C++ Forum	7	18-Oct-2004 14:31

Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.

Re: Knight tour (working... I think... but inefficient) help.