如何解决骑士旅行问题（|回溯算法设计1） _国际象棋

本文概述

C ++
C
Java
Python3
C#

回溯是一种算法范式，它尝试不同的解决方案，直到找到一个可行的解决方案。通常使用回溯技术解决的问题有以下共同特性。这些问题只能通过尝试所有可能的配置来解决，而且每个配置只尝试一次。对于这些问题，一个简单的解决方案是尝试所有配置，并输出符合给定问题约束的配置。回溯以一种增量的方式工作，并且是对原始解决方案的一种优化，在原始解决方案中生成并尝试所有可能的配置。
例如，考虑以下的骑士旅行问题。
问题描述：
给出一个N*N的棋盘，骑士放在一个空棋盘的第一块上。按照国际象棋的规则，骑士必须访问每个方格一次。打印它们访问的每个单元格的顺序。
例子：

Input : N = 8 Output: 05938333017863 373431609622916 58136393227187 3548412661101528 42572494023619 4750455425201114 56435232213245 514655445342112

骑士走过的路覆盖了所有的单元格
以下是带有8 x 8格的棋盘。单元格中的数字表示骑士的移动次数。

文章图片
让我们首先讨论针对该问题的朴素算法, 然后再讨论回溯算法。
骑士旅行的朴素算法
天真的算法是一一生成所有行程, 并检查生成的行程是否满足约束条件。

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } }

回溯以递增的方式解决问题。通常, 我们从一个空的解决方案向量开始, 然后逐个添加项(项的含义因问题而异。在Knight的旅行问题中, 一项是Knight的举动)。添加项目时, 我们检查添加当前项目是否违反了问题约束, 如果确实存在, 则我们删除该项目并尝试其他替代方法。如果没有其他选择可行, 那么我们进入上一个阶段并删除在上一个阶段中添加的项目。如果我们回到初始阶段, 那么我们就说不存在解决方案。如果添加项目没有违反约束条件, 则我们递归地逐个添加项目。如果解决方案向量完成, 那么我们将打印解决方案。
骑士旅行的回溯算法
以下是针对Knight的旅行问题的回溯算法。

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" )

以下是Knight巡回问题的实现。它以2D矩阵形式打印一种可能的解决方案。基本上, 输出是2D 8 * 8矩阵, 其数字从0到63, 这些数字表示Knight进行的步骤。
C ++

// C++ program for Knight Tour problem #include < bits/stdc++.h> using namespace std; #define N 8 int solveKTUtil( int x, int y, int movei, int sol[N][N], int xMove[], int yMove[]); /* A utility function to check if i, j are valid indexes for N*N chessboard */ int 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 = 0; x < N; x++) { for ( int y = 0; y < N; y++) cout < < " " < < setw(2) < < sol[x][y] < < " " ; cout < < 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 = 0; x < N; x++) for ( int y = 0; 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) == 0) { cout < < "Solution does not exist" ; return 0; } else printSolution(sol); return 1; } /* A recursive utility function to solve Knight Tour problem */ int solveKTUtil( int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N]) { 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 1; else// backtracking sol[next_x][next_y] = -1; } } return 0; } // Driver Code int main() { // Function Call solveKT(); return 0; } // This code is contributed by ShubhamCoder

// C program for Knight Tour problem #include < stdio.h> #define N 8 int solveKTUtil( int x, int y, int movei, int sol[N][N], int xMove[], int yMove[]); /* A utility function to check if i, j are valid indexes for N*N chessboard */ int 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 = 0; x < N; x++) { for ( int y = 0; y < N; y++) printf ( " %2d " , sol[x][y]); printf ( "\n" ); } } /* 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 = 0; x < N; x++) for ( int y = 0; 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) == 0) { printf ( "Solution does not exist" ); return 0; } else printSolution(sol); return 1; } /* A recursive utility function to solve Knight Tour problem */ int solveKTUtil( int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N]) { 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 1; else sol[next_x][next_y] = -1; // backtracking } } return 0; } /* Driver Code */ int main() {// Function Call solveKT(); return 0; }

Java

// Java program for Knight Tour problem class KnightTour { static int N = 8 ; /* A utility function to check if i, j are valid indexes for N*N chessboard */ static boolean isSafe( int x, int y, int sol[][]) { return (x > = 0 & & x < N & & y > = 0 & & y < N & & sol[x][y] == - 1 ); } /* A utility function to print solution matrix sol[N][N] */ static void printSolution( int sol[][]) { for ( int x = 0 ; x < N; x++) { for ( int y = 0 ; y < N; y++) System.out.print(sol[x][y] + " " ); System.out.println(); } } /* This function solves the Knight Tour problem using Backtracking.Thisfunction 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.*/ static boolean solveKT() { int sol[][] = new int [ 8 ][ 8 ]; /* Initialization of solution matrix */ for ( int x = 0 ; x < N; x++) for ( int y = 0 ; 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[] = { 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 }; int yMove[] = { 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)) { System.out.println( "Solution does not exist" ); return false ; } else printSolution(sol); return true ; } /* A recursive utility function to solve Knight Tour problem */ static boolean solveKTUtil( int x, int y, int movei, int sol[][], int xMove[], int yMove[]) { int k, next_x, next_y; if (movei == N * N) return true ; /* 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)) return true ; else sol[next_x][next_y] = - 1 ; // backtracking } } return false ; } /* Driver Code */ public static void main(String args[]) { // Function Call solveKT(); } } // This code is contributed by Abhishek Shankhadhar

Python3

# Python3 program to solve Knight Tour problem using Backtracking # Chessboard Size n = 8 def isSafe(x, y, board): ''' A utility function to check if i, j are valid indexes for N*N chessboard ''' if (x > = 0 and y > = 0 and x < n and y < n and board[x][y] = = - 1 ): return True return False def printSolution(n, board): ''' A utility function to print Chessboard matrix ''' for i in range (n): for j in range (n): print (board[i][j], end = ' ' ) print () def solveKT(n): ''' 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. ''' # Initialization of Board matrix board = [[ - 1 for i in range (n)] for i in range (n)] # move_x and move_y define next move of Knight. # move_x is for next value of x coordinate # move_y is for next value of y coordinate move_x = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ] move_y = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] # Since the Knight is initially at the first block board[ 0 ][ 0 ] = 0 # Step counter for knight's position pos = 1 # Checking if solution exists or not if ( not solveKTUtil(n, board, 0 , 0 , move_x, move_y, pos)): print ( "Solution does not exist" ) else : printSolution(n, board) def solveKTUtil(n, board, curr_x, curr_y, move_x, move_y, pos): ''' A recursive utility function to solve Knight Tour problem ''' if (pos = = n * * 2 ): return True # Try all next moves from the current coordinate x, y for i in range ( 8 ): new_x = curr_x + move_x[i] new_y = curr_y + move_y[i] if (isSafe(new_x, new_y, board)): board[new_x][new_y] = pos if (solveKTUtil(n, board, new_x, new_y, move_x, move_y, pos + 1 )): return True # Backtracking board[new_x][new_y] = - 1 return False # Driver Code if __name__ = = "__main__" :# Function Call solveKT(n) # This code is contributed by AAKASH PAL

// C# program for // Knight Tour problem using System; class GFG { static int N = 8; /* A utility function to check if i, j are valid indexes for N*N chessboard */ static bool isSafe( int x, int y, int [, ] sol) { return (x > = 0 & & x < N & & y > = 0 & & y < N & & sol[x, y] == -1); } /* A utility function to print solution matrix sol[N][N] */ static void printSolution( int [, ] sol) { for ( int x = 0; x < N; x++) { for ( int y = 0; y < N; y++) Console.Write(sol[x, y] + " " ); Console.WriteLine(); } } /* 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. */ static bool solveKT() { int [, ] sol = new int [8, 8]; /* Initialization of solution matrix */ for ( int x = 0; x < N; x++) for ( int y = 0; 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 = { 2, 1, -1, -2, -2, -1, 1, 2 }; int [] yMove = { 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)) { Console.WriteLine( "Solution does " + "not exist" ); return false ; } else printSolution(sol); return true ; } /* A recursive utility function to solve Knight Tour problem */ static bool solveKTUtil( int x, int y, int movei, int [, ] sol, int [] xMove, int [] yMove) { int k, next_x, next_y; if (movei == N * N) return true ; /* 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)) return true ; else // backtracking sol[next_x, next_y] = -1; } } return false ; } // Driver Code public static void Main() { // Function Call solveKT(); } } // This code is contributed by mits.

输出如下

05938333017863 373431609622916 58136393227187 3548412661101528 42572494023619 4750455425201114 56435232213245 514655445342112

这里有N^2个单元，每个单元最多有8种可能的移动可供选择，所以最坏的运行时间是O(8^(N^2))。
重要的提示：
xMove没有顺序, yMove是错误的, 但是它们将极大地影响算法的运行时间。例如, 考虑以下情况：第8个选择是正确的选择, 而在此之前我们的代码运行了7条不同的错误路径。与尝试随机回溯相比, 具有启发性总是一个好主意。就像在这种情况下, 我们知道下一步可能在南向或东向, 然后检查通向第一条路线的路径是一个更好的策略。
请注意, 回溯并不是解决骑士旅行问题的最佳解决方案。有关其他更好的解决方案, 请参见下面的文章。这篇文章的目的是通过示例解释回溯。
Warnsdorff针对Knight巡回问题的算法
参考文献：
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf
http://www.cis.upenn.edu/~matuszek/cit594-2009/Lectures/35-backtracking.ppt
http://mathworld.wolfram.com/KnightsTour.html
http://en.wikipedia.org/wiki/Knight%27s_tour
【如何解决骑士旅行问题（|回溯算法设计1）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。