N kraliça problemi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit Amazon Amdoklar alma ByteDance Facebook MAQ microsoft cuqquldamaq Viza
Geri qayıtmaBaxılıb 66

N kraliça problemi anlayışından istifadə etmək Geri qayıtma. Burada kraliçanı elə yerləşdiririk ki, hücum şəraitində heç bir kraliça olmasın. Kraliçaların hücum vəziyyəti, iki kraliçanın eyni sütunda, sətirdə və diaqonalda olması halında hücum altındadır. Bunu aşağıdakı rəqəmlə görək.

N kraliça problemiPin

Burada kraliçanın mövqeyinin sol tərəfdən 4-cü sırada və 4-cü sütunda olduğunu görürük. Qırmızı xəttin çəkildiyi hüceyrələrə başqa bir ana arı qoysaq, o ana arı hücum altındadır. Bu eyni diaqonalların vəziyyəti. Yaşıl xəttin çəkildiyi hüceyrələrə başqa bir ana arı qoysaq, o zaman ana arı hücum altındadır və burada eyni sətir və sütunun vəziyyəti.

Beləliklə, bu problemdə, N * N şahmat taxtasına N kraliça yerləşdirməliyik ki, heç bir kraliça hücum şəraitində olmasın.

Giriş Formatı

Bir ədəd tam N dəyəri olan birinci sətir.

Çıxış formatı

Bu hücrədə kraliça varsa, əks halda 1 hüceyrə dəyəri 0 olduğu N * N matrisini çap edin.

N kraliça problemi üçün izah

Burada ilk növbədə ith satırına bir kraliça və 1 <= i <= N olduğu ith sütununa qoyduq. Gəlin görək 4 Q problemi anlamaq üçün.

N kraliça problemiPin

İndi çapalonlar boyunca yalnız kraliçaların hücumuna məruz qaldığını görürük. Beləliklə, Ni kraliçanı Ni sətirdə necə yerləşdirəcəyimizi yoxlayırıq ki, 0 <= i <= n-1 olduğu təhlükəsiz zonada olsun. Burada 2-ci kraliçanı (2,2) hüceyrəyə yerləşdirə bilmərik, onu (2,3) hücrədə saxlayın. Sonra 3-cü kraliçanın vəziyyətini (2,3) hüceyrəyə dəyişirik.

N kraliça problemiPin

Artıq 3-cü kraliçanı təhlükəsiz zonada saxlamaq üçün bir vəziyyətin olmadığını gördük, buna görə 2-cü kraliçaya getmədən birbaşa kraliça 4-nin vəziyyətini dəyişdirdik. Və eyni sütuna iki kraliçanın gəlmədiyini unutmayın.

N kraliça problemiPin

Budur, 4-cü kraliçanı təhlükəsiz zonada saxlaya biləcəyimiz bir seçim edə bilməyəcəyimizi görürük. (1) -də 1,1 kraliça üçün bütün mümkün halları yoxlayırıq və hələlik öz həllimizi almırıq. Beləliklə, N kraliçaları yerləşdirdiyimiz şəraitdə 1-ci kraliçanın (1,2) və 2-ci kraliçanın (2,1) vəziyyətini dəyişdirin. O zaman mümkün yollardan biri:

Pin

İndi 2-ci kraliçanın hücum altında olduğunu görürük, sonra 2-ci kraliçanın mövqeyini (2,4) olaraq dəyişdiririk. Eyni sütunda iki kraliça daha yeni, buna görə 4-cü kraliçanın mövqeyini (1,4) olaraq dəyişdiririk.

Pin

Bu vəziyyətdə, 3-cü kraliça hücum vəziyyətindədir, buna görə 2-ci kraliçanın mövqeyini (3,1) olaraq dəyişdiririk. Eyni sütunda iki kraliça daha yeni, buna görə 4-cü kraliçanın mövqeyini (4,3) olaraq dəyişdiririk.

Pin

Bu vəziyyətdə hücum vəziyyətində heç bir kraliça olmadığı üçün cavabımızı birbaşa yazdırırıq. Kraliçanın bir hüceyrədə olduğu yerdə, əks halda 1-i çap edirik. Bu misal üçün giriş / çıxış formatına baxın.

Example Input:
4
Example Output:
0 1 0 0 
0 0 0 1
1 0 0 0
0 0 1 0

N queen problemi üçün istifadə olunan alqoritm

Step:1 Set all queens such that ith queen place on (i, i) cell.
Step:2 For j in range j to N:
       i) Check for all the possible values of the jth row.
       ii) Change the position of queens such that no queens come in the same column.
       iii) If the jth queen is placed on its right place, see other queens for that position.
       iv) If all queens are placed such that no queens are under attack then print the result.

N queen problemi üçün tətbiqetmə

/*C++ Implementation for N-QUEUE PROBLEM*/ 
#include<bits/stdc++.h>
using namespace std;
const int maxsize=1000;
int valid(int chess_board[][maxsize],int row, int column, int n)
{
    /*check for whether there is two queen on the same raw*/
    for(int i=0;i<column;i++)
    {
        if(chess_board[row][i])
        {
            return 0;
        }
    }
    /*check whether there is a queen on the left upper diagonal*/
    for(int i=row,j=column;i>=0&&j>=0;i--,j--)
    {
        if(chess_board[i][j])
        {
            return 0;
        }
    }
    /*check whether there is a queen on the left bottom diagonal*/
    for(int i=row,j=column;i<n&&j>=0;i++,j--)
    {
        if(chess_board[i][j])
        {
            return 0;
        }
    }
    /*if queen in safe condition*/
    return 1;
}
int solution_existency(int chess_board[][maxsize],int column,int n)
{
    /*if n queens are placed successfully*/
    if(column>=n)
    {
        return 1;
    }
    /*for each row check placing of queen is possible or not*/
    for(int i=0;i<n;i++)
    {
        if(valid(chess_board,i,column,n))
        {
            /*if its valid position then place at here(i,column)*/
            chess_board[i][column]=1;
            if(solution_existency(chess_board,column+1,n))
            {
                return 1;
            }
            /*where no place is possible to place the queen then remove the queen*/
            chess_board[i][column]=0;
        }
    }
    /*when no case found in which we store n queens in chess board*/
    return 0;
}
int n_queen(int chess_board[][maxsize], int n)
{
    int i=solution_existency(chess_board,0,n);
    return i;
}
int main() 
{ 
    int n;
    /*input value*/
    cin>>n;
    int chess_board[maxsize][maxsize];
    memset(chess_board,0,sizeof(chess_board));
    int possible=n_queen(chess_board,n);
    if(possible)
    {
    /*Print the chess board current state which is our answer*/
    cout<<"Chess board current state: "<<endl;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<chess_board[i][j]<<" ";
        }
        cout<<'\n';
    }
    }
    else
    {
        cout<<-1<<endl;
    }
    return 0; 
}
8
Chess board current state: 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 

Zamanın mürəkkəbliyi

O (N * N * N) bu, hər bir kraliçanın N * N Şahmat lövhəsində mümkün olan etibarlı vəziyyətini və hər bir kraliça mövqeyindən sonra növbənin etibarlı vəziyyətini yoxlamaq üçün O (N) vaxtını yoxladığımızda mümkün olan maksimum dərəcədə mümkündür.

Kosmik Mürəkkəblik

O (N * N) burada N şahmat taxtasının bir tərəfidir. Hər bir kraliçanın etibarlı mövqeyini tapmaq üçün əməliyyatı yerinə yetirmək üçün kraliçanın mövqeyini saxlamaq üçün N * N matrisindən istifadə edirik.

References

Translate »