#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);	
}	

#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);
   }
}

#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();
}

#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();
}

#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();
}