knight_tour.cpp File Reference

Knight's tour algorithm More...

#include <array>
#include <iostream>

Include dependency graph for knight_tour.cpp:

Go to the source code of this file.

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

Definition in file knight_tour.cpp.

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 ....

Definition at line 40 of file knight_tour.cpp.

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

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 88 of file knight_tour.cpp.

           {
    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()

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 )

Knight's tour algorithm

Template Parameters

V	number of vertices in array

Parameters

x	current index in rows
y	current index in columns
mov	movement to be done
sol	matrix where numbers are saved
xmov	next move of knight (x coordinate)
ymov	next move of knight (y coordinate)

Returns

true if solution exists

false if solution does not exist

Definition at line 57 of file knight_tour.cpp.

                                                                 {
    int k = 0, xnext = 0, ynext = 0;
 
    if (mov == V * V) {
        return true;
    }
 
    for (k = 0; k < V; k++) {
        xnext = x + xmov[k];
        ynext = y + ymov[k];
 
        if (issafe<V>(xnext, ynext, sol)) {
            sol[xnext][ynext] = mov;
 
            if (solve<V>(xnext, ynext, mov + 1, sol, xmov, ymov) == true) {
                return true;
            } else {
                sol[xnext][ynext] = -1;
            }
        }
    }
    return false;
}