JAVA coding problems solved -- The N-Queens Puzzle

Here is the first of a series of coding exercises that I will share with you after solving and testing them.

---

Title: N-Queens Puzzle

Difficulty: hard

You can find the description of the problem here on leetcode.com .

In a nutshell: you have to find all the ways to place N queens on a N×N chess board so that the queens do not attack each other.

Example:
Input: 8
Output: All combinations for 8 queens on a 8x8 chess board

_{wikimedia commons image}

INDEX:

• QUESTIONS
• HINTS _{(to solve it on your own)}
• MY SOLUTION

---

---

QUESTIONS

1. How would you improve it / how would you have solved it instead?

I'm aware that performance wise it's not a great algorithm. Better approaches that could bring to better time complexity are:

• Use of recursion
• Distribution of the workload on multiple threads
  _{(probably makes sense only for big Ns - with a classic chessboard there shouldn't be any significant improvement)}
• Dynamic Programming?

2. How would you have solved it in the worst way possible?

I'll post an example in the comments later on.   : )

---

---

HINTS

Always analyse the properties of the system. Each row need to have one and only one queen. This means that:

• Once you manage to add to a row a queen that does not attack the others, you can stop trying to place a new queen on the same row
• If you find yourself in a situation in which one of the rows is empty you can discard that solution right away

---

---

MY SOLUTION

• On paper:

• Code:

  package leetcode;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  public class NQueens {
    public static void main(String... a) {
        System.out.println(">> " + new Solution().solveNQueens(5));
    }
  }
  
  // (template provided to submit the solution)
  class Solution {
    public List<List<String>> solveNQueens(int n) {
        return new Game().start(n);
    }
  }
  
  class Game {
    int n;
    Character[][] board;
    
    public List<List<String>> start(int n) {
        this.n = n;
        this.board = new Character[n][n];
        return calculateSolutions();
    }
    
    // Algorithm: Last Queen Reposition --- COMPLEXITY: O(N^3)                                   ~ 2√2N*N^2 ?
    // N=1 -> Found 1 solutions in 0.001 seconds
    // N=5 -> Found 10 solutions in 0.006 seconds
    // N=15 -> Found 2279184 solutions in 270.876 seconds (~4.5 mins)
    List<List<String>> calculateSolutions() {
        List<List<String>> solutions = new ArrayList<>();
        List<int[]> queenPositions = new ArrayList<>();
        outer:
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!hasClashes(i, j)) { // ADD QUEEN
                    board[i][j] = 'Q';
                    queenPositions.add(new int[] {i, j});
                    if (i < n - 1) {
                        j = n - 1; // skip the rest of the row
                    } else {
                        saveCurrentSolution(solutions);
                        // CHECK REMAINING positions for this configuration
                        int[] queenPos = getPosOfLastQueenToReplace(queenPositions);
                        if (queenPos != null) { // for N=1
                            i = queenPos[0];
                            j = queenPos[1];
                        }
                    }
                } else { // ADD DOT
                    if (j == n - 1) {
                        // EMPTY LINE. Resume from next position of previous queen.
                        // if (i == 0) break outer; -> (nope, never used)
                        int[] queenPos = getPosOfLastQueenToReplace(queenPositions);
                        if (queenPos == null) break outer; // END - end of line and no queens left
                        i = queenPos[0];
                        j = queenPos[1];
                    }
                }
            }
        }
        return solutions;
    }
    
    int[] removeLastQueen(List<int[]> queenPositions) {
        int[] lqPos = queenPositions.get(queenPositions.size() - 1);
        int lastQueenI = lqPos[0];
        int lastQueenJ = lqPos[1];
        board[lastQueenI][lastQueenJ] = null;
        queenPositions.remove(queenPositions.size() - 1);
        return new int[] { lastQueenI, lastQueenJ };
    }
  
    int[] getPosOfLastQueenToReplace(List<int[]> queenPositions) {
        int[] queenPos = removeLastQueen(queenPositions);
        int lastQueenJ = queenPos[1];
        if (lastQueenJ == n - 1) {
            if (queenPositions.size() == 0) return null;
            queenPos = removeLastQueen(queenPositions);
            lastQueenJ = queenPos[1];
        }
        return queenPos;
    }
    
    void saveCurrentSolution(List<List<String>> solutions) {
        List<String> currentSolution = new ArrayList<>();
        for(Character[] row : Arrays.asList(board)) {
            String rowStr = "";
            for(Character cell : Arrays.asList(row)) {
                rowStr += cell == null ? "." : cell; 
            }
            currentSolution.add(rowStr);
        }
        solutions.add(currentSolution);
    }
  
    boolean hasClashes(int i, int j) {
        return queensOnCross(i, j) || queensOnDiagonal(i, j);
    }
  
    boolean queensOnCross(int i, int j) {
        for (int r = 0; r < n; r++) {
            if (r != i && board[r][j] != null) return true;
        }
        for (int c = 0; c < n; c++) {
            if (c != j && board[i][c] != null) return true;
        }
        return false;
    }
  
    boolean queensOnDiagonal(int i, int j) {
        int r = i - 1, c = j + 1;
        while (r >= 0 && c < n) { // top-right
            if (board[r][c] != null) return true;
            r--;
            c++;
        }
        r = i + 1;
        c = j - 1;
        while (r < n && c >= 0) { // bottom-left
            if (board[r][c] != null) return true;
            r++;
            c--;
        }
        r = i - 1;
        c = j - 1;
        while (r >= 0 && c >= 0) { // top-left
            if (board[r][c] != null) return true;
            r--;
            c--;
        }
        r = i + 1;
        c = j + 1;
        while (r < n && c < n) { // bottom-right
            if (board[r][c] != null) return true;
            r++;
            c++;
        }
        return false;
    }
  }
  

---

---