hi
i've been trying to program a solution for the knight's tour problem. i wanted to use recursive backtracking in order to accomplish this.
this is what i have so far. i keep getting stack overflows, but debugging doesn't really help or is quite complicated in some cases.
i'd appreciate any help.
public partial class KnightsTourProblemForm : Form
{
private const int BOARDSIDE = 8;
private int[,] board = new int[BOARDSIDE, BOARDSIDE];
public KnightsTourProblemForm()
{
InitializeComponent();
}
private bool CheckPosition(int row, int column)
{
return (row >= 0 && row < BOARDSIDE && column >= 0 && column < BOARDSIDE);
}
private void StepBack(ref int row, ref int column)
{
board[row, column] = 0;
switch (board[row,column])
{
case 1:
row--;
column -= 2;
break;
case 2:
row -= 2;
column--;
break;
case 3:
row -= 2;
column++;
break;
case 4:
row--;
column += 2;
break;
case 5:
row++;
column += 2;
break;
case 6:
row += 2;
column++;
break;
case 7:
row += 2;
column--;
break;
case 8:
row++;
column -= 2;
break;
}
}
private void DisplayBoard(int[,] board)
{
boardLabel.Text = "";
for (int i = 0; i < BOARDSIDE; i++)
{
for (int j = 0; j < BOARDSIDE; j++)
{
if (board[i,j] > 0)
{
boardLabel.Text += "$ ";
}
else
{
boardLabel.Text += "0 ";
}
}
boardLabel.Text += "\r\n";
}
}
private bool SolutionFound(int[,] board)
{
for (int i = 0; i < BOARDSIDE; i++)
{
for (int j = 0; j < BOARDSIDE; j++)
{
if (board[i,j] == 0)
{
return false;
}
}
}
return true;
}
private void Search(int row, int column)
{
if (! SolutionFound(board))
{
if (CheckPosition(row, column))
{
if (board[row, column] == 0 && CheckPosition(row + 1, column + 2))
{
row++;
column += 2;
board[row, column] = 1;
}
else if (board[row , column] == 1 && CheckPosition(row + 2, column + 1))
{
row += 2;
column++;
board[row, column] = 2;
}
else if (board[row, column] == 2 && CheckPosition(row + 2, column - 1))
{
row += 2;
column--;
board[row, column] = 3;
}
else if (board[row, column] == 3 && CheckPosition(row + 1, column - 2))
{
row++;
column -= 2;
board[row, column] = 4;
}
else if (board[row, column] == 4 && CheckPosition(row - 1, column - 2))
{
row--;
column -= 2;
board[row, column] = 5;
}
else if (board[row, column] == 5 && CheckPosition(row - 2, column - 1))
{
row -= 2;
column--;
board[row, column] = 6;
}
else if (board[row, column] == 6 && CheckPosition(row - 2, column + 1))
{
row -= 2;
column++;
board[row, column] = 7;
}
else if (board[row, column] == 7 && CheckPosition(row - 1, column + 2))
{
row--;
column += 2;
board[row, column] = 8;
}
else
{
StepBack(ref row, ref column);
}
Search(row, column);
}
DisplayBoard(board);
}
}
private void generateButton_Click(object sender, EventArgs e)
{
// empty chessboard
for (int i = 0; i < BOARDSIDE; i++)
{
for (int j = 0; j < BOARDSIDE; j++)
{
board[i, j] = 0;
}
}
Search(0, 0);
}
}
thanks in advance
pygmalion
