Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const vector<int> dx = {-2, -1, 1, 2, 2, 1, -1, -2};
- const vector<int> dy = {1, 2, 2, 1, -1, -2, -2, -1};
- void knightTour(int row, int col, int cellVisited, vector<vector<int> > &chess, vector<string> &allValidKnightPaths){
- //Invalid Path
- if(row < 0 || row >= chess.size() || col < 0 || col >= chess.size() || chess[row][col]){
- return;
- }
- //Mark the current cell visited by the Knight
- chess[row][col] = cellVisited;
- //base case
- if(cellVisited == pow(chess.size(), 2)){
- string validPath = "";
- for(int i = 0; i < chess.size(); i++){
- for(int j = 0; j < chess[0].size(); j++){
- validPath += to_string(chess[i][j]) + " ";
- }
- validPath += '\n';
- }
- allValidKnightPaths.push_back(validPath);
- chess[row][col] = 0;
- return;
- }
- //Levels/States = each cell
- //Options/Transitions = all the 8 moves
- //explore all 8 options for each cell
- for(int k = 0; k < dx.size(); k++){
- knightTour(row + dx[k], col + dy[k], cellVisited + 1, chess, allValidKnightPaths);
- }
- // Backtrack from the current cell/mark unvisited
- chess[row][col] = 0;
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<vector<int> > chess(n, vector<int>(n, 0));
- vector<string> allValidKnightPaths;
- // Start Knight Tour from each of the cell in chessboard, to generate all possible configurations
- for(int i = 0; i < n; i++){
- for(int j = 0; j < n; j++){
- // here 1 is passed, as the current cell is marked as visited
- knightTour(i, j, 1, chess, allValidKnightPaths);
- }
- }
- //print all valid knight paths
- cout << "Total Paths: " << allValidKnightPaths.size() << '\n';
- for(string path : allValidKnightPaths){
- cout << path << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
