Как я могу пропустить повторяющиеся состояния доски в проблеме N-Queen? - PullRequest
Новая
       70

Как я могу пропустить повторяющиеся состояния доски в проблеме N-Queen?

1 голос
/ 20 марта 2020

Я написал некоторый код, который работает нормально, за исключением того факта, что он также находит дублированные состояния платы. Я хочу внести минимальные изменения в мой код, чтобы он мог найти только уникальные состояния платы. Я вставляю свой код ниже: 

class Solution {

List<List<String>> arrangements = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
    int visited[][] = new int[n][n];
    char board[][] = new char[n][n];
    solve(board,visited,0);
    return arrangements;
}

public boolean solve(char board[][], int visited[][], int queens) {
    if(queens == board.length) {
        return true;
    }
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board.length; j++) {
            if(visited[i][j] == 0) {
                changePosition(visited,i,j,1); //set
                board[i][j] = 'Q';
                if(solve(board,visited,queens+1)) {
                    save(board);
                }
                changePosition(visited,i,j,-1); // unset
                board[i][j] = '.';
            }
        }
    }
    return false;
}

public void save(char board[][]) {
    List<String> state = new ArrayList<>();
    for(int i = 0; i < board.length; i++) {
        String row = "";
        for(int j = 0; j < board.length; j++) {
            if(board[i][j] == 'Q'){
                row += 'Q';
            }else{
                row += '.';
            }
        }
        state.add(row);
    }
    arrangements.add(state);
}

public void changePosition(int visited[][], int i, int j, int val) {
    // setting the column
    for(int k = 0; k < visited.length; k++) {
        visited[k][j] += val;
    }
    visited[i][j] -= val;
    //setting the row
    for(int k = 0; k < visited.length; k++) {
        visited[i][k] += val;
    }
    visited[i][j] -= val;
    //setting 1 diagonal
    int a = i, b = j;
    while(a < visited.length && b < visited.length) {
        visited[a][b] += val;
        a++;
        b++;
    }
    visited[i][j] -= val;
    a = i;
    b = j;
    while(a >= 0 && b >= 0) {
        visited[a][b] += val;
        a--;
        b--;
    }
    visited[i][j] -= val;
    //setting 2nd diagonal
    a = i;
    b = j;
    while(a < visited.length && b >= 0) {
        visited[a][b] += val;
        a++;
        b--;
    }
    visited[i][j] -= val;
    a = i;
    b = j;
    while(a >=0 && b < visited.length) {
        visited[a][b] += val;
        a--;
        b++;
    }
}

} Функция solveNQueens возвращает все допустимые состояния платы в виде списковых состояний платы (состояние платы представлено в виде списка строк, которые представлены используя строку). Заранее спасибо!

...