Размещение чисел в двумерном массиве с помощью шаблона движения шахматного рыцаря в Java с использованием рекурсии - PullRequest
Новая
       7

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

0 голосов
/ 28 сентября 2018 
public class ChessComplete 
{
    private int size;
    private int[][] board;
    private long callNum;

    public ChessComplete(int size)//constructor with 2D array size as a parameter
    {
        this.size = size;
        board = new int [size][size];
        board[0][0] = 1;
    }
    public boolean isValid(int r, int c)//To check the if the number that is added is in the 2D array is in bound
    {
        if(r < 0 || c < 0 || r >= size || c >= size)
        {
            return false;
        }
        return true;
    }

    /*
     * Move through the 2D array by placing the consecutive number for each (row,col) until its full
     * Moves Are only allowed in a chess knight pattern
     */
    public boolean move(int r, int c, int count) {
    callNum++;

    if (!isValid(r, c)) {
        return false;
    }

    if (count == (size * size))// Base case if count reaches the end of 2D
                                // array

    {

        return true;
    }
    board[r][c] = count;// fills the positon with the current count

    if (board[r][c] == 0) {
        return false;
    }

    // Check if each possible move is valid or not
    if (board[r][c] != 0) {

        for (int i = 0; i < 8; i++) {

            int X[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
            int Y[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

            // Position of knight after move
            int x = r + X[i];
            int y = c + Y[i];

            if (move(x, y, count + 1)) {

                return move(x, y, count + 1);
            }

        }
    }
    board[r][c] = 0;
    return false;
}
    public long getSteps()//Number of reccursive trials
    {
        return callNum;
    }
    public void displayBoard()
    {
        String s = " ";
        for(int r = 0; r < size; r++)
        {
            for(int c = 0; c < size; c++)
            {
                System.out.print(board[r][c] + " ");
            }
            System.out.println();
        }

    }
}

Вывод: 

1,  0,  0,  0,  0, 

0,  0,  0,  23, 0, 

0,  2,  0,  0,  0, 

0,  0,  0,  0, 24, 

0,  0,  3,  0,  0 

Recursive method call count: 78,293,671

Пояснение

Уведомление в позиции (строка, столбец) (0, 0) есть 1 и в позиции (2, 1) тамэто 2.Как видите, рыцарь на шахматной доске движется аналогичным образом.Таким образом, нам нужно заполнить весь 2D-массив последовательными числами так, чтобы он строго следовал схеме рыцаря.

Проблема

Я не понимаю, почему весь 2D-массив не используетсязаполнены всеми другими последовательными номерами.Например, после заполнения позиции 3 в двумерном массиве числа пропускаются до 23.

1 Ответ

0 голосов
/ 28 сентября 2018

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

Измените isValid, чтобы проверить, что целевой квадрат пуст: 

public boolean isValid(int r, int c) {
    if (r < 0 || c < 0 || r >= size || c >= size || board[r][c] != 0) {
        return false;
    }
    return true;
}

... и удалите шаг инициализации board[0][0] = 1; в конструкторе (он должен быть установлен при первом вызове move).

Дополнительно (но не фатально),

if (move(x, y, count + 1)) {
    return move(x, y, count + 1);
}

Должно быть 

if (move(x, y, count + 1)) {
    return true;
}

А проверки if (board[r][c] == 0) и if (board[r][c] != 0) ничего не делают, потому что они происходят сразу после того, как вы установили board[r][c] = count;.

...