I have been trying to solve Knight's tour problem using backtracking.Here is my code :-
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication12
{
class Program
{
static void Main(string[] args)
{
int[,] arr = new int[8, 8];
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
arr[i, j] = -1;
}
// Console.WriteLine();
}
arr[0, 0] = 0;
knightTour(arr, 0, 0, 0, 63);
printArray(arr);
}
private static void knightTour(int[,] arr, int x, int y, int move, int empty)
{
if (empty <= 0)
{
printArray(arr);
Console.WriteLine("--------------------------------------------");
}
else
{
//int movelocal = move;
int temp = 0;
if (isavailable(arr, x + 2, y + 1))
{
temp = arr[x + 2, y + 1];
arr[x + 2, y + 1] = move + 1;
knightTour(arr, x + 2, y + 1, move + 1, empty - 1);
arr[x + 2, y + 1] = temp;
}
if (isavailable(arr, x - 2, y + 1))
{
temp = arr[x - 2, y + 1];
arr[x - 2, y + 1] = move + 1;
knightTour(arr, x - 2, y + 1, move + 1, empty - 1);
arr[x - 2, y + 1] = temp; //backtrack
}
if (isavailable(arr, x - 1, y + 2))
{
temp = arr[x - 1, y + 2];
arr[x - 1, y + 2] = move + 1;
knightTour(arr, x - 1, y + 2, move + 1, empty - 1);
arr[x - 1, y + 2] = temp;
}
if (isavailable(arr, x + 1, y + 2))
{
temp = arr[x + 1, y + 2];
arr[x + 1, y + 2] = move + 1;
knightTour(arr, x + 1, y + 2, move + 1, empty - 1);
arr[x + 1, y + 2] = temp;
}
if (isavailable(arr, x + 2, y - 1))
{
temp = arr[x + 2, y - 1];
arr[x + 2, y - 1] = move + 1;
knightTour(arr, x + 2, y - 1, move + 1, empty - 1);
arr[x + 2, y - 1] = temp;
}
if (isavailable(arr, x - 2, y - 1))
{
temp = arr[x - 2, y - 1];
arr[x - 2, y - 1] = move + 1;
knightTour(arr, x - 2, y - 1, move + 1, empty - 1);
arr[x - 2, y - 1] = temp;
}
if (isavailable(arr, x + 1, y - 2))
{
temp = arr[x + 1, y - 2];
arr[x + 1, y - 2] = move + 1;
knightTour(arr, x + 1, y - 2, move + 1, empty - 1);
arr[x + 1, y - 2] = temp;
}
if (isavailable(arr, x - 1, y - 2))
{
temp = arr[x - 1, y - 2];
arr[x - 1, y - 2] = move + 1;
knightTour(arr, x - 1, y - 2, move + 1, empty - 1);
arr[x - 1, y - 2] = temp;
}
}
}
private static bool isavailable(int[,] arr, int x, int y)
{
if (x < 8 && x >= 0 && y < 8 && y >= 0 && arr[x, y] == -1)
{
return true;
}
else
{
return false;
}
}
private static void printArray(int[,] arr)
{
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
{
Console.Write(arr[i, j]);
Console.Write(" ");
}
Console.WriteLine();
}
}
}
}`
Its a simple backtracking approach ,where out of 8 moves available I traverse one of them and see if it leads to a solution . If it doesn't , then I go back to my previous state and try the remaining moves. The program keeps running in recursion and never falls into base case .Can someone help me find the bug ?