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

https://upload.wikimedia.org/wikipedia/commons/1/1f/Eight-queens-animation.gifwikimedia 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:

[IMAGE: https://cdn.steemitimages.com/DQmWfrspZRm4n8L4W4jSjgD8twrWtLYQFFgf4R5EthPxsDx/NQueens-notes.png]

• 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> solveNQueens(int n) {
  return new Game().start(n);
  }
  }

  class Game {
  int n;
  Character[][] board;

  public List> 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> calculateSolutions() {
      List> solutions = new ArrayList<>();
      List 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 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 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> solutions) {
      List 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;
  }
  

  }