Нахождение всех уникальных возможных ходов рыцаря

Question

у нас есть доска 8x8 с ячейками, начиная с одной, моя цель - написать такую ​​функцию с сигнатурой: public static String findPos(int i, int j, int n), которая принимает параметры (i, j) начальной позиции коня на доске, а n - это общее количество ходов, которые он совершит (n> = 0)

Например:

findPos (1,1,0) вернет (1,1) только потому, что при 0 ходах рыцарь может только оставайся на своей собственной позиции

findPos (1,1,1) вернется (1,1), (2,3), (3,2)

Я написал не очень красиво решение, однако он подсчитывает повторяющиеся позиции, которые может занять конь в случае, например findPos (1,1,2):

public static String findPos(int i, int j, int n) {

        if (n == 0) {
            if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
                return "(" + i + ", " + j + " )";;
            } else {
                return "";
            }

        } else {

            if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
                return "(" + i + ", " + j + " )" + findPos(i - 1, j - 2, n - 1)
                        + findPos(i - 2, j - 1, n - 1)
                        + findPos(i - 2, j + 1, n - 1)
                        + findPos(i - 1, j + 2, n - 1)
                        + findPos(i + 1, j + 2, n - 1)
                        + findPos(i + 2, j + 1, n - 1)
                        + findPos(i + 2, j - 1, n - 1)
                        + findPos(i + 1, j - 2, n - 1);

            } else {

                return findPos(i - 1, j - 2, n - 1)
                        + findPos(i - 2, j - 1, n - 1)
                        + findPos(i - 2, j + 1, n - 1)
                        + findPos(i - 1, j + 2, n - 1)
                        + findPos(i + 1, j + 2, n - 1)
                        + findPos(i + 2, j + 1, n - 1)
                        + findPos(i + 2, j - 1, n - 1)
                        + findPos(i + 1, j - 2, n - 1);

            }

        }

    }

Мой вопрос: как я могу улучшить код / ​​рекурсию, чтобы он возвращал только уникальные позиции он может занять, потому что в настоящее время он также пишет дубликаты?

Answer 1

В вашем коде вы используете логический массив, чтобы пометить посещенные позиции и предотвратить повторный вызов этой позиции.

Вот модификация:

   static boolean visited[][] = new boolean[9][9];
   public static String findPos(int i, int j, int n) {
      if(i<1 || i>8 || j<1 || j>8 || visited[i][j]) return "";
      else {
         visited[i][j] = true;
         if (n == 0) {
            if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
               return "(" + i + ", " + j + " )";
            } else {
               return "";
            }
         } else {
            if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
               return "(" + i + ", " + j + " )" + findPos(i - 1, j - 2, n - 1)
                  + findPos(i - 2, j - 1, n - 1)
                  + findPos(i - 2, j + 1, n - 1)
                  + findPos(i - 1, j + 2, n - 1)
                  + findPos(i + 1, j + 2, n - 1)
                  + findPos(i + 2, j + 1, n - 1)
                  + findPos(i + 2, j - 1, n - 1)
                  + findPos(i + 1, j - 2, n - 1);

            } else {

               return findPos(i - 1, j - 2, n - 1)
                  + findPos(i - 2, j - 1, n - 1)
                  + findPos(i - 2, j + 1, n - 1)
                  + findPos(i - 1, j + 2, n - 1)
                  + findPos(i + 1, j + 2, n - 1)
                  + findPos(i + 2, j + 1, n - 1)
                  + findPos(i + 2, j - 1, n - 1)
                  + findPos(i + 1, j - 2, n - 1);
            }
         }
      }
   }

Или, вы можете использовать алгоритм BFS, чтобы достичь этого довольно легко. Чтобы узнать больше об алгоритме BFS, вы можете использовать этот сайт . Подробности в коде. (Извините за использование C ++ вместо Java, я надеюсь, что вы сможете получить суть)

Вот как вы можете это сделать -

#include<bits/stdc++.h>
using namespace std;
//This array is to check if a position is visited or not
bool visited[8][8];
//Here you're making a direction array for the move of the knight
int row[] = {-2,-1,+1,+2,+2,+1,-1,-2};
int col[] = {+1,+2,+2,+1,-1,-2,-2,-1};
//Returning the next move based on the current position and the move no
pair<int,int> nextMove(pair<int,int> curPos, int moveNo) {
    return {
        curPos.first+row[moveNo],
        curPos.second+col[moveNo]
    };
}
//Checking if the current position is in the board or not
bool validity(pair<int,int> curPos) {
    if(curPos.first<1 || curPos.first>8) return false;
    if(curPos.second<1 || curPos.second>8) return false;
    return true;
}
//BFS algorithm
string bfs(pair<int,int> curPos, int n) {
    //Making the string representation of the visited positions
    string ans = "("+to_string(curPos.first)+","+to_string(curPos.second)+")";
    queue<pair<int,int>> q;
    q.push(curPos);
    //Maintaining level so that it doesn't exceed the given "n" number of moves
    map<pair<int,int>, int> level;
    level[curPos] = 0;
    visited[curPos.first][curPos.second] = true;
    while(!q.empty()) {
        curPos = q.front();
        if(level[curPos]>=n) break;
        q.pop();
        for(int i=0; i<8; i++) {
            pair<int,int> tempPos = nextMove(curPos,i);
            if(validity(tempPos) && !visited[tempPos.first][tempPos.second]) {
                level[tempPos] = level[curPos]+1;
                q.push(tempPos);
                visited[tempPos.first][tempPos.second] = true;
                ans += "("+to_string(tempPos.first)+","+to_string(tempPos.second)+")";
            }
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    int i,j,n;
    cin >> i >> j >> n;
    cout << bfs({i,j},n) << "\n";
}

Пример ввода:

1 1 2

Пример ввода:

(1,1)(2,3)(3,2)(1,5)(3,5)(4,4)(4,2)(3,1)(1,3)(2,4)(5,3)(5,1)