مساله سفر اسب — به زبان ساده

1// C program for Knight Tour problem 
2#include<stdio.h> 
3#define N 8 
4  
5int solveKTUtil(int x, int y, int movei, int sol[N][N], 
6                int xMove[],  int yMove[]); 
7  
8/* A utility function to check if i,j are valid indexes 
9   for N*N chessboard */
10bool isSafe(int x, int y, int sol[N][N]) 
11{ 
12    return ( x >= 0 && x < N && y >= 0 && 
13             y < N && sol[x][y] == -1); 
14} 
15  
16/* A utility function to print solution matrix sol[N][N] */
17void printSolution(int sol[N][N]) 
18{ 
19    for (int x = 0; x < N; x++) 
20    { 
21        for (int y = 0; y < N; y++) 
22            printf(" %2d ", sol[x][y]); 
23        printf("\n"); 
24    } 
25} 
26  
27/* This function solves the Knight Tour problem using 
28   Backtracking.  This function mainly uses solveKTUtil() 
29   to solve the problem. It returns false if no complete 
30   tour is possible, otherwise return true and prints the 
31   tour. 
32   Please note that there may be more than one solutions, 
33   this function prints one of the feasible solutions.  */
34bool solveKT() 
35{ 
36    int sol[N][N]; 
37  
38    /* Initialization of solution matrix */
39    for (int x = 0; x < N; x++) 
40        for (int y = 0; y < N; y++) 
41            sol[x][y] = -1; 
42  
43    /* xMove[] and yMove[] define next move of Knight. 
44       xMove[] is for next value of x coordinate 
45       yMove[] is for next value of y coordinate */
46    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 }; 
47    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 }; 
48  
49    // Since the Knight is initially at the first block 
50    sol[0][0]  = 0; 
51  
52    /* Start from 0,0 and explore all tours using 
53       solveKTUtil() */
54    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false) 
55    { 
56        printf("Solution does not exist"); 
57        return false; 
58    } 
59    else
60        printSolution(sol); 
61  
62    return true; 
63} 
64  
65/* A recursive utility function to solve Knight Tour 
66   problem */
67int solveKTUtil(int x, int y, int movei, int sol[N][N], 
68                int xMove[N], int yMove[N]) 
69{ 
70   int k, next_x, next_y; 
71   if (movei == N*N) 
72       return true; 
73  
74   /* Try all next moves from the current coordinate x, y */
75   for (k = 0; k < 8; k++) 
76   { 
77       next_x = x + xMove[k]; 
78       next_y = y + yMove[k]; 
79       if (isSafe(next_x, next_y, sol)) 
80       { 
81         sol[next_x][next_y] = movei; 
82         if (solveKTUtil(next_x, next_y, movei+1, sol, 
83                         xMove, yMove) == true) 
84             return true; 
85         else
86             sol[next_x][next_y] = -1;// backtracking 
87       } 
88   } 
89  
90   return false; 
91} 
92  
93/* Driver program to test above functions */
94int main() 
95{ 
96    solveKT(); 
97    return 0;

1// Java program for Knight Tour problem 
2class KnightTour { 
3    static int N = 8; 
4  
5    /* A utility function to check if i,j are 
6       valid indexes for N*N chessboard */
7    static boolean isSafe(int x, int y, int sol[][]) { 
8        return (x >= 0 && x < N && y >= 0 && 
9                y < N && sol[x][y] == -1); 
10    } 
11  
12    /* A utility function to print solution 
13       matrix sol[N][N] */
14    static void printSolution(int sol[][]) { 
15        for (int x = 0; x < N; x++) { 
16            for (int y = 0; y < N; y++) 
17                System.out.print(sol[x][y] + " "); 
18            System.out.println(); 
19        } 
20    } 
21  
22    /* This function solves the Knight Tour problem 
23       using Backtracking.  This  function mainly 
24       uses solveKTUtil() to solve the problem. It 
25       returns false if no complete tour is possible, 
26       otherwise return true and prints the tour. 
27       Please note that there may be more than one 
28       solutions, this function prints one of the 
29       feasible solutions.  */
30    static boolean solveKT() { 
31        int sol[][] = new int[8][8]; 
32  
33        /* Initialization of solution matrix */
34        for (int x = 0; x < N; x++) 
35            for (int y = 0; y < N; y++) 
36                sol[x][y] = -1; 
37  
38       /* xMove[] and yMove[] define next move of Knight. 
39          xMove[] is for next value of x coordinate 
40          yMove[] is for next value of y coordinate */
41        int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2}; 
42        int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1}; 
43  
44        // Since the Knight is initially at the first block 
45        sol[0][0] = 0; 
46  
47        /* Start from 0,0 and explore all tours using 
48           solveKTUtil() */
49        if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) { 
50            System.out.println("Solution does not exist"); 
51            return false; 
52        } else
53            printSolution(sol); 
54  
55        return true; 
56    } 
57  
58    /* A recursive utility function to solve Knight 
59       Tour problem */
60    static boolean solveKTUtil(int x, int y, int movei, 
61                               int sol[][], int xMove[], 
62                               int yMove[]) { 
63        int k, next_x, next_y; 
64        if (movei == N * N) 
65            return true; 
66  
67        /* Try all next moves from the current coordinate 
68            x, y */
69        for (k = 0; k < 8; k++) { 
70            next_x = x + xMove[k]; 
71            next_y = y + yMove[k]; 
72            if (isSafe(next_x, next_y, sol)) { 
73                sol[next_x][next_y] = movei; 
74                if (solveKTUtil(next_x, next_y, movei + 1, 
75                                sol, xMove, yMove)) 
76                    return true; 
77                else
78                    sol[next_x][next_y] = -1;// backtracking 
79            } 
80        } 
81  
82        return false; 
83    } 
84  
85    /* Driver program to test above functions */
86    public static void main(String args[]) { 
87        solveKT(); 
88    } 
89} 
90// This code is contributed by Abhishek Shankhadhar 

1// C# program for  
2// Knight Tour problem 
3using System; 
4  
5class GFG 
6{ 
7    static int N = 8; 
8  
9    /* A utility function to  
10    check if i,j are valid  
11    indexes for N*N chessboard */
12    static bool isSafe(int x, int y,  
13                       int[,] sol)  
14    { 
15        return (x >= 0 && x < N &&  
16                y >= 0 && y < N && 
17                sol[x, y] == -1); 
18    } 
19  
20    /* A utility function to  
21    print solution matrix sol[N][N] */
22    static void printSolution(int[,] sol)  
23    { 
24        for (int x = 0; x < N; x++)  
25        { 
26            for (int y = 0; y < N; y++) 
27                Console.Write(sol[x, y] + " "); 
28            Console.WriteLine(); 
29        } 
30    } 
31  
32    /* This function solves the  
33    Knight Tour problem using  
34    Backtracking. This function  
35    mainly uses solveKTUtil() to  
36    solve the problem. It returns  
37    false if no complete tour is  
38    possible, otherwise return true  
39    and prints the tour. Please note  
40    that there may be more than one  
41    solutions, this function prints  
42    one of the feasible solutions. */
43    static bool solveKT()  
44     { 
45        int[,] sol = new int[8, 8]; 
46  
47        /* Initialization of 
48        solution matrix */
49        for (int x = 0; x < N; x++) 
50            for (int y = 0; y < N; y++) 
51                sol[x, y] = -1; 
52  
53     /* xMove[] and yMove[] define 
54        next move of Knight. 
55        xMove[] is for next  
56        value of x coordinate 
57        yMove[] is for next  
58        value of y coordinate */
59        int[] xMove = {2, 1, -1, -2,  
60                      -2, -1, 1, 2}; 
61        int[] yMove = {1, 2, 2, 1,  
62                      -1, -2, -2, -1}; 
63  
64        // Since the Knight is  
65        // initially at the first block 
66        sol[0, 0] = 0; 
67  
68        /* Start from 0,0 and explore  
69        all tours using solveKTUtil() */
70        if (!solveKTUtil(0, 0, 1, sol,  
71                         xMove, yMove))  
72        { 
73            Console.WriteLine("Solution does "+  
74                                  "not exist"); 
75            return false; 
76        } 
77        else
78            printSolution(sol); 
79  
80        return true; 
81    } 
82  
83    /* A recursive utility function  
84    to solve Knight Tour problem */
85    static bool solveKTUtil(int x, int y, int movei, 
86                            int[,] sol, int[] xMove, 
87                            int[] yMove)  
88    { 
89        int k, next_x, next_y; 
90        if (movei == N * N) 
91            return true; 
92  
93        /* Try all next moves from  
94        the current coordinate x, y */
95        for (k = 0; k < 8; k++)  
96        { 
97            next_x = x + xMove[k]; 
98            next_y = y + yMove[k]; 
99            if (isSafe(next_x, next_y, sol))  
100            { 
101                sol[next_x,next_y] = movei; 
102                if (solveKTUtil(next_x, next_y, movei +  
103                                 1, sol, xMove, yMove)) 
104                    return true; 
105                else
106                    // backtracking 
107                    sol[next_x,next_y] = -1; 
108            } 
109        } 
110  
111        return false; 
112    } 
113  
114    // Driver Code 
115    public static void Main()  
116    { 
117        solveKT(); 
118    } 
119} 
120  
121// This code is contributed by mits. 

1# Python3 program to solve Knight Tour problem using Backtracking 
2  
3# Chessboard Size 
4n = 8
5  
6def isSafe(x,y,board): 
7    ''' 
8        A utility function to check if i,j are valid indexes  
9        for N*N chessboard 
10    '''
11    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1): 
12        return True
13    return False
14  
15def printSolution(board): 
16    ''' 
17        A utility function to print Chessboard matrix 
18    '''
19    for i in range(n): 
20        for j in range(n): 
21            print(board[i][j],end =' ') 
22        print() 
23  
24  
25def solveKT(): 
26    ''' 
27        This function solves the Knight Tour problem using  
28        Backtracking. This function mainly uses solveKTUtil()  
29        to solve the problem. It returns false if no complete  
30        tour is possible, otherwise return true and prints the  
31        tour.  
32        Please note that there may be more than one solutions,  
33        this function prints one of the feasible solutions. 
34    '''
35      
36    # Initialization of Board matrix  
37    board = [[-1 for i in range(n)]for i in range(n)] 
38      
39    # move_x and move_y define next move of Knight.  
40    # move_x is for next value of x coordinate  
41    # move_y is for next value of y coordinate 
42    move_x = [2, 1, -1, -2, -2, -1, 1, 2] 
43    move_y = [1, 2, 2, 1, -1, -2, -2, -1] 
44      
45    # Since the Knight is initially at the first block 
46    board[0][0] = 0
47      
48    # Step counter for knight's position 
49    pos = 1
50      
51    # Checking if solution exists or not  
52    if(not solveKTUtil(board, 0, 0, move_x, move_y, pos)): 
53        print("Solution does not exist") 
54    else: 
55        printSolution(board) 
56  
57def solveKTUtil(board,curr_x,curr_y,move_x,move_y,pos): 
58    ''' 
59        A recursive utility function to solve Knight Tour  
60        problem 
61    '''
62      
63    if(pos == n**2): 
64        return True
65      
66    # Try all next moves from the current coordinate x, y 
67    for i in range(8): 
68        new_x = curr_x + move_x[i] 
69        new_y = curr_y + move_y[i] 
70        if(isSafe(new_x,new_y,board)): 
71            board[new_x][new_y] = pos 
72            if(solveKTUtil(board,new_x,new_y,move_x,move_y,pos+1)): 
73                return True
74              
75            # Backtracking 
76            board[new_x][new_y] = -1
77    return False
78          
79# Driver program to test above function  
80if __name__ == "__main__":  
81    solveKT() 
82      
83# This code is contributed by AAKASH PAL