Knights tour problem

[Bazman]

I am wrintig some C++ code to try and resolve the knight's tour problem. That is to see whether it is possible for the knight chess price to move so that he visits all 64 squares of the ches board only once. (I know it's not possible but it's part of the course I am doing.)

I'm at the planning stage of my code and I'm happy I can do most of it. the only thing that perplexes me slightly is the following.

In order to make the code more effective each square of the chess board is given a number reflecting its "accessibility". The lower th number the less accesible it is. The corners unsurprisingly are the least accessible with accessibility 2.

int board[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,}

now the knight as you probably know can move two squares in either a vertical or horizontal direction + 1 square in a direction perpendicular to the first 2.

A centrally located has 8 possible moves which he can make. The idea is to move to the square that is least accesible. If there is a tie for the least accessible square you must run the analysis again on the two tied squares and so on till you find the a path that leads to an individual least accessible square.

The only was I saee to do it is to have an array with

value i j calling array calling x calling y


ie. eash time you have a tie you have create a new array detailing the tied squares and the array from which they were called. When the least accessible square is identified you can go back looking at the calling array to find the optimal path.

However this seems quite a clunky way of doing it. Involving several arrays that have to be stored in memory. Is there a better methos to resolve this problem? It seems almost like a recursive problem but it bracnches rather than producing a simpler case.

[Lindley]

I am wrintig some C++ code to try and resolve the knight's tour problem. That is to see whether it is possible for the knight chess price to move so that he visits all 64 squares of the ches board only once. (I know it's not possible but it's part of the course I am doing.)

Sure it's possible. Actually there are quite a lot of solutions.

I'm at the planning stage of my code and I'm happy I can do most of it. the only thing that perplexes me slightly is the following.

In order to make the code more effective each square of the chess board is given a number reflecting its "accessibility". The lower th number the less accesible it is. The corners unsurprisingly are the least accessible with accessibility 2.

int board[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,}

now the knight as you probably know can move two squares in either a vertical or horizontal direction + 1 square in a direction perpendicular to the first 2.

A centrally located has 8 possible moves which he can make. The idea is to move to the square that is least accesible. If there is a tie for the least accessible square you must run the analysis again on the two tied squares and so on till you find the a path that leads to an individual least accessible square.

The only was I saee to do it is to have an array with

value i j calling array calling x calling y


ie. eash time you have a tie you have create a new array detailing the tied squares and the array from which they were called. When the least accessible square is identified you can go back looking at the calling array to find the optimal path.

However this seems quite a clunky way of doing it. Involving several arrays that have to be stored in memory. Is there a better methos to resolve this problem? It seems almost like a recursive problem but it bracnches rather than producing a simpler case.

The "accessibility" thing is called an heuristic. What you've got is essentially a depth-first-search problem; you're trying to find some valid path that leads to a recursion depth of 64. The idea is that you're likely to find that a bit faster if you make smart, rather than random, decisions at each stage; and accessibility seems like a reasonable guideline for making those choices.

Does that help any?

[sszd]

(I know it's not possible but it's part of the course I am doing.)

As Lindley mentioned, it is most definitely possible. Back in my days of chess tournaments I once witnessed a grandmaster solve this blindfolded, giving each square a name from individuals randomly selected from the audience. And if I'm remembering correctly, it can be done from any starting point on the board.

[Bazman]

OK I'm now convinced it is possible.

I understand what is being done in terms of using a heuristic. My issue is how to implement it efficiently in C++.

The only solution I can think of is to create a new array every thime an equal pair is found. Which keeps track of the equal vlaue where the equal squares are on the chess board and also the square that they were each called from previously.

When an individual least square is identifies you would then loop to identify the optimal path before continuing to find the next least square or sequence of squares.

My problem is that my solution requires alot of array sto be created ans stored all of which contain quite alot of information.

Is there another more efficient way to do this?

[Lindley]

I'm not clear on precisely what your problem is with equal values, but often graph search algorithms make use of a priority queue for squares in the boundary, and expand whichever is best out all possible next positions. Google the A* algorithm, that's probably similar to what you need to do.

[Bazman]

Hi Lindley,

Thanks again for all your help. The A* algorithm does look very interesting and I will certainly follow it up.

However I am following Deitel & Deitels C++ how to program. The problem i am working on come from chapter 4 of the book on arrays. So far all we have covered is basic logic statements, how to define functions and pass by reference and basic arrays. So I think the A* solution may be getting away from what the authors intended.

I'll draft up some code of how I am attemting to answer the problem. I do feel my approach is rather cumbersome but at least it'll be clearer if I code it up.

Anyway what is a good book to introduce someone to the A* algorithm and algorithms more generally?

[Liminal]

Look up something called Warnsdorff's heuristic. I was given the same assignment myself, and this helped quite a bit... I don't see A* being much help to you here...

[Bazman]

Well here's my take,

So far I have a 3 dimensional array. dim 1 = the possible moce at time t, dim 2 records the infor for the saure at each possible move at time t, and dim 3 records the moves for each subsequent time step on that branch.

I now need to add a fourth dimension to account for the branching at each time step. Obviously I am having trouble viusalising this. Any hints on how to arganise higher dimensional matrices in your head would be much appreciated.

Can I think of them as a series of 3*8*64 rectangular blocks?

Like I say its going ot be pretty resource intensive this program and maybe I am going about this wrong alternative sugestions welcome.

 

#include <iostream>
using std::cout;
using std::cin;

#include <ctime>

#include <cstdlib>

void testmove( int [][8], int [][3][64],int [][8], int );
void findleast( int [][3][64],int, bool&, int);

int main()
{
	
//	cout << "Please enter starting square x vlaue then y vlaue: ";
//	cin >> i >> j;

	//start in top tight corner

	int i=0; 
	int j=0;

	const int size =8;
	
	int board[size][size] = {0};
	int moves[size][3][64] = {0};
	bool test= 0;  // used to test whether there are muliple least accessibe squares
	int counter=0;

	board[i][j] = 1;
	moves[counter][0][0]=board[i][j];
	moves[counter][0][1]= i;
	moves[counter][0][2]= j;


int access[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,};

					
		do {
			testmove( access, moves, board, counter);	
			counter++;
			findleast( moves, size, test, counter );
			
		} while ( test == 1);

return 0;
}


void testmove( int access[][8],int moves[][3][64],int board[][8], int counter)
{
	const int horizontal[8] ={2,1,-1,-2,-2,-1,1,2};
	const int vertical[8] = {-1,-2,-2,-1,1,2,2,1};
	
	for ( int k = 0; k < 8; k++)
	{if ( moves[counter][k][1]+ horizontal[k] < 0 || moves[counter][k][1] + horizontal[k] > 7 )
			continue;
		if ( moves[counter][k][2]+ vertical[k] < 0 || moves[counter][k][2] + vertical[k] > 7 )
			continue;
			if (board[moves[counter][k][1]+ horizontal[k]][moves[counter][k][2] + vertical[k]] =! 0)
				continue;
	
		moves[counter+1][k][0]= access[moves[counter][k][1]+horizontal[k]][moves[counter][k][2]+vertical[k]];
		moves[counter+1][k][1]= moves[counter][k][1]+horizontal[k];
		moves[counter+1][k][2]= moves[counter][k][2]+vertical[k];
	}
	
}


	
void findleast ( int moves[][3][64], int size, bool& test, int counter)
{
	int least=9;
	
	
	for ( int k =0; k < size; k++)
		if ( moves[counter][k][0] < least	)
			least = moves[counter][k][0];
	
	int sort = 0;

	for ( k = 0; k < size; k++)
	{if ( moves[counter][k][0] == least )
	{ if (k == sort)
			{continue;}
			 else
			 {moves[counter][sort][0] = moves[counter][k][0];
			  moves[counter][sort][1] = moves[counter][k][1];
			  moves[counter][sort][2] = moves[counter][k][2];
			  sort++;
			  if (sort > 1)
			  test=1;}
	}
	moves[counter][k][0] = 0;
	moves[counter][k][1] = 0;
	moves[counter][k][2] = 0;
	}
}

[Lindley]

If I were writing a Knight's Tour program, it'd work something like this:

1) Mark current node visited.
1a) If depth == 64, done.
2) Store a list of next-moves sorted by accessibility
3) For each next-move,
3a) If next-move is not visited, recurse with depth = depth + 1.
4) Mark current node unvisited.
5) Return (with depth = depth - 1).