骑士巡游问题

#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
 //check place is in range and not assigned yet
bool isValid(int x, int y, int sol[N][N]) {    
   return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void displaySolution() {
   cout << "The possible solution: " << endl;    
   for (int x = 0; x < N; x++) {
      for (int y = 0; y < N; y++)
         cout << setw(3) << sol[x][y] << " ";
      cout << endl;
   }
}
int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
   int xNext, yNext;
   //when the total board is covered
   if (move == N*N)     
      return true;
   for (int k = 0; k < 8; k++) {
      xNext = x + xMove[k];
      yNext = y + yMove[k];
      //check room is preoccupied or not
      if (isValid(xNext, yNext, sol)) {     
         sol[xNext][yNext] = move;
         if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
            return true;
         else
            // backtracking
            sol[xNext][yNext] = -1;
      }
   }
   return false;
}
bool findKnightTourSol() {
   //initially set all values to -1 of solution matrix    
   for (int x = 0; x < N; x++)     
      for (int y = 0; y < N; y++)
         sol[x][y] = -1;
   //all possible moves for knight
   int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
   int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
   //starting from room (0, 0)
   sol[0][0]  = 0;     
   if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
      cout << "Solution does not exist";
      return false;
   } else
      displaySolution();
   return true;
}
int main() {
   findKnightTourSol();
}

import java.util.Arrays;
public class Main {
   static final int N = 8;
   static int[][] sol = new int[N][N];
   //check place is in range and not assigned yet
   static boolean isValid(int x, int y) {    
      return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
   }
   static void displaySolution() {
      System.out.println("The possible solution: ");
      for (int x = 0; x < N; x++) {
         for (int y = 0; y < N; y++)
            System.out.printf("%3d ", sol[x][y]);
         System.out.println();
      }
   }
   static boolean knightTour(int x, int y, int move, int[] xMove, int[] yMove) {
      int xNext, yNext;
      //when the total board is covered
      if (move == N*N)     
         return true;
      for (int k = 0; k < 8; k++) {
         xNext = x + xMove[k];
         yNext = y + yMove[k];
         //check room is preoccupied or not
         if (isValid(xNext, yNext)) {     
            sol[xNext][yNext] = move;
               if (knightTour(xNext, yNext, move+1, xMove, yMove))
                  return true;
               else
                  // backtracking
                  sol[xNext][yNext] = -1;
         }
      }
      return false;
   }
   static boolean findKnightTourSol() {
      //initially set all values to -1 of solution matrix    
      for (int[] row : sol)
         Arrays.fill(row, -1);
         //all possible moves for knight
         int[] xMove = {2, 1, -1, -2, -2, -1, 1, 2};
         int[] yMove = {1, 2, 2, 1, -1, -2, -2, -1};
         //starting from room (0, 0)
         sol[0][0] = 0;     
         if (!knightTour(0, 0, 1, xMove, yMove)) {
            System.out.println("Solution does not exist");
            return false;
         } else
            displaySolution();
      return true;
   }
   public static void main(String[] args) {
      findKnightTourSol();
   }
}

N = 8

# The solution matrix
sol = [[-1 for _ in range(N)] for _ in range(N)]

# Check if place is in range and not assigned yet
def isValid(x, y):
    return (x >= 0 and x < N and y >= 0 and y < N and sol[x][y] == -1)

# Function to print the solution
def displaySolution():
    print("The possible solution: ")
    for x in range(N):
        for y in range(N):
            print(f"{sol[x][y]:3}", end=" ")
        print()

# Recursive function to solve the problem
def knightTour(x, y, move, xMove, yMove):
    if move == N*N:
        return True
    for k in range(8):
        xNext = x + xMove[k]
        yNext = y + yMove[k]
        if isValid(xNext, yNext):
            sol[xNext][yNext] = move
            if knightTour(xNext, yNext, move+1, xMove, yMove):
                return True
            else:
                # Backtracking
                sol[xNext][yNext] = -1
    return False

def findKnightTourSol():
    # All possible moves for knight
    xMove = [2, 1, -1, -2, -2, -1, 1, 2]
    yMove = [1, 2, 2, 1, -1, -2, -2, -1]
    # Starting from room (0, 0)
    sol[0][0] = 0
    if not knightTour(0, 0, 1, xMove, yMove):
        print("Solution does not exist")
        return False
    else:
        displaySolution()
    return True

if __name__ == "__main__":
    findKnightTourSol()