0

Hello Guys I am trying to learn Backtracking and so I tried solving the famous Knight Tour problem. I have written the code but I dont know where its going wrong. Output Expected: The 2d array with numbers printed from 0 to 63. Output Im getting : Soln doesnt exist

Pls Help.

#include<bits/stdc++.h>
using namespace std;

#define N 8

bool knightTour(int arr[N][N],int movei, int dx[],int dy[],int i,int j)
{
    if(movei == N*N)
        return true;

    int next_x,next_y;
    for(int k=0;k< 8;k++)
    {
        next_x = i + dx[k];
        next_y = j + dy[k];

        if(next_x >= 0 && next_x < N && next_y>=0 && next_y < N && arr[next_x][next_y]==-1)
        {
            arr[next_x][next_y] = movei;
            if(knightTour(arr,movei+1,dx,dy,next_x,next_y))
                return true;
            else
                arr[next_x][next_y] = -1;

        }
    }
   return false;
}

int main()
{
    int arr[N][N] ={-1};
   int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
    arr[0][0] = 0; // Since the knight starts from 0,0

    if(knightTour(arr,1,dx,dy,0,0) == true)
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    else
    {
        cout<<"No soln Exists";
    }

}
Haider Keshwani
  • 11
  • 3
  • 2
    Print the contents of `arr` before you do anything else; it's not what you think. Then read about how arrays are initialised in your favourite C++ book. – molbdnilo Jul 22 '20 at 07:01
  • Since you're setting are[0][0] = 0 in main, movei can go to atmax N*N-1. If condition should be checking for that. – srt1104 Jul 22 '20 at 07:03
  • @molbdnilo Ha, I spent ages looking at the backtracking code (it seems correct to me). A debugger would have solved this very quickly too. To the OP - do you know how to use a debugger? Seems you would benefit from learning how. – john Jul 22 '20 at 07:05
  • @lucieon But `movei` is initially set to `1` so I think that is OK. – john Jul 22 '20 at 07:06
  • knightTour(arr, 64, dx, dy, next_x, next_y) never gets called. Hence it's returning false. – srt1104 Jul 22 '20 at 07:09
  • @lucieon No you're are not right about that for the reason I explained. I fixed the problem that mobdnilo found and then the code works correctly. – john Jul 22 '20 at 07:12
  • I tried N*N-1 didnt work, @lucieon – Haider Keshwani Jul 22 '20 at 07:14
  • `N*N` is correct given the rest of the code. – john Jul 22 '20 at 07:14
  • I dont know anything about a debugger. I only use cout statements for debugging bugs in my code. Would be helpful if someone would tell me how its used. @john – Haider Keshwani Jul 22 '20 at 07:15
  • @HaiderKeshwani What compiler do you use? Each compiler has it's own debugger. – john Jul 22 '20 at 07:16
  • 1
    For general info on debuggers see https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems – churill Jul 22 '20 at 07:16
  • ah my bad, I was thinking wrong. – srt1104 Jul 22 '20 at 07:17
  • @john It worked. So basically had to use memset for initialising the array to initial value. – Haider Keshwani Jul 22 '20 at 07:20

0 Answers0