N-Queen Начинающий Возвращение - PullRequest
Новая
       25

N-Queen Начинающий Возвращение

0 голосов
/ 14 января 2019

Чтобы попрактиковаться в том, что я узнал об алгоритмах возврата, я пытаюсь решить проблему N-Queen.

Я написал несколько функций для проверки законности перемещения, но я не понимаю, как реализовать те из них, которые используют возврат. 

bool manger_ligne (int a[][4],int i) {
    for (int j=0;j<4;j++) {
        if (a[i][j] == 1)
            return false ;
    }

    return true;
}

bool manger_col (int a[][4],int j) {
    for (int i=0;i<4;i++) {
        if (a[i][j] == 1)
            return false ;
    }
    return true ; 
}

bool isTrue (int a[][4],int i,int j,int k) {
    if (k==0) {
        return 1;
    }
    if (i > 3 && j > 3) {
        return 0;
    }

    if (manger_diagonal(a, i, j) == true && manger_col(a, j) == true &&
        manger_ligne(a, i) == true) {
        a[i][j] = 1;
        if (isTrue(a, i, j+1 ,k) == true) {
            if (isTrue(a, i+1,j ,k) == true) //backtracking problem
                return true;
        }
        a[i][j] = 0;
    }
    return false ;
}

1 Ответ

0 голосов
/ 14 января 2019

несколько дней назад мне пришлось выполнить эту задачу как школьное задание. Это решение с 8 королевами. Я решил это следующим образом:

В основном я вызываю функцию solveQn. Затем программа все делает сама.

Bool решитьNQ: 

bool solveNQ(){
int board[N][N] = { 
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0}
};
if ( solveNQUtil(board, 0) == false )
{
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}

Bool solveNQUntil: 

bool solveNQUtil(int board[N][N], int col){
if (col >= N)
    return true;
for (int i = 0; i < N; i++)
{
    if ( isSafe(board, i, col) )
    {
        board[i][col] = 1;
        if ( solveNQUtil(board, col + 1) )
            return true;
        board[i][col] = 0;
    }
}
return false;
}

Bool isSafe: 

bool isSafe(int board[N][N], int row, int col){
int i, j;

for (i = 0; i < col; i++)
    if (board[row][i])
        return false;

for (i=row, j=col; i>=0 && j>=0; i--, j--)
    if (board[i][j])
        return false;

for (i=row, j=col; j>=0 && i<N; i++, j--)
    if (board[i][j])
        return false;

return true;
}

Вывести решение: 

void printSolution(int board[N][N]){
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
        printf(" %d ", board[i][j]);
    printf("\n");
}
}

В начале кода вам нужно определить глобальную переменную N со значением 8, в данном случае. Вам также необходимо включить заголовок stdbool.h, потому что здесь вы будете использовать Booleans.

...