Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Aug 31st, 2011, 2:39 PM   #1
David321
Newbie
 
Join Date: Aug 2011
Posts: 11
Rep Power: 0 David321 is on a distinguished road
Knights Tour problem

I posted this on Daniweb and no one helped me there so if it looks familiar that's why. Maybe someone here can help me.

I've been having some trouble making the knights tour (getting a knight to go around a chessboard without touching the same square twice) work correctly. Right now the max amount of moves I can get out of it is 59. I can't figure out any reason why it shouldn't go to 64 moves (which means it's completed). I just learned about multidimensional arrays, so if you're solution is even slightly advanced it probably won't help me. Please help me! Here's my code:
#include <iostream>

using std::cout;
using std::endl;
using std::cin;

const int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
const int vertical[8]={-1,-2,-2,-1,1,2,2,1};

int moveKnight(int board[][8]);
bool check( int board[][8]);
bool anyValid(int board[][8],int row, int column);
void printArray(int [], int size);
void resetArrayOneD(int [], int);
void resetArrayTwoD(int [][8],int);

int main()
{
	int board[8][8];
	int status=0;
	
	resetArrayTwoD(board,8);
	status=moveKnight(board);
	
	system("pause");
	return 0;
}

int moveKnight(int board[][8])
{
	int currentRow=0;
	int currentColumn=0;
	int moves[64];
	int counter=0;

	for (int i=0;i<64;i++)
		moves[i]=-1;

	for (int i=0; i<=7;i++)
		for (int j=0;j<=7;j++)
		{
			//reset starting point and board
			resetArrayTwoD(board,8);
			resetArrayOneD(moves,64);
			counter=0;

			currentRow=i;
			currentColumn=j;
			
			board[i][j]=1;
			
			for (int k=0;k<=7;k++) //cycle through the moves possible
				if (currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 &&  board[currentRow+vertical[k]][currentColumn+horizontal[k]]==0 )
				{
					//if it's not off the board and the spot wasn't taken
					currentRow+=vertical[k];
					currentColumn+=horizontal[k];
					board[currentRow][currentColumn]=1;
					moves[counter]=k;
					counter++;
					//reset moves to -1, the for will increment it to 0
					k=-1;
				}
				else if ((currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 && anyValid(board,currentRow, currentColumn)==0)||k==7)
				{
					//if it's not off the board but there are no valid moves;  we need to backtrack
					//we are taking away the PREVIOUS move
					do
					{
					counter--;
					board[currentRow][currentColumn]=0;
					currentRow-=vertical[moves[counter]];
					currentColumn-=horizontal[moves[counter]];
					//have to reset some moves
					k=moves[counter]+1;
					//get rid of the last move recorded
					moves[counter]=-1;
					}while (k>7);
				}
				else if (counter==63)// && check(board))
				{
					//did it
					cout<<"Start at row "<<i<<" column "<<j<<endl;
					printArray(moves, 64);
					return 1;
				}
		}

}

void printArray(int a[], int size)
{
	for (int i=0; i<size;i++)
		cout<<a[i]<<endl;
}

//see if it completed the tour
bool check (int board[][8])
{
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			if (board[i][j]==0)
				return 0;
				
	return 1;
}

//check if there are any valid moves to be made by cycling through the moves array
//0 means no moves left
bool anyValid(int board[][8],int row, int column)
{
	for (int i=0;i<7;i++)
	{
		if (row+vertical[i]<8 && row+vertical[i]>=0 && column+horizontal[i]<8 && column+horizontal[i]>=0 && board[row+vertical[i]][column+horizontal[i]]==0)
			return 1;
	}

	return 0;
}

void resetArrayOneD(int a[], int size) //resets to -1
{
	for (int i=0;i<size-1;i++)
	{
		a[i]=-1;
	}
}

void resetArrayTwoD(int a[][8], int size)
{
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			a[i][j]=0;
}
David321 is offline   Reply With Quote
Old Aug 31st, 2011, 3:50 PM   #2
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 18 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Knights Tour problem

You need to decrement k after backtracking, to account for the fact that the for loop is going to increment k to where it should be.

...
}while (k>7);
k -= 1;
...

This kind of nonsense is the sort of reason you shouldn't try to use a for loop for any purpose other than iterating over some sequence in a predetermined manner. It would be easier to reason and to read if you used a while loop. Incidentally, I think you could eliminate 'k' completely by using your 'moves' array.

Also, you shouldn't really need your "anyValid" function (aside: it should be i<8 in this method, not i<7), if you're careful about how you handle your three cases. This is because there won't be a valid move if you've managed to try each k and the counter is less than 63, since you've now tested every other move from this board setup in previous iterations. Similarly, k will eventually get past 7 if there aren't any valid moves, so you don't need to make your backtrack condition so eager.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Old Sep 2nd, 2011, 2:29 AM   #3
David321
Newbie
 
Join Date: Aug 2011
Posts: 11
Rep Power: 0 David321 is on a distinguished road
Re: Knights Tour problem

Thank you for your help, I really do appreciate it. I went through your suggestions in my code, and really feel I gained from your advice.
Quote:
Incidentally, I think you could eliminate 'k' completely by using your 'moves' array.
I don't think I understand what you're saying. How would I do that?
David321 is offline   Reply With Quote
Old Sep 2nd, 2011, 1:29 PM   #4
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 18 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Knights Tour problem

Basically, instead of keeping moves[counter] at -1 until you find a valid k, you would do away with k and increment moves[counter] instead. Then moves[counter] can be substituted for k. To backtrack, you would decrement moves[counter]. You might need to make some other subtle changes in order to keep your backtracking loop correct, but that's the gist of it. The hope is that the code should become easier to follow because you will have fewer variables that are dependent on each other.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Knight's Tour program need help fistpunch Java 16 Feb 7th, 2011 4:30 PM
Serious RichTextBox problem most hacker C# 0 Feb 27th, 2010 4:23 AM
How to develop problem analysis skills to enable one to decipher a given problem before coding in C++ Man G C++ 7 Apr 16th, 2009 4:49 AM
Knights Tour Probelm budder8818 Java 13 Feb 13th, 2009 5:14 AM
Problem solving ReggaetonKing Software Design and Algorithms 7 Jan 4th, 2008 1:49 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 8:46 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC