1
\$\begingroup\$

I have a version of the N-Queens problem in Java. I have function that returns the column placement for each row. And another function that takes that and translates it to a board with '.' representing blanks and 'Q' representing the queens. I was hoping to get an opinion on this.

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<Deque<Integer>> result = this.nQueens(n);
        //String[] board = new String[n];
        //Arrays.fill(board, defaultRow);
        List<List<String>> resultAsStr = new ArrayList<List<String>>();
        for (Deque<Integer> variation: result){
            String[] board = new String[n];
            Integer[] temp = variation.toArray(new Integer[0]);
            for (int row=0;row<variation.size();++row){
                char[] currRow = new char[n];
                Arrays.fill(currRow, '.');
                Integer col = temp[row];
                currRow[col] = 'Q';
                board[row] = new String(currRow);                
            }
            resultAsStr.add(new ArrayList<String>(Arrays.asList(board)));
        }


        return resultAsStr;

    }

    private List<Deque<Integer>> nQueens(int n){
        List<Deque<Integer>> result = new ArrayList<Deque<Integer>>();
        Deque<Integer> colPlacement = new ArrayDeque<Integer>();
        this.nQueens(n, 0, colPlacement, result);
        return result;
    }

    private void nQueens(int n, int row, Deque<Integer> colPlacement, List<Deque<Integer>> result){
        if (n==row){
            result.add(new ArrayDeque<Integer>(colPlacement));
        } else {

            for (int col=0;col<n;++col){
                colPlacement.add(col);
                if (this.isValid(colPlacement)){
                    this.nQueens(n, row+1, colPlacement, result);
                }
                colPlacement.pollLast();
            }
        }
    }

    private boolean isValid(Deque<Integer> colPlacement){
        int row_id = colPlacement.size() -1;
        Integer[] colArray = colPlacement.toArray(new Integer[0]);
        for (int i=0;i<row_id;++i){
            int diff = Math.abs(colArray[i] - colArray[row_id]);
            if (diff == 0 || diff == row_id -i){
                return false;
            }
        }
        return true;
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Documenting the parameters and return values of the functions would really help here. It's hard to guess what a List<List<String>> represents in this context. \$\endgroup\$ – feersum Apr 13 '17 at 5:01
1
\$\begingroup\$

Like @feersum mentioned in a comment, it's not clear what exactly you return. I had to go through the entire implementation before I found out. You either need to explain it in a comment, or choose a more intuitive representation. Another thing that might help is the name of your methods (and class).

If for example you had the following method signature:

public class NQueensSolver {
    public static List<char[][]> findAllSolutions(int n){

You expect a list of all the possible boards. Where each board is represented by a grid of char.

Your method SolveNQueens could mean find all solutions, or just find 1. If it's just 1, it might mean you get a list of rows, containing a list of strings, each representing a single cell. The fact that we can interpret the return type like this makes it really confusing what is actually returned.

Your initial idea of using String[] might have worked slightly better even. Since then you could guess that a String is an entire row, and the [] combines the rows into an entire board. Then the List is more easily interpreted as a list of all solutions.


I prefer to decouple finding a solution with how to show it to the user. Since NQueens is a rather small problem, we can just stick with 1 class and have it provide both a method to solve the NQueens and another one to print it. No need to write a specific class to show the solution. (Except if you want to show it graphically for example).

The class will look something like this:

public class NQueensSolver {
    public static SOLUTIONS findAllSolutions(int n) {...}
    public static void printSolutions(SOLUTIONS solutions) {...}
}

The methods are static because we don't keep any state inside the class. All state for a solution is either inside the method or passed in via parameters.

Now let's look at what return type fits for the SOLUTIONS.
I'd say there are 2 ways to look at the problem. Depending on how you look at it you'll use a different representation.

1) You want to find for each cell of the board whether or not it contains a queen.
2) For each row, you want to find in what column the queen is placed.

For case (1) you probably want to represent it by a boolean[][]. Since [][] means a 2D array of cells. And for each cell you say it contains a queen (true) or not (false). Alternatively you could also use a char and represent it with a . or Q like you did.

For case (2) you need a list of numbers. So either List<Integer> or int[]. This means the solution {1,3,0,2} could be printed as:

. Q . .
. . . Q
Q . . .
. . Q .

Since the way you actually solved it was by using the (2) representation, let's go with that.

Because we're putting all solutions in a List I peronally prefer to use List<int[]> over List<List<Integer>>. But both can work.

So now our method becomes:

/**
* Returns a list with all solutions. Each solution is represented by an array of rows. 
* Where the number says for that row, in which column the queen is placed.
*/
public static List<int[]> findAllSolutions(int n){...}

Notice how I also put a comment above explaining how the solutions are represented.


Let's look at your main solving method:

private void nQueens(int n, int row, Deque<Integer> colPlacement,
                    List<Deque<Integer>> result){

This in itself works fine, but we're going to have to transform our result to List<int[]. So instead let's try to collect our result in the wanted type from the start.

Same for the colPlacement. This is our partial solution, but we can start by reserving exactly n numbers from the start and change those during the search.

This means our new method signature becomes:

private static void solve(int n, int currentRow, int[] currentSolution, 
                          List<int[]> result){ ...}

We also don't really need a separate method to call this.

public static List<int[]> findAllSolutions(int n) {
    List<int[]> resultCollector = new ArrayList<int[]>();
    solve(n, 0, new int[n], resultCollector);
    return resultCollector;
}

A minor things to note here: new int[n] initialises the array to all 0. Otherwise we would have had use the Arrays.fill() like you already did for the .s.

Before we go to the solve(...) implementation, let's first look at the isValid(...) method.

Since we no longer work with Deque the signature is going to change to take an int[] partialSolution instead. But we can't do partialSolution.lenght (instead of deque.size()) anymore to find out what row we want to check. So let's also pass int currentRow as a parameter.

private static boolean isValid(int[] partialSolution, int currentRow){
    for (int i = 0 ; i < currentRow ; i++){
        int diff = Math.abs(partialSolution[i] - partialSolution[currentRow]);
        if (diff == 0 || diff == currentRow-i){
            return false;
        }
    }
    return true;
}

Note that i changed the ++i inside the for to i++. This is what people usually write.

Now let's look at what needs to change in the solve method.

private static void solve(int n, int currentRow, int[] currentSolution, 
                          List<int[]> result){ 
    if(n == currentRow){
        result.add(Arrays.copyOf(currentSolution,n));
        return;
    }

    for(int col=0 ; col < n ; col++){
        currentSolution[currentRow] = col;
        if(isValid(currentSolution, currentRow)){
           solve(n, row+1, currentSolution, result);
        }
    }
}

We still need to make a copy when adding the solution to the result. Only now it's a copy of an array.
I added the return; inside the if, so we don't need the explicit else anymore which saves us a level of indentation.
Instead of adding the new column number to the Deque, we just set it in it's place in the solution array.
And don't forget to also pass the currentRow to the new isValid method call.


All that's left is to write the printSolutions() method so we can actually see the solutions. These are just some simple loops:

public static void printSolutions(List<int[]> solutions){
    for(int[] solution : solutions){
        for(int row = 0; row < solution.length; row++){
            for(int col = 0; col < solution.length; col++){
                if(solution[row]==col){
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
        System.out.println();
    }
}

Running this simple main method shows that everthing works (given no copy-paste mistakes):

public static void main(String[] args) throws Exception {
    printSolutions(findAllSolutions(4));
}

. Q . . 
. . . Q 
Q . . . 
. . Q . 


. . Q . 
Q . . . 
. . . Q 
. Q . . 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.