Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
knight_tour.cpp File Reference

Knight's tour algorithm More...

#include <iostream>
#include <array>
Include dependency graph for knight_tour.cpp:

Namespaces

 backtracking
 Backtracking algorithms.
 

Functions

template<size_t V>
bool backtracking::issafe (int x, int y, const std::array< std::array< int, V >, V > &sol)
 
template<size_t V>
bool backtracking::solve (int x, int y, int mov, std::array< std::array< int, V >, V > &sol, const std::array< int, V > &xmov, std::array< int, V > &ymov)
 
int main ()
 

Detailed Description

Knight's tour algorithm

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path, the tour is closed; otherwise, it is open.

Author
Nikhil Arora
David Leal

Function Documentation

◆ main()

int main ( void  )

Main function

80  {
81  const int n = 8;
82  std::array <std::array <int, n>, n> sol = { 0 };
83 
84  int i, j;
85  for (i = 0; i < n; i++) {
86  for (j = 0; j < n; j++) { sol[i][j] = -1; }
87  }
88 
89  std::array <int, n> xmov = { 2, 1, -1, -2, -2, -1, 1, 2 };
90  std::array <int, n> ymov = { 1, 2, 2, 1, -1, -2, -2, -1 };
91 
92  sol[0][0] = 0;
93 
94  bool flag = backtracking::solve<n>(0, 0, 1, sol, xmov, ymov);
95  if (flag == false) {
96  std::cout << "Error: Solution does not exist\n";
97  }
98  else {
99  for (i = 0; i < n; i++) {
100  for (j = 0; j < n; j++) { std::cout << sol[i][j] << " "; }
101  std::cout << "\n";
102  }
103  }
104  return 0;
105 }
std::cout
std::array
STL class.