N രാജ്ഞിയുടെ പ്രശ്നം


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ അംദോക്കുകൾ ആപ്പിൾ ബൈറ്റ്ഡാൻസ് ഫേസ്ബുക്ക് MAQ മൈക്രോസോഫ്റ്റ് ട്വിറ്റർ വിസ
ബാക്ക്ട്രാക്കിംഗ്

N രാജ്ഞിയുടെ പ്രശ്നം എന്ന ആശയം ഉപയോഗിച്ച് ബാക്ക്ട്രാക്കിംഗ്. ആക്രമണാവസ്ഥയിൽ ഒരു രാജ്ഞിയുമില്ലാത്തവിധം ഞങ്ങൾ ഇവിടെ രാജ്ഞിയെ പ്രതിഷ്ഠിക്കുന്നു. ഒരേ നിര, വരി, ഡയഗണൽ എന്നിവയിൽ രണ്ട് രാജ്ഞികൾ ഉണ്ടെങ്കിൽ അവർ ആക്രമണത്തിലാണ് എന്നതാണ് രാജ്ഞികളുടെ ആക്രമണ അവസ്ഥ. ചുവടെയുള്ള ചിത്രം ഉപയോഗിച്ച് ഇത് നോക്കാം.

N രാജ്ഞിയുടെ പ്രശ്നം

രാജ്ഞിയുടെ സ്ഥാനം ഇടത് വശത്ത് നിന്ന് നാലാമത്തെ വരിയിലും നാലാമത്തെ നിരയിലുമാണെന്ന് ഇവിടെ കാണാം. ചുവന്ന വര വരച്ച സെല്ലുകളിൽ ഞങ്ങൾ മറ്റൊരു രാജ്ഞിയെ വച്ചാൽ, ആ രാജ്ഞി ആക്രമണത്തിലാണ്. ഇതാണ് ഒരേ ഡയഗണലുകളുടെ കേസ്. പച്ച വര വരച്ച സെല്ലുകളിൽ ഞങ്ങൾ മറ്റൊരു രാജ്ഞിയെ വച്ചാൽ, ആ രാജ്ഞി ആക്രമണത്തിലാണ്, ഇതിൽ ഇതാണ് ഒരേ വരിയുടെയും നിരയുടെയും കേസ്.

അതിനാൽ, ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾ‌ N രാജ്ഞികളെ N * N ചെസ്സ്ബോർ‌ഡിൽ‌ സ്ഥാപിക്കേണ്ടതുണ്ട്, കാരണം രാജ്ഞികളൊന്നും ആക്രമണ സാഹചര്യങ്ങളിൽ‌ ഇല്ല.

ഇൻപുട്ട് ഫോർമാറ്റ്

ഒറ്റ സംഖ്യ മൂല്യം N. ഉൾക്കൊള്ളുന്ന ആദ്യ വരി.

Put ട്ട്‌പുട്ട് ഫോർമാറ്റ്

ആ സെല്ലിൽ രാജ്ഞി ഉണ്ടെങ്കിൽ സെൽ മൂല്യം 1 ആയിരിക്കുന്ന N * N മാട്രിക്സ് അച്ചടിക്കുക.

എൻ രാജ്ഞി പ്രശ്നത്തിനുള്ള വിശദീകരണം

ഇവിടെ ആദ്യം നമ്മൾ ഒരു രാജ്ഞിയെ ith വരിയിലും 1 <= i <= N. നമുക്ക് നോക്കാം 4 Q പ്രശ്നം മനസ്സിലാക്കാൻ.

N രാജ്ഞിയുടെ പ്രശ്നം

ഇപ്പോൾ, രാജ്ഞികൾ മാത്രമേ ഡയഗോണലുകളിലൂടെ ആക്രമിക്കപ്പെടുന്നുള്ളൂ. അതിനാൽ, നി <വരി നി നി വരിയിൽ എങ്ങനെ സ്ഥാപിക്കാമെന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു, അത് 0 <= i <= n-1 ഉള്ള ഒരു സുരക്ഷിത മേഖലയിലാണ്. ഇവിടെ നമുക്ക് രണ്ടാമത്തെ രാജ്ഞിയെ (2) സെല്ലിൽ സ്ഥാപിക്കാൻ കഴിയില്ല, അതിനാൽ (2,2) സെല്ലിൽ സൂക്ഷിക്കുക. മൂന്നാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (2,3) സെല്ലിലേക്ക് മാറ്റുന്നു.

N രാജ്ഞിയുടെ പ്രശ്നം

ഇപ്പോൾ, മൂന്നാം രാജ്ഞിയെ സുരക്ഷിത മേഖലയിൽ സൂക്ഷിക്കാൻ സ്ഥാനമില്ലെന്ന് ഞങ്ങൾ കാണുന്നു, അതിനാൽ നാലാമത്തെ രാജ്ഞിയുടെ അടുത്തേക്ക് പോകാതെ തന്നെ രാജ്ഞി 3 ന്റെ സ്ഥാനം ഞങ്ങൾ നേരിട്ട് മാറ്റുന്നു. ഒരേ നിരയിൽ രണ്ട് രാജ്ഞികൾ വരില്ലെന്നോർക്കുക.

N രാജ്ഞിയുടെ പ്രശ്നം

നാലാമത്തെ രാജ്ഞിയെ സുരക്ഷിത മേഖലയിൽ സൂക്ഷിക്കുന്നതിനുള്ള ഒരു ഓപ്ഷൻ ഞങ്ങൾക്ക് ഇല്ലെന്ന് ഇവിടെ ഞങ്ങൾ കാണുന്നു. (4) ലെ 1 രാജ്ഞിക്കായി, സാധ്യമായ എല്ലാ കേസുകളും ഞങ്ങൾ പരിശോധിക്കുന്നു, പക്ഷേ ഇപ്പോഴും ഞങ്ങളുടെ പരിഹാരം ലഭിക്കുന്നില്ല. അതിനാൽ, ഞങ്ങൾ N രാജ്ഞികളെ സ്ഥാപിക്കുന്ന അവസ്ഥയിൽ ഒന്നാം രാജ്ഞിയുടെ സ്ഥാനം (1,1), രണ്ടാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (1) എന്നിവയിലേക്ക് മാറ്റുക. അപ്പോൾ സാധ്യമായ ഒരു മാർഗം:

ഇപ്പോൾ, രണ്ടാമത്തെ രാജ്ഞി ആക്രമണത്തിലാണെന്ന് ഞങ്ങൾ കാണുന്നു, തുടർന്ന് രണ്ടാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (2) ആക്കി മാറ്റുന്നു. ഒരേ നിരയിൽ‌ പുതിയ രണ്ട് രാജ്ഞികൾ‌ അതിനാൽ‌ ഞങ്ങൾ‌ നാലാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (2) ആക്കി മാറ്റുന്നു.

ഈ സാഹചര്യത്തിൽ, മൂന്നാം രാജ്ഞി ആക്രമണാവസ്ഥയിലാണ്, അതിനാൽ ഞങ്ങൾ രണ്ടാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (3) ആക്കി മാറ്റുന്നു. ഒരേ നിരയിൽ‌ പുതിയ രണ്ട് രാജ്ഞികൾ‌ അതിനാൽ‌ ഞങ്ങൾ‌ നാലാമത്തെ രാജ്ഞിയുടെ സ്ഥാനം (2) ആക്കി മാറ്റുന്നു.

ഈ സാഹചര്യത്തിൽ ഒരു രാജ്ഞിയും ആക്രമണാവസ്ഥയിലല്ല, അതിനാൽ ഞങ്ങൾ നേരിട്ട് ഉത്തരം അച്ചടിക്കുന്നു. ഒരു സെല്ലിൽ‌ രാജ്ഞി ഉള്ളിടത്ത് ഞങ്ങൾ‌ 1 അല്ലെങ്കിൽ‌ 0 അച്ചടിക്കുന്നു. ഈ ഉദാഹരണത്തിന് ഇൻ‌പുട്ട് / output ട്ട്‌പുട്ട് ഫോർ‌മാറ്റ് കാണുക.

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

എൻ‌ രാജ്ഞി പ്രശ്‌നത്തിനായി അൽ‌ഗോരിതം ഉപയോഗിച്ചു

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.

എൻ രാജ്ഞി പ്രശ്നത്തിന് നടപ്പിലാക്കൽ

/*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 

സമയ സങ്കീർണ്ണത

O (N * N * N) ഓരോ രാജ്ഞിയുടെയും സ്ഥാനത്തിന് ശേഷം ക്യൂവിന്റെ സാധുവായ സ്ഥാനം പരിശോധിക്കുന്നതിനായി N * N ചെസ്സ്ബോർഡിലും O (N) സമയത്തിലും ഓരോ രാജ്ഞിയുടെയും സാധുവായ സ്ഥാനം പരിശോധിക്കുമ്പോൾ ഇത് പരമാവധി സാധ്യമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N * N) ഇവിടെ N എന്നത് ചെസ്സ് ബോർഡിന്റെ ഒരു വശമാണ്. ഓരോ രാജ്ഞിയുടെയും സാധുവായ സ്ഥാനം കണ്ടെത്തുന്നതിനുള്ള പ്രവർത്തനം നടത്താൻ രാജ്ഞിയുടെ സ്ഥാനം സംഭരിക്കാൻ ഞങ്ങൾ ഒരു N * N മാട്രിക്സ് ഉപയോഗിക്കുന്നു.

അവലംബം