51. N-Queens


  • 0
    C

    Approach #1 Use BFS [Accepted]

    We can use the BFS( Broad First Search) method to solve the problem. From the first row, we consider every possible position and search the next row recursively. In each row we exclude the positions that are illegal, so the search paths will be reduced rapidly.

    Java

    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> re = new ArrayList<>();
            int[] pos = new int[n];
            for(int i=0; i<n; i++){
                pos[0] = i;
                judgePos(re, pos, 1, n);
            }
            return re;
        }
        /*
         *  @param re : the list to store the result
         *  @param index : current row index
         *  @param pos : the array recording the used positions each row, from pos[0] to pos[index-1]
         *  @param n : the limit of index
        */
        public void judgePos(List<List<String>> re, int[] pos, int index, int n){
            if(index == n) {
                re.add(generateString(pos));
                return;
            }
            boolean[] wrongCells = new boolean[n]; // cells that cannot be used int current row;
            for(int i=0; i<index; i++){ // the same column or diagonal
                wrongCells[pos[i]] = true;
                if(pos[i] + index - i < n) wrongCells[pos[i] + index - i] = true;
                if(pos[i] + i - index >= 0) wrongCells[pos[i] + i - index] = true;
            }
            for(int i=0; i<n; i++){
                if(!wrongCells[i]){
                    pos[index] = i;
                    judgePos(re, pos, index + 1, n);
                }
            }
        }
    
        /*
         *  Generate the map for a success solution;
        */
        public List<String> generateString(int[] pos){
            char[] template = new char[pos.length];
            Arrays.fill(template, '.');
            List<String> re = new ArrayList<>(pos.length);
            for(int num : pos){
                template[num] = 'Q';
                re.add(String.valueOf(template));
                template[num] = '.';
            }
            return re;
        }
    }
    

    Complex Analysis

    • Time complexity : O(n^n). We trim the search paths, so the actual time cost would be much less than O(n^n).
    • Space complexity : O(n). We use an array to record the used positions, and an array to help judge positions whether can be used in each row.

  • 0
    M

    Here in this solution i am using backtracking approach. In this problem we have to place a queens if possible in each row such that it is at safe position.
    safe position here means:

    1. there is no other queen in that same row
    2. there is no other queen in that same coloumn.
    3. there is no other queen present diagnoaly corresponding to the current position.

    for checking these three things i have made a funciton issafe();
    and for solving the main problem recursively(using backtracking) i have made a solve function.

    #include<bits/stdc++.h>
    using namespace std;
    int ar[11][11];
     int n;
    
     bool issafe(int row,int col)
     {
        // coloumn check
        int count=0;
          for(int k=0;k<row;k++)
               if(ar[k][col]==1)
                return false;
    
    
      //upper right diagnoal 
      int k=row; int l=col;
        while(k>=0&&l<n){
           if(ar[k][l]==1)
             return false;
         k--; l++;    
        }
    
     //upper left diagnoal
     k=row; l=col;
     while(k>=0&&l>=0)
     {
         if(ar[k][l]==1)
             return false;
     k--; l--;
     }
    
     return true;
     }
    
    bool solve(int row)
    {
      if(row>=n)
        return true;
    
         for(int i=0;i<n;i++)
         {
            if(issafe(row,i))
              {ar[row][i]=1;
                if(solve(row+1))
                 return true;
                 ar[row][i]=0;
               }
          }
          return false;
    
    }
    void print1()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<ar[i][j]<<" ";
            }
            cout<<endl;
        }
    
    
    }
    
    
    main()
    {
    
     cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
         ar[i][j]=0;
    
    if(solve(0))
        print1();
    else
        cout<<"Not possible";
    
    
    
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.