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;
  }
}

Sort:

Trending

[-]

minnowsupporter (57) 6 years ago

Resteemed by @minnowsupporter . Check on @minnowsupporter to know how i can support you

$0.28

2 votes

resteembot (48) 6 years ago

Resteemed by @resteembot! Good Luck!
The resteem was paid by @marcocasario
Check @resteembot's introduction post or the other great posts I already resteemed.

$0.00

abasinkanga (61) 6 years ago

@smartbot tip 1

Your post has been resteemed. Thanks for using my resteem service
Get more rewards in my discord server

smartbot (57) 6 years ago

Σ$$$ Tipped @gaottantacinque Σ1 SMART! Comment @smartbot help to claim. Currently the price of SmartCash in the market is $0.027 USD per SMART. Current value of the tip is $0.03 USD. To find out more about SmartCash, please visit @smartcash.

$0.29

4 votes

resteemr (50) 6 years ago

This post was upvoted and resteemed by @resteemr!
Thank you for using @resteemr.

@resteemr is a low price resteem service.
Check what @resteemr can do for you. Introduction of resteemr.