-
Notifications
You must be signed in to change notification settings - Fork 20
/
knight_problem.cpp
73 lines (49 loc) · 1.6 KB
/
knight_problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
//knight problem
//username-Mohit-2304
//Backtracking algorithm for Knight’s tour problem
// problem can also be solved by naive algorithm but backtracking gives a better solution
//Please Note : The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once
bool can_place(int row,int col,int board[8][8])
{
return row<8&&col<8&&row>=0&&col>=0&&board[row][col]==0;
}
bool solve(int board[8][8],int move_no,int row,int col)
{
if(move_no==64)
return true;
int nextrow[]={-1,-2,-2,-1, 1, 2, 2, 1};
int nextcol[]={ 2, 1,-1,-2,-2,-1, 1, 2};
for(int i=0;i<8;i++)
{
int newrow=row+nextrow[i];
int newcol=col+nextcol[i];
bool check=can_place(newrow,newcol,board);
if(check==true)
{
board[newrow][newcol]=move_no+1;
bool correct=solve(board,move_no+1,newrow,newcol);
if(correct==true)
return true;
board[newrow][newcol]=0;
}
}
return false;
}
int main()
{
int board[8][8]={0},row=0,col=0; // board is the chessboard of size 8*8
board[0][0]=1;
bool print=solve(board,1,0,0);
if(print==true)
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
cout<<setw(3)<<board[i][j];
cout<<"\n";
}
}
}
//The code prints one possible solution in 2D matrix form , the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.