0

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 ?

Community
  • 1
  • 1
Anurag
  • 307
  • 5
  • 9
  • 1
    In the worst-case, a back-tracking algorithm for the Knight's Tour could require 8^63 (**~7.8463771692333509547947367790096e+56**, i.e. a really large number) iterations. Are you sure you have a bug? Is it possible your program is just taking a lot longer to run than you thought it might? (Actually, you do have a bug, but I don't think you have a bug in the fundamental back-tracking part of it...that bug is that even after finding a solution, the algorithm will continue to search the problem space.) – Peter Duniho Jun 24 '17 at 05:26
  • Yes, but I have a breakpoint in the Base case on my visual studio IDE. So if the solution is found, IDE should flag it. I agree to your point that code will keep searching for more solution. Also, I ran the code for 30mins and it did not fall into Base case. Should I run it for more time? – Anurag Jun 24 '17 at 05:30
  • I don't think you're really getting the magnitude of the problem here. The largest value for a 64-bit signed integer is 9,223,372,036,854,775,807, or 9.223372036854775807e+18. The number of possible iterations in your program is 10^38 larger than that. Assuming your program could perform 9 quintillion iterations in a second (that's, well...beyond optimistic), it could still take 3,170,979,198,376,458,650,431,253,170,979 years to find a solution. Have you really been running the program that long yet? Hint: 30 minutes is quite a bit shorter than that. – Peter Duniho Jun 24 '17 at 05:36
  • (By the way, I've oversimplified, because as you progress, you prune the search tree because you can't revisit squares. But I don't think the search tree gets pruned quickly enough to matter. It's still going to take a very long time. Other examples I've seen apply the algorithm to a smaller board, such as 4x4 or 5x5.) – Peter Duniho Jun 24 '17 at 05:38
  • @PeterDuniho Thanks for pointing out the duplicate question and providing the insights to the magnitude .I tried running the program on 7*7 and it did yield the correct result. – Anurag Jun 24 '17 at 06:01

0 Answers0