March Madness - Knights Tour

On Tuesday night at the meeting we were discussing the programs for March Madness. I was talking about 8 queens and Phil mentioned Knights Tour, so i just HAD TO TRY IT. It was a bit more challenging that 8-queens.

No I am not a chess player, this is just a good programming problem.

This is also brute force, put a Knight in the first location and keep trying moves until you fill up the board. If you cant find a move into a space that has not been touched before, back up to the previous move and try it again.

The Arduino on Unix library I wrote on day 2 came in VERY useful. Debugging on Arduino would have been very painful because it took so long to come up with an answer.

On Unix (MacOSX) it took .3 seconds

On the Arduino it took 5 minutes and 57 seconds

//************************************************************************

UNIX (MacOSX command line)


Knights Tour brute force
move Index= 63  zeroCount= 0
+------------------------+
|1  50 59 46 41 36 61 64 |
|58 47 56 49 60 63 40 37 |
|51 2  45 42 39 24 35 62 |
|44 57 48 55 16 33 38 23 |
|3  52 43 32 25 22 15 34 |
|28 31 54 17 14 11 8  21 |
|53 4  29 26 19 6  13 10 |
|30 27 18 5  12 9  20 7  |
+------------------------+

ALL DONE!!!!
Total itterations=3424303
real	0m0.330s
user	0m0.323s
sys	    0m0.004s

//************************************************************************
Arduino

Knights Tour brute force


+------------------------+
|1  50 59 46 41 36 61 64 |
|58 47 56 49 60 63 40 37 |
|51 2  45 42 39 24 35 62 |
|44 57 48 55 16 33 38 23 |
|3  52 43 32 25 22 15 34 |
|28 31 54 17 14 11 8  21 |
|53 4  29 26 19 6  13 10 |
|30 27 18 5  12 9  20 7  |
+------------------------+



ALL DONE!!!!
Total itterations (boards) checked 3424303
total seconds=357
hours=0
minutes=5
seconds=57





//************************************************************************
//*	Kinghts tour
//*	
//*		(C) 2010 by Mark Sproul
//*		Open source as per standard Arduino code
//*	http://obereed.net/queens/solution.html
//************************************************************************

#include 
#include 
#include 
#include 
#include 

//#define _COMPILE_FOR_UNIX_
#ifdef _COMPILE_FOR_UNIX_
	#include	"arduino_unix.h"
#else
	#include "WProgram.h"
	#include "HardwareSerial.h"
#endif


enum 
{
	kMove_Up_Left	=	0,
	kMove_Up_Right,
	kMove_Right_Up,
	kMove_Right_Down,
	kMove_Down_Right,
	kMove_Down_Left,
	kMove_Left_Down,
	kMove_Left_Up,
	
	kMove_Last

};


int	gMoveOffsets[]	=	
{
	-1,	2,		//	move 5
	1,	2,		//	move 4

	2,	1,		//	move 3
	2,	-1,		//	move 2

	-2,	1,		//	move 6
	-2,	-1,		//	move 7

	-1,	-2,		//	move 0
	1,	-2,		//	move 1


	
};


typedef struct 
{
	int	boardXpos;
	int	boardYpos;
	int	nextMove;
} KNIGHTS_MOVES;


#define	kMaxMoves	70

unsigned short	gChessBoard[20][20];
unsigned long	gLoopCounter;
int				gValidCount;
int				gMoveIndex;

KNIGHTS_MOVES	gKMoves[kMaxMoves];

//************************************************************************
int	CountZerosOnBoard(void)
{
int	zeroCount;
int	xx, yy;

	zeroCount	=	0;
	for (yy=1; yy<=8; yy++)
	{
		for (xx=1; xx<=8; xx++)
		{
			if (gChessBoard[xx][yy] == 0)
			{
				zeroCount++;
			}
		}
	}
	return(zeroCount);
}


//************************************************************************
void	PrintChessBoard(void)
{
int		ii;
int		jj;
int		zeroCount;
char	boardSeperator[]	=	"+------------------------+";

	zeroCount	=	CountZerosOnBoard();
	
//	Serial.print("move Index= ");
//	Serial.print(gMoveIndex);
//	Serial.print("  zeroCount= ");
//	Serial.print(zeroCount);
	Serial.println();

	Serial.println(boardSeperator);
	for (ii=1; ii<=8; ii++)
	{
		
		Serial.print("|");
		for (jj=1; jj<=8; jj++)
		{
			Serial.print(gChessBoard[jj][ii]);
			if (gChessBoard[jj][ii] < 10)
			{
				Serial.print(" ");
			}
			Serial.print(" ");
		}
		Serial.println("|");
	}
	Serial.println(boardSeperator);
	Serial.println();
}


//************************************************************************
void setup()
{
int	ii, jj;

	Serial.begin(9600);
	Serial.println();
	Serial.println("Knights Tour brute force");

	//*	initialize the board
	for (ii=0; ii<=8; ii++)
	{
		for (jj=0; jj<=8; jj++)
		{
			gChessBoard[ii][jj]	=	0;
		}
	}

	for (ii=0; iiboardXpos;
	currentYpos	=	currentLocation->boardYpos;
	currentMove	=	currentLocation->nextMove;
	
	keepLooking	=	true;
	currentMove++;
	while ((currentMove < kMove_Last) && keepLooking)
	{
		newXpos	=	currentXpos + gMoveOffsets[(currentMove * 2)];
		newYpos	=	currentYpos + gMoveOffsets[(currentMove * 2) + 1];
		moveOK	=	true;
		
		if ((newXpos < 1) || (newXpos > 8))
		{
			moveOK	=	false;
		}
		else if ((newYpos < 1) || (newYpos > 8))
		{
			moveOK	=	false;
		}
		else if (gChessBoard[newXpos][newYpos] != 0)
		{
			moveOK	=	false;
		}
		
		
		if (moveOK)
		{
			keepLooking	=	false;
			newMove		=	currentMove;
		}
		currentMove++;
	}
	return(newMove);
}



//************************************************************************
void loop()
{
int		nextMove;
int		currentXpos;
int		currentYpos;


	gLoopCounter++;
	
	if ((gLoopCounter % 10000) == 0)
	{
		Serial.print("+");
	}
	if ((gLoopCounter % 500000) == 0)
	{
		Serial.println("+");
	}
	
	
	nextMove	=	MakeKnightMove(&(gKMoves[gMoveIndex]));
	if (nextMove >= 0)
	{
		currentXpos	=	gKMoves[gMoveIndex].boardXpos;
		currentYpos	=	gKMoves[gMoveIndex].boardYpos;

		gChessBoard[currentXpos][currentYpos]	=	gMoveIndex + 1;

		//*	we have a valid move
		gKMoves[gMoveIndex].nextMove	=	nextMove;
		gMoveIndex++;
		
		gKMoves[gMoveIndex].boardXpos	=	currentXpos + gMoveOffsets[(nextMove * 2)];
		gKMoves[gMoveIndex].boardYpos	=	currentYpos + gMoveOffsets[(nextMove * 2) + 1];
		gKMoves[gMoveIndex].nextMove	=	-1;


	}
	else
	{
	//	Serial.println("Backup!!!!");
		//*	set the board back to zero
		currentXpos	=	gKMoves[gMoveIndex].boardXpos;
		currentYpos	=	gKMoves[gMoveIndex].boardYpos;
		gChessBoard[currentXpos][currentYpos]	=	0;

		gMoveIndex--;
		if (gMoveIndex >= 0)
		{
			
		}
		else
		{
			Serial.println("GIVE UP!!!!");
		#ifdef _COMPILE_FOR_UNIX_
			exit(0);
		#endif
			while (true);
		}
		
	}

	if (gMoveIndex >= 63)
	{
	int		zeroCount;
	long	elapsedSeconds;
	long	elapsedMinutes;
	long	elapsedHours;
	
		zeroCount	=	CountZerosOnBoard();
		if (zeroCount == 1)
		{
			currentXpos	=	gKMoves[gMoveIndex].boardXpos;
			currentYpos	=	gKMoves[gMoveIndex].boardYpos;
			gChessBoard[currentXpos][currentYpos]	=	gMoveIndex + 1;

			PrintChessBoard();
			
			Serial.println("ALL DONE!!!!");
			Serial.print("Total itterations=");
			Serial.print(gLoopCounter);
	
			elapsedSeconds	=	millis() / 1000;
			elapsedMinutes	=	elapsedSeconds / 60;
			elapsedHours	=	elapsedMinutes / 60;
			
			Serial.println("----------------------------------");
			Serial.println("All done");
			Serial.print("Total itterations (boards) checked ");
			Serial.println(gLoopCounter);



			Serial.print("total seconds=");
			Serial.println(elapsedSeconds);

			Serial.print("hours=");
			Serial.println(elapsedHours);

			Serial.print("minutes=");
			Serial.println(elapsedMinutes % 60);

			Serial.print("seconds=");
			Serial.println(elapsedSeconds % 60);



		
		#ifdef _COMPILE_FOR_UNIX_
			exit(0);
		#endif
			while (true);
		}
	}

/*
	{
	long	elapsedSeconds;
	long	elapsedMinutes;
	long	elapsedHours;
	
		elapsedSeconds	=	millis() / 1000;
		elapsedMinutes	=	elapsedSeconds / 60;
		elapsedHours	=	elapsedMinutes / 60;
		
		Serial.println("----------------------------------");
		Serial.println("All done");
		Serial.print("Total itterations (boards) checked ");
		Serial.println(gLoopCounter);


		Serial.println("This is what the board ends up looking like");


		PrintChessBoard();
		Serial.println("----------------------------------");

		Serial.print("total seconds=");
		Serial.println(elapsedSeconds);

		Serial.print("hours=");
		Serial.println(elapsedHours);

		Serial.print("minutes=");
		Serial.println(elapsedMinutes % 60);

		Serial.print("seconds=");
		Serial.println(elapsedSeconds % 60);

	#ifdef _COMPILE_FOR_UNIX_
		exit(0);
	#endif
		while (1);
	}
*/
}



#ifdef _COMPILE_FOR_UNIX_
//************************************************************************
int	main()
{
	gStartTimeSeconds	=	time(&tloc);
	setup();
	
	while (true)
	{
		loop();
	}
}

#endif