content: package by.andd3dfx.recursion;
  
  import lombok.AllArgsConstructor;
  import lombok.Data;
  
  /**
   * Place N Queens to NxN board
   * <p>
   * Used Rod Stephens - 'Essential Algorithms' book
   *
   * @see <a href="https://youtu.be/v9kctJiD4KQ">Video solution</a>
   */
  public class EightQueens {
  
      @Data
      @AllArgsConstructor
      public static class Solution {
          private boolean isFound;
          private boolean[][] cellsTaken;
  
          public int[][] prettyPrint() {
              int size = cellsTaken.length;
              int[][] result = new int[size][size];
              for (int i = 0; i < size; i++) {
                  for (int j = 0; j < size; j++) {
                      result[i][j] = cellsTaken[i][j] ? 1 : 0;
                  }
              }
              return result;
          }
      }
  
      public Solution solve(int boardSize) {
          boolean[][] cellsTaken = new boolean[boardSize][boardSize];
          boolean isFound = checkSolution(boardSize, cellsTaken, 0);
  
          return new Solution(isFound, cellsTaken);
      }
  
      private boolean checkSolution(int size, boolean[][] cellsTaken, int queensPositioned) {
          if (!isLegal(size, cellsTaken)) {
              return false;
          }
          if (queensPositioned == size) {
              return true;
          }
  
          for (int row = 0; row < size; row++) {
              for (int col = 0; col < size; col++) {
                  if (!cellsTaken[row][col]) {
                      cellsTaken[row][col] = true;
  
                      if (checkSolution(size, cellsTaken, queensPositioned + 1)) {
                          return true;
                      } else {
                          cellsTaken[row][col] = false;
                      }
                  }
              }
          }
          return false;
      }
  
      boolean isLegal(int size, boolean[][] cellsTaken) {
          for (int i = 0; i < size; i++) {
              for (int j = 0; j < size; j++) {
                  if (cellsTaken[i][j]) {
                      // check rows
                      for (int r = 1; r < size; r++) {
                          if (i + r < size && cellsTaken[i + r][j]) {
                              return false;
                          }
                          if (i - r >= 0 && cellsTaken[i - r][j]) {
                              return false;
                          }
                      }
  
                      // check columns
                      for (int r = 1; r < size; r++) {
                          if (j + r < size && cellsTaken[i][j + r]) {
                              return false;
                          }
                          if (j - r >= 0 && cellsTaken[i][j - r]) {
                              return false;
                          }
                      }
  
                      // check diagonals
                      for (int r = 1; r < size; r++) {
                          if (i + r < size && j + r < size && cellsTaken[i + r][j + r]) {
                              return false;
                          }
                          if (i + r < size && j - r >= 0 && cellsTaken[i + r][j - r]) {
                              return false;
                          }
                          if (i - r >= 0 && j + r < size && cellsTaken[i - r][j + r]) {
                              return false;
                          }
                          if (i - r >= 0 && j - r >= 0 && cellsTaken[i - r][j - r]) {
                              return false;
                          }
                      }
                  }
              }
          }
          return true;
      }
  }
  