#include <array>
#include <iostream>

Include dependency graph for knight_tour.cpp:

Namespaces
namespace	backtracking
	for vector container

namespace	knight_tour
	Functions for the Knight's tour algorithm.

Functions
template<size_t V>
bool	backtracking::knight_tour::issafe (int x, int y, const std::array< std::array< int, V >, V > &sol)

template<size_t V>
bool	backtracking::knight_tour::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 ()
	Main function.

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

◆ issafe()

template<size_t V>

bool backtracking::knight_tour::issafe	(	int	x,
		int	y,
		const std::array< std::array< int, V >, V > &	sol )

A utility function to check if i,j are valid indexes for N*N chessboard

Template Parameters

V	number of vertices in array

Parameters

x	current index in rows
y	current index in columns
sol	matrix where numbers are saved

Returns: true if ....; false if ....

                                                                    {
    return (x < V && x >= 0 && y < V && y >= 0 && sol[x][y] == -1);
}

Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns: 0 on exit

           {
    const int n = 8;
    std::array<std::array<int, n>, n> sol = {0};
 
    int i = 0, j = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            sol[i][j] = -1;
        }
    }
 
    std::array<int, n> xmov = {2, 1, -1, -2, -2, -1, 1, 2};
    std::array<int, n> ymov = {1, 2, 2, 1, -1, -2, -2, -1};
 
    sol[0][0] = 0;
 
    bool flag = backtracking::knight_tour::solve<n>(0, 0, 1, sol, xmov, ymov);
    if (flag == false) {
        std::cout << "Error: Solution does not exist\n";
    } else {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                std::cout << sol[i][j] << "  ";
            }
            std::cout << "\n";
        }
    }
    return 0;
}

◆ solve()