Рубрики

Задача тура Рыцаря | Откат-1

Backtracking — это алгоритмическая парадигма, которая пробует разные решения, пока не найдет решение, которое «работает». Проблемы, которые обычно решаются с помощью метода обратного отслеживания, имеют следующее общее свойство. Эти проблемы могут быть решены только путем попытки каждой возможной конфигурации, и каждая конфигурация пробуется только один раз. Наивное решение для этих проблем состоит в том, чтобы попробовать все конфигурации и вывести конфигурацию, которая соответствует заданным ограничениям проблемы. Возврат работает в инкрементном режиме и является оптимизацией по сравнению с наивным решением, где все возможные конфигурации генерируются и пробуются.

Например, рассмотрим следующую задачу « Рыцарский тур» .
Рыцарь размещается на первом блоке пустой доски и, двигаясь по правилам шахмат, должен посетить каждый квадрат ровно один раз.

Путь, по которому идет Рыцарь, чтобы покрыть все клетки

Следующая шахматная доска с 8 х 8 клеток. Числа в клетках указывают ход хода рыцаря.

Давайте сначала обсудим алгоритм Naive для этой задачи, а затем алгоритм Backtracking.

Наивный алгоритм для рыцарского тура
Наивный алгоритм состоит в том, чтобы генерировать все обходы один за другим и проверять, удовлетворяет ли сгенерированный обход ограничениям.

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

Backtracking работает постепенно, чтобы атаковать проблемы. Как правило, мы начинаем с пустого вектора решения и по одному добавляем элементы (значение элемента меняется от проблемы к проблеме. В контексте проблемы тура Найта, элемент — это ход рыцаря). Когда мы добавляем элемент, мы проверяем, нарушает ли добавление текущего элемента ограничение проблемы, если это так, то мы удаляем элемент и пробуем другие альтернативы. Если ни одна из альтернатив не сработает, мы переходим на предыдущий этап и удаляем элемент, добавленный на предыдущем этапе. Если мы вернемся к начальной стадии назад, мы скажем, что решения не существует. Если добавление элемента не нарушает ограничений, то мы рекурсивно добавляем элементы один за другим. Если вектор решения становится полным, то мы печатаем решение.

Алгоритм возврата для Knight's Tour
Ниже приводится алгоритм возврата для задачи тура Найта.

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" )

Ниже приведены реализации для задачи тура Найта. Он печатает одно из возможных решений в виде 2D матрицы. По сути, выходные данные представляют собой матрицу 2D 8 * 8 с числами от 0 до 63, и эти числа показывают шаги, сделанные Найтом.

С

// C программа для задачи Knight Tour
#include<stdio.h>
#define N 8

  

int solveKTUtil(int x, int y, int movei, int sol[N][N],

                int xMove[],  int yMove[]);

  
/ * Утилита для проверки, являются ли i, j действительными индексами

   для N * N шахматной доски * /

int isSafe(int x, int y, int sol[N][N])

{

    return ( x >= 0 && x < N && y >= 0 &&

             y < N && sol[x][y] == -1);

}

  
/ * Вспомогательная функция для печати решения матрицы 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");

    }

}

  
/ * Эта функция решает проблему Knight Tour, используя

   Откат. Эта функция в основном использует solveKTUtil ()

   решить проблему. Возвращает false если не завершено

   возможен тур, в противном случае верните true и напечатайте

   тур.

   Обратите внимание, что может быть более одного решения,

   эта функция печатает одно из возможных решений. * /

int solveKT()

{

    int sol[N][N];

  

    / * Инициализация матрицы решений * /

    for (int x = 0; x < N; x++)

        for (int y = 0; y < N; y++)

            sol[x][y] = -1;

  

    / * xMove [] и yMove [] определяют следующий ход рыцаря.

       xMove [] для следующего значения координаты x

       yMove [] для следующего значения координаты y * /

    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };

    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };

  

    // Поскольку рыцарь изначально находится в первом блоке

    sol[0][0]  = 0;

  

    / * Начните с 0,0 и изучите все туры, используя

       solveKTUtil () * /

    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0)

    {

        printf("Solution does not exist");

        return 0;

    }

    else

        printSolution(sol);

  

    return 1;

}

  
/ * Рекурсивная утилита для решения Knight Tour

   проблема * /

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;

  

   / * Попробуйте все последующие шаги от текущей координаты 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;// возвращение

       }

   }

  

   return 0;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    solveKT();

    return 0;

}

Джава

// Java-программа для задачи Knight Tour

class KnightTour {

    static int N = 8;

  

    / * Утилита для проверки, если i, j

       действительные индексы для N * N шахматной доски * /

    static boolean isSafe(int x, int y, int sol[][]) {

        return (x >= 0 && x < N && y >= 0 &&

                y < N && sol[x][y] == -1);

    }

  

    / * Утилита для печати решения

       матричный золь [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();

        }

    }

  

    / * Эта функция решает проблему Knight Tour

       используя Backtracking. Эта функция в основном

       решает проблему с помощью solveKTUtil (). Это

       возвращает false, если полный тур невозможен,

       в противном случае возвращает true и печатает тур.

       Обратите внимание, что может быть более одного

       решения, эта функция печатает один из

       Возможные решения. * /

    static boolean solveKT() {

        int sol[][] = new int[8][8];

  

        / * Инициализация матрицы решений * /

        for (int x = 0; x < N; x++)

            for (int y = 0; y < N; y++)

                sol[x][y] = -1;

  

       / * xMove [] и yMove [] определяют следующий ход рыцаря.

          xMove [] для следующего значения координаты x

          yMove [] для следующего значения координаты y * /

        int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2};

        int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1};

  

        // Поскольку рыцарь изначально находится в первом блоке

        sol[0][0] = 0;

  

        / * Начните с 0,0 и изучите все туры, используя

           solveKTUtil () * /

        if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) {

            System.out.println("Solution does not exist");

            return false;

        } else

            printSolution(sol);

  

        return true;

    }

  

    / * Рекурсивная вспомогательная функция для решения Knight

       Задача тура * /

    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;

  

        / * Попробуйте все последующие шаги от текущей координаты

            х, у * /

        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;// возвращение

            }

        }

  

        return false;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[]) {

        solveKT();

    }

}
// Этот код предоставлен Abhishek Shankhadhar

C #

// C # программа для
// Рыцарский тур

using System;

  

class GFG

{

    static int N = 8;

  

    / * Полезная функция для

    проверьте, действительны ли i, j

    указатели для N * N шахматной доски * /

    static bool isSafe(int x, int y, 

                       int[,] sol) 

    {

        return (x >= 0 && x < N && 

                y >= 0 && y < N &&

                sol[x, y] == -1);

    }

  

    / * Полезная функция для

    матрица решения печати 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();

        }

    }

  

    / * Эта функция решает

    Проблема Knight Tour с использованием

    Откат. Эта функция

    в основном использует solveKTUtil () для

    решать проблему. Возвращается

    false, если нет полного тура

    возможно, в противном случае верните true

    и печатает тур. пожалуйста, обратите внимание

    что может быть более одного

    решения, эта функция печатает

    одно из возможных решений. * /

    static bool solveKT() 

     {

        int[,] sol = new int[8, 8];

  

        / * Инициализация

        матрица решений * /

        for (int x = 0; x < N; x++)

            for (int y = 0; y < N; y++)

                sol[x, y] = -1;

  

     / * xMove [] и yMove [] определяют

        следующий ход рыцаря.

        xMove [] для следующего

        значение координаты х

        yMove [] для следующего

        значение координаты y * /

        int[] xMove = {2, 1, -1, -2, 

                      -2, -1, 1, 2};

        int[] yMove = {1, 2, 2, 1, 

                      -1, -2, -2, -1};

  

        // Поскольку Рыцарь

        // изначально в первом блоке

        sol[0, 0] = 0;

  

        / * Начните с 0,0 и изучите

        все туры с использованием solveKTUtil () * /

        if (!solveKTUtil(0, 0, 1, sol, 

                         xMove, yMove)) 

        {

            Console.WriteLine("Solution does "

                                  "not exist");

            return false;

        }

        else

            printSolution(sol);

  

        return true;

    }

  

    / * Рекурсивная функция полезности

    решить проблему Knight Tour * /

    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;

  

        / * Попробуйте все последующие шаги из

        текущая координата 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;

            }

        }

  

        return false;

    }

  

    // Код драйвера

    public static void Main() 

    {

        solveKT();

    }

}

  
// Этот код предоставлен mits.

python3

# Python3 программа для решения проблемы Knight Tour с использованием Backtracking

  
# Размер шахматной доски

n = 8

  

def isSafe(x,y,board):

    «»»

        Функция полезности, чтобы проверить, являются ли i, j действительными индексами

        для N * N шахматной доски

    «»»

    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1):

        return True

    return False

  

def printSolution(board):

    «»»

        Утилита для печати матрицы шахматной доски

    «»»

    for i in range(n):

        for j in range(n):

            print(board[i][j],end =' ')

        print()

  

  

def solveKT():

    «»»

        Эта функция решает проблему Knight Tour, используя

        Откат. Эта функция в основном использует solveKTUtil ()

        решить проблему. Возвращает false если не завершено

        возможен тур, в противном случае верните true и напечатайте

        тур.

        Обратите внимание, что может быть более одного решения,

        эта функция печатает одно из возможных решений.

    «»»

      

    # Инициализация матрицы платы

    board = [[-1 for i in range(n)]for i in range(n)]

      

    # move_x и move_y определяют следующий ход рыцаря.

    # move_x для следующего значения координаты x

    # move_y для следующего значения координаты y

    move_x = [2, 1, -1, -2, -2, -1, 1, 2]

    move_y = [1, 2, 2, 1, -1, -2, -2, -1]

      

    # Так как рыцарь изначально на первом блоке

    board[0][0] = 0

      

    # Счетчик шагов для положения рыцаря

    pos = 1

      

    # Проверка, существует ли решение или нет

    if(not solveKTUtil(board, 0, 0, move_x, move_y, pos)):

        print("Solution does not exist")

    else:

        printSolution(board)

  

def solveKTUtil(board,curr_x,curr_y,move_x,move_y,pos):

    «»»

        Рекурсивная утилита для решения Knight Tour

        проблема

    «»»

      

    if(pos == n**2):

        return True

      

    # Попробуйте все последующие шаги от текущей координаты 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(board,new_x,new_y,move_x,move_y,pos+1)):

                return True

              

            # Возврат

            board[new_x][new_y] = -1

    return False

          
# Программа драйвера для проверки вышеуказанной функции

if __name__ == "__main__"

    solveKT()

      
# Этот код предоставлен AAKASH PAL


Выход:

  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

Обратите внимание, что Backtracking — не лучшее решение проблемы тура Найта. Смотрите ниже статью для других лучших решений. Цель этого поста — объяснить Backtracking на примере.
Алгоритм Варнсдорфа для задачи тура Найта

Ссылки:
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

0.00 (0%) 0 votes