//************************************************************************
//* 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
|