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