Код Knight's Tour работает в бесконечном цикле, не достигает решения - PullRequest
Новая
       16

Код Knight's Tour работает в бесконечном цикле, не достигает решения

0 голосов
/ 25 декабря 2018

Мой рекурсивный подход к возвращению в Knight's Tour проходит бесконечный цикл.Сначала я думал, что проблема может занимать так много времени в целом, но некоторые решения делают это в одно мгновение.Пожалуйста, расскажите, что не так с моим кодом.

package io.github.thegeekybaniya.InterviewPrep.TopTopics.Backtracking;

import java.util.Arrays;

public class KnightsTour {
    private static int counter=0;

    public static void main(String[] args) {

        knightsTour(8);
    }

    private static void knightsTour(int i) {
        int[][] board = new int[i][i];
        for (int[] arr :
                board) {
            Arrays.fill(arr, -1);

        }
        board[0][0] = 0;
        knightsTour(board,0,1);

    }

    private static boolean knightsTour(int[][] board, int cellno, int stepno) {
        if (stepno == board.length * board.length) {
            printBoard(board);
            return true;
        }

        int[][] dirs = {
                {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
        };
        int row = cellno / board.length, col = cellno % board.length;
        for (int i = 0; i < dirs.length; i++) {
            int r = dirs[i][0] + row;
            int c = dirs[i][1] + col;
            if (isSafe(board, r, c)&&board[r][c]==-1) {
                int ncell = r * board.length + c;
                board[r][c] = stepno;
                if (knightsTour(board, ncell, stepno + 1)) {
                    return true;
                } else {
                    board[r][c] = -1;
                }
            }
        }


        return false;
    }

    private static boolean isSafe(int[][] board, int r, int c) {

        return r >= 0 && c >= 0 && r < board.length && c < board.length;
    }

    private static void printBoard(int[][] board) {
        System.out.println(++counter);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.print(board[i][j]+" ");

            }
            System.out.println();
        }
    }

}

1 Ответ

0 голосов
/ 26 декабря 2018

В вашем коде нет ошибки, просто грубый метод медленный, потому что пространство поиска огромно.Вы можете ускорить поиск, применив правило Warnsdorf .Это эвристика для выбора следующего хода, когда вы всегда пробуете ход, который приводит к наименьшему количеству доступных ходов для следующего хода после этого.Это можно сделать в несколько простых циклов: 

int row = cellno / board.length, col = cellno % board.length;

// find move with fewest moves available for the next move:
int minMovesAvailable = 8;
int minMovesDir = 0;
for (int i = 0; i < dirs.length; i++) {
    int r = dirs[i][0] + row;
    int c = dirs[i][1] + col;
    if (isSafe(board, r, c)&&board[r][c]==-1)
    {
        board[r][c] = stepno;
        int movesAvailable = 0;
        for (int j = 0; j < dirs.length; j++) {
            int r2 = dirs[j][0] + r;
            int c2 = dirs[j][1] + c;
            if (isSafe(board, r2, c2)&&board[r2][c2]==-1)
            {
                movesAvailable++;
            }
        }
        board[r][c] = -1;
        if(movesAvailable < minMovesAvailable)
        {
            minMovesAvailable = movesAvailable;
            minMovesDir = i;
        }
    }
}

// now recurse this move first:
// int r = dirs[minMovesDir][0] + row;
// int c = dirs[minMovesDir][1] + col;
...