Knight Tour

[merlinf]

Hey guys, I'm trying to do a recursion about the famous problem Knight Tour but it seems that my source code is wrong. I coded it using the algorithm found on Internet. Thanks for helping me.

#include"header1.h" // inside just regular library and prototype

using namespace std;

void display(int *Knight, int n)
{
	for (int i = 0; i < n; i++)
		cout << i+1 << "," << Knight[i]+11 << endl; // I try to make the result look like an int 
										//that the first number is a row and the second is colunm
}

bool available(int row, int col, int n) // Check if the move is in the chessboard
{
	if (row > n || col > n || row < 0 || col < 0)
		return false;
	return true;
}		

void KnightTour(int *Knight,int n,int k,bool* row,bool* col,bool &one,int x,int y,int xMove[],int yMove[])
{
	if (k >= n*n) // If complete
	{
		display(Knight,n*n);
		one = false; // I want only one result so I put a bool to prevent other result
	}	
	else
		for (int i = 0; i < 8; ++i) // I check all possible 8 move of a knight
			if (available(x+xMove[i],y+yMove[i],n) && (row[x+xMove[i]] && col[y+yMove[i]]) && one)
			{
				Knight[k] = (x+xMove[i])*10 + y+yMove[i]; //// I try to make the result look like an int 
										//that the first number is a row and the second is colunm
				row[x+xMove[i]] = false; // I mark this row and col is used,
				col[y+yMove[i]] = false; // If both are marked, The knight cannot come to that cell
				KnightTour(Knight,n,k+1,row,col,one,x,y,xMove,yMove); // Recursive
				row[x+xMove[i]] = true; // Unmarking
				col[y+yMove[i]] = true;
			}
			
}

void solve(int N, int x, int y)
{
	int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
			
	int *n = new int;
	*n = N;
	bool *row = new bool[*n];
	bool *col = new bool[*n];
	for (int i = 0; i < *n; ++i)
	{
		row[i] = true;
		col[i] = true;
	}					
	int* Knight = new int[(*n)*(*n)];
	bool one = true;
	KnightTour(Knight,N,0,row,col,one,x-1,y-1,xMove,yMove);	
}	

[lastchance]

To be honest, it's well-nigh impossible to work out what you are doing, not helped by skipping between 1-d and 2-d (implied) arrays. However, ...

but it seems that my source code is wrong.

Think about it - that statement helps no-one. What exactly is going wrong with your source code? Does it not compile, explode, or simply give the wrong answer.



#include"header1.h"
Well, I don't have a clue what is in that header. Maybe somebody else in the forum will. Or maybe it's your own little file that is preventing anyone else here from even trying your code.



void display(int *Knight, int n)
Actually, you called that routine with n*n, not n, implying some flattened 2-d array perhaps.



cout << i+1 << "," << Knight[i]+11 << endl;
I'm trying ... and failing ... to see what that has to do with a chessboard.

bool available(int row, int col, int n)
{
	if (row > n || col > n || row < 0 || col < 0)

(a) Those boundaries aren't quite correct.
(b) In the usual Knight's tour you should also be checking whether a square has been taken before.



one = false;
What is that supposed to signify?



Knight[k] = (x+xMove[i])*10 + y+yMove[i];
Why the 10? A standard chessboard is 8x8 (and yours is, at one point, n*n)

				row[x+xMove[i]] = false;
				col[y+yMove[i]] = false;
				KnightTour(Knight,n,k+1,row,col,one,x,y,xMove,yMove);
				row[x+xMove[i]] = true;
				col[y+yMove[i]] = true;

No idea. Explain your logic. You need individual squares, not whole rows or columns.

	int *n = new int;
	*n = N;

That could win a prize for the two most pointless lines of code ...


int* Knight = new int[(*n)*(*n)];
... see above.

[Ganado]

well-nigh impossible

Don't you mean, neigh-impossible? :D

[lastchance]

Ah, very true @Ganado.

Actually, with that username, merlin probably ought to know more about knights than the rest of us ...

[George P]

merlinf wrote:

I coded it using the algorithm found on Internet.

And which algorithm might that be? Where was the algorithm? (hint, a link)

In a very cursory 'net search I found at least 3. (https://duckduckgo.com/?q=knight%27s+tour+solution+8x8+c%2B%2B&t=ffsb&ia=web)

Brute-force algorithm
Common backtracking algorithm
Warnsdorff's rule algorithm

Along with some source code showing one way to implement each.*
https://github.com/wisn/knights-tour

As to the sample algorithms being suitable for solving the problem, I can't say. I didn't try any of them.

There is code available to "solve" the tour in programming languages other than C++ as well:
https://rosettacode.org/wiki/Knight%27s_tour

The C++ solution from that link uses Warnsdorff's rule and (iterative) backtracking if that fails.

So maybe 4 ways to solve.

*FYI, using C formatted output (printf) in C++ source code is no longer needed, C++20 added std::format to the C++ toolbox. The C++ code snippets from github using printf are kinda outdated now.
https://en.cppreference.com/w/cpp/utility/format/format

A C++ snippet using std::format for a nice formatted table:

#include <iostream>
#include <format>

// or

// import <iostream>;
// import <format>;

int main()
{
   unsigned int limit { };
   std::cout << "This program calculates n! and the sum of the integers "
      << "up to n for values 1 to limit.\n";
   std::cout << "What upper limit for n would you like? ";
   std::cin >> limit;

   // The format string for all rows of the table
   const auto table_format { "{:>8} {:>8} {:>20}\n" };

   // Output column headings
   std::cout << std::format(table_format, "integer", "sum", "factorial");

   for (unsigned long long n { 1 }, sum {}, factorial { 1 }; n <= limit; ++n)
   {
      sum += n; // Accumulate sum to current n
      factorial *= n; // Calculate n! for current n

      std::cout << std::format(table_format, n, sum, factorial);
   }
}

This program calculates n! and the sum of the integers up to n for values 1 to limit.
What upper limit for n would you like? 18
 integer      sum            factorial
       1        1                    1
       2        3                    2
       3        6                    6
       4       10                   24
       5       15                  120
       6       21                  720
       7       28                 5040
       8       36                40320
       9       45               362880
      10       55              3628800
      11       66             39916800
      12       78            479001600
      13       91           6227020800
      14      105          87178291200
      15      120        1307674368000
      16      136       20922789888000
      17      153      355687428096000
      18      171     6402373705728000

[lastchance]

#include <iostream>
#include <iomanip>
#include <utility>
using namespace std;

const int N = 8;
int A[N][N]{};
pair<int,int> jump[] = { {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

//==========================================================

void display()
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) cout << setw( 3 ) << A[i][j];
      cout << '\n';
   }
}

//==========================================================

bool solve( int mv = 1, int i0 = 0, int j0 = 0)            // main backtracking routine
{
   if ( mv > N * N ) return true;                          // completion
   if ( A[i0][j0]  ) return false;                         // already taken

   A[i0][j0] = mv;
   for ( auto pr : jump )
   {
      int i = i0 + pr.first ;
      int j = j0 + pr.second;
      if ( i >= 0 && i < N && j >= 0 && j < N && solve( mv + 1, i, j ) ) return true;  // *** MAIN RECURSIVE CALL ***
   }
   A[i0][j0] = 0;
   return false;
}

//==========================================================

int main()
{
   if( solve() ) display();
}

  1 38 59 36 43 48 57 52
 60 35  2 49 58 51 44 47
 39 32 37 42  3 46 53 56
 34 61 40 27 50 55  4 45
 31 10 33 62 41 26 23 54
 18 63 28 11 24 21 14  5
  9 30 19 16  7 12 25 22
 64 17  8 29 20 15  6 13

[merlinf]

I'm so sorry not adding any description
I edit the post with description what I intend to do now
This is the link I saw the algorithms https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/

The result of my code is nothing on the console though

[jonnin]

your code is really hard to follow because instead of a 2-d board, you doubled up 1-d boards.

it is a lot easier to visualize and work it from 2-d.
consider
bool beenthere[8][8]{}; //havent been anywhere yet.
pick a start square, make a move, mark it true, until you get stuck. when you get stuck, undo the last move and try a different one (naturally handled by the recursion, just unmark the board). eventually it finishes or not. I forget if its doable from every start square or not. This is the brute force way, though. If you want to tweak that, you can, but its really not too slow on an 8x8 board and a modern computer. I would just because, but if you just copy off someone else, meh. Its the figuring it out yourself that is worth doing.

[George P]

If you look at the code you should notice neither the C or C++ code uses pointers to create arrays. Both use clearly defined compile time arrays being passed into the functions. Clearly defined 2D arrays, not pointers as 1D arrays that you use.

I gave you earlier several links you should look at. The C++ coding at Rosetta for example uses classes and other C++ constructs like std::array and std::tuple to do the magic.

The C code at Rosetta use double pointer notation to pass 2D arrays into functions. 2D arrays, not 1D.

The 3 C++ algorithms at the wisn github site don't use classes, but they use another C++ construct that is a function wrapper, std::function, to wrap lambdas.
https://en.cppreference.com/w/cpp/utility/functional/function
https://en.cppreference.com/w/cpp/language/lambda

One huge problem with the geeksforgeeks site is they use a non-standard C++ header (#include <bits/stdc++.h> ) that should never be used as a direct include, it is for internal compiler usage. Not every C++ compiler has the header. Visual Studio doesn't.

The result of my code is nothing on the console though

I'm not surprised. Try this:

#include <iostream>
#include <iomanip>

constexpr unsigned N { 8 };

bool solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[8], int yMove[8]);

/* A utility function to check if i,j are
valid indexes for N*N chessboard */
bool isSafe(int x, int y, int sol[N][N])
{
   return (x >= 0 && x < N&& y >= 0 && y < N&& sol[x][y] == -1);
}

/* A utility function to print
solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
   for (int x { }; x < N; x++)
   {
      for (int y { }; y < N; y++)
      {
         std::cout << ' ' << std::setw(2) << sol[x][y] << ' ';
      }
      std::cout << std::endl;
   }
}

/* This function solves the Knight Tour problem using
Backtracking. This function mainly uses solveKTUtil()
to solve the problem. It returns false if no complete
tour is possible, otherwise return true and prints the
tour.
Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
int solveKT()
{
   int sol[N][N];

   /* Initialization of solution matrix */
   for (int x { }; x < N; x++)
   {
      for (int y { }; y < N; y++)
      {
         sol[x][y] = -1;
      }
   }

   /* xMove[] and yMove[] define next move of Knight.
   xMove[] is for next value of x coordinate
   yMove[] is for next value of y coordinate */
   int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
   int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

   // Since the Knight is initially at the first block
   sol[0][0] = 0;

   /* Start from 0,0 and explore all tours using solveKTUtil() */
   if (!solveKTUtil(0, 0, 1, sol, xMove, yMove))
   {
      std::cout << "Solution does not exist\n";
      return 0;
   }
   else
   {
      printSolution(sol);
   }

   return 1;
}

/* A recursive utility function to solve Knight Tour problem */
bool solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[8], int yMove[8])
{
   int k, next_x, next_y;

   if (movei == N * N)
   {
      return 1;
   }

   /* Try all next moves from the current coordinate x, y */
   for (k = 0; k < 8; k++)
   {
      next_x = x + xMove[k];
      next_y = y + yMove[k];

      if (isSafe(next_x, next_y, sol))
      {
         sol[next_x][next_y] = movei;
         if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1)
         {
            return true;
         }
         else
         { // backtracking
            sol[next_x][next_y] = -1;
         }
      }
   }
   return false;
}

// Driver Code
int main()
{
   // Function Call
   solveKT();
}

  0  59  38  33  30  17   8  63
 37  34  31  60   9  62  29  16
 58   1  36  39  32  27  18   7
 35  48  41  26  61  10  15  28
 42  57   2  49  40  23   6  19
 47  50  45  54  25  20  11  14
 56  43  52   3  22  13  24   5
 51  46  55  44  53   4  21  12

[seeplus]

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>

constexpr unsigned N {8};
using Move = std::vector<int>;
using Array = std::vector<Move>;
using Coord = std::pair<unsigned, unsigned>;
enum movDir {XMOVE, YMOVE};

bool solveKTUtil(const Coord& co, unsigned movei, Array& sol, const Move ktMove[YMOVE + 1]);

bool isSafe(const Coord& co, const Array& sol) {
    return co.first < N && co.second < N && sol[co.first][co.second] == -1;
}

void printSolution(const Array& sol) {
    for (unsigned x {}; x < N; ++x) {
        for (unsigned y {}; y < N; ++y)
            std::cout << ' ' << std::setw(2) << sol[x][y] << ' ';

        std::cout << '\n';
    }
}

bool solveKT() {
    const Move ktMove[YMOVE + 1] {{2, 1, -1, -2, -2, -1, 1, 2}, {1, 2, 2, 1, -1, -2, -2, -1}};

    Array sol(N, Move(N, -1));

    sol[0][0] = 0;

    if (!solveKTUtil({0, 0}, 1, sol, ktMove))
        return (std::cout << "Solution does not exist\n"), false;

    printSolution(sol);

    return true;
}

bool solveKTUtil(const Coord& co, unsigned movei, Array& sol, const Move ktMove[YMOVE + 1]) {
    if (movei == N * N)
        return true;

    for (unsigned k {}; k < ktMove[XMOVE].size(); ++k) {
        const auto next_x {co.first + ktMove[XMOVE][k]};
        const auto next_y {co.second + ktMove[YMOVE][k]};

        if (isSafe({next_x, next_y}, sol)) {
            sol[next_x][next_y] = movei;

            if (solveKTUtil({next_x, next_y}, movei + 1, sol, ktMove))
                return true;

            sol[next_x][next_y] = -1;
        }
    }

    return false;
}

int main() {
    solveKT();
}