vendredi 21 mai 2021

Trying to solve Knights Tour on nested vector

I have written a code for knights tour problem which work for 2D array but not for vector<vector<pair<int,int>> ** WORKING CODE**

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

bool isPossible(int sol[N][N], int x, int y)
{
    if ( sol[x][y]==-1 && x >= 0 && x < N && y >= 0 && y < N)
    {
        return true;
    }
    return false;
}
bool KNT(int sol[N][N], int moveNUM, int x, int y, int movex[8], int movey[8])
{
    int i,next_x,next_y;
    if (moveNUM == N * N)
    {
        return true;
    }
    for ( i = 0; i < 8; i++)
    {
         next_x = x + movex[i];
         next_y = y + movey[i];
        if (isPossible(sol, next_x, next_y))
        {
            sol[next_x][next_y]=moveNUM;
            
            if (KNT(sol, moveNUM + 1, next_x, next_y, movex, movey))
            {
                return true;
            }
        
           sol[next_x][next_y] = -1; //Backtracking
            
        }
    }
    return false; 
}
int main()
{
   
    
    int sol[N][N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            sol[i][j]=-1;
        }
        
    }

    int movex[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int movey[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    KNT(sol,1,0,0,movex, movey);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << sol[i][j] << " ";
        }
        cout << endl;
    }
}

NON WORKING CODE

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

bool isPossible(vector<vector<pair<int, int>>> &Brd, int x, int y)
{
    if ((Brd[x][y].first == -1) && x >= 0 && x < N && y >= 0 && y < N)
    {
        return true;
    }
    return false;
}
bool KNT(vector<vector<pair<int, int>>> &Brd, int moveNUM, int x, int y, int movex[8], int movey[8])
{
    int i,next_x,next_y;
    if (moveNUM == N * N)
    {
        return true;
    }
    for ( i = 0; i < 8; i++)
    {
         next_x = x + movex[i];
         next_y = y + movey[i];
        if (isPossible(Brd, next_x, next_y))
        {
             Brd[next_x][next_y].first = 1;
             Brd[next_x][next_y].second = moveNUM;
           
            if (KNT(Brd, moveNUM + 1, next_x, next_y, movex, movey))
            {
                return true;
            }
            Brd[next_x][next_y].first = -1;
            Brd[next_x][next_y].second = 0;
             //Backtracking
            
        }
    }
    return false; //Check for error
}
int main()
{
    vector<vector<pair<int, int>>> Brd;
    for (int i = 0; i < N; i++)
    {
        vector<pair<int, int>> temp;
        for (int j = 0; j < N; j++)
        {
            temp.push_back(make_pair(-1, 0));
        }
        Brd.push_back(temp);
    }
    
     int movex[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int movey[8] = {1, 2, 2, 1, -1, -2, -2, -1}; 
   
    KNT(Brd,1,0,0,movex,movey);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << Brd[i][j].second << " ";
        }
        cout << endl;
    }
}

In NON-WORKing code when I run the code it doesn't give any output but rather ends abruptly. P.S. Any help will mean a lot I have wasted Around 2 days finding the solution for this.

Aucun commentaire:

Enregistrer un commentaire