Simple Java solution


  • 3
    Y

    It's very simple column by column tries with DFS. For each column, try every row; for each try point, check if it is safe. When reached level n, print out.

    List<String[]> list = new ArrayList<String[]>();
    
    public List<String[]> solveNQueens(int n) {
        int[][] b = new int[n][n];
        dfs(b, 0, n);
        return list;
    }
    
    public void dfs(int[][] b, int col, int n)
    {
    	if (col == n)
    	{
            list.add(printS(b, n));
    		return;
    	}
        for (int row = 0; row < n; row ++)
        {
            if (isSafe(b, row, col, n))
            {
                b[row][col] = 1;
                dfs(b, col + 1, n);
                b[row][col] = 0;
            }
        }
    }
    public boolean isSafe(int[][] b, int x, int y, int n)
    {
        for (int i = 0; i < n; i++)
        {
            if (b[x][i] == 1 || b[i][y] == 1)
            {
                return false;
            }
        }
        for (int i = 0; i< n; i ++)
        for (int j = 0; j < n; j++)
        {
            if ((i + j == x + y) &&  b[i][j] == 1)
            {
               return false;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (x-i >=0 && y-i >= 0  &&  b[x-i][y-i] == 1)
            {
               return false;
            }
            if (x+i < n && y+i < n && b[x+i][y+i] == 1)
            {
                return false;
            }
        }
        return true;
    }

  • 0
    A

    I'm doing the same, except i'm doing per row rather than per column. i found this approach would choak when n== 13 or above. my solution passed OJ, but wonder if there's better solution...


  • 3
    S

    the isSafe function can be simplified as below:

    public boolean isSafe (int[][]matrix,  column, int row, int n){
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==row && matrix[i][j]==1) return false;
                if(j==column&& matrix[i][j]==1) return false;
                if((Math.abs(row-i)==Math.abs(column-j))&&(matrix[i][j]==1)) return false;
            }
        }
        return true;
       
    }

  • 0
    L

    I use same idea, but instead of using a two-dimension array, I use an one-dimension array plus a hash set to speed it up. Notice, we can't have two queue in same row or in same queue. So using one-dimension array is enough to express the queue position, every value in the array represent the column of the queue in this row. So if the queue[i] = j; it means queue in ith row is in jth column. Instead of trying every column from 0 ~ n, I use a hash set to store the 0 ~n value, if we set a queue to kth column, we remove k from the set, other queues can only choose column among the rest elements in the set.


  • 0
    L

    you can reduce auxillary space of O(n^2) to O(n) in your dfs function
    instead of doing b[row][col]=1 , do b[row]=col;


  • 0
    I

    I tried 13, it has 73712 solution.


Log in to reply
 

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