如何解决骑士旅行问题？|回溯算法设计1

2021年4月2日09:45:55 发表评论 1,088 次浏览

本文概述

回溯是一种算法范式，它尝试不同的解决方案，直到找到一个可行的解决方案。通常使用回溯技术解决的问题有以下共同特性。这些问题只能通过尝试所有可能的配置来解决，而且每个配置只尝试一次。对于这些问题，一个简单的解决方案是尝试所有配置，并输出符合给定问题约束的配置。回溯以一种增量的方式工作，并且是对原始解决方案的一种优化，在原始解决方案中生成并尝试所有可能的配置。

例如，考虑以下的骑士旅行问题。

问题描述：

给出一个N*N的棋盘，骑士放在一个空棋盘的第一块上。按照国际象棋的规则，骑士必须访问每个方格一次。打印它们访问的每个单元格的顺序。

例子：

Input : 
N = 8
Output:
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

骑士走过的路覆盖了所有的单元格

以下是带有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

// 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.  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 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#

// 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.

输出如下

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

这里有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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: