package edu.mit.yingyin.util;

import java.util.ArrayList;
import java.util.Arrays;

public class NQueens {

  private int size;
  private int[][] board;
  /**
   * 4 diagonal directions.
   */
  private int[] dr = {-1, -1, 1, 1};
  private int[] dc = {-1, 1, 1, -1};
  private ArrayList<int[]> solutions = new ArrayList<int[]>();
  
  public NQueens(int size) {
    this.size = size;
    board = new int[size][size];
    for (int i = 0; i < size; i++)
      Arrays.fill(board[i], 0);
  }
  
  /**
   * An implementation that marks -1 on the board for positions that are not 
   * possible after placing a queen. This is more efficient because subsequent
   * recursive calls only need to check the mark at a particular position 
   * without iteration. It requires more memory however because it needs to 
   * create a new copy of the board at each recursion level so that we can 
   * easily undo the marking.
   * 
   * @return all the solutions.
   */
  public ArrayList<int[]> solveWithMarking() {
    solutions.clear();
    solve1WithMarking(0, board);
    return solutions;
  }

  /**
   * An implementation that does not mark out invalid positions. Subsequence 
   * placement of a queen needs to check conflicts iteratively.
   * 
   * @return all the solutions.
   */
  public ArrayList<int[]> solveWithoutMarking() {
    solutions.clear();
    solve1WithoutMarking(0);
    return solutions;
  }
  
  
  public void printBoard(int[][] tmpBoard) {
    for (int r = 0; r < size; r++) {
      for (int c = 0; c < size; c++) {
        System.out.print(String.format("%+d ", tmpBoard[r][c]));
      }
      System.out.println();
    }
    System.out.println();
  }

  public int[][] getBoard() {
    return board;
  }

  /**
   * Solves one particular row with marking.
   * @param row
   * @param tmpBoard
   */
  private void solve1WithMarking(int row, int[][] tmpBoard) {
    if (row == size) {
      addSolutions(tmpBoard);
      return;
    }
    
    for (int c = 0; c < size; c++) {
      if (tmpBoard[row][c] == 0) {
        int[][] newBoard = copyBoard(tmpBoard);
        markBoard(row, c, newBoard);
        solve1WithMarking(row + 1, newBoard);
      }
    }
  }
  
  /**
   * Creates a deep copy of the current temporary board.
   * @param tmpBoard
   * @return
   */
  private int[][] copyBoard(int[][] tmpBoard) {
    int[][] newBoard = new int[size][size];
    for (int i = 0; i < size; i++)
      System.arraycopy(tmpBoard[i], 0, newBoard[i], 0, size);
    return newBoard;
  }
  
  
  /**
   * Marks a copy of the board with -1 at positions that are in conflict with 
   * position (row, col). 
   * 
   * @param row
   * @param col
   * @param tmpBoard
   */
  private void markBoard(int row, int col, int[][] tmpBoard) {
    for (int i = 0; i < size; i++) {
      tmpBoard[row][i] = -1;
      tmpBoard[i][col] = -1;
    }
    for (int i = 0; i < 4; i++) {
      int nrow = row;
      int ncol = col;
      while (true) {
        nrow += dr[i];
        ncol +=  dc[i];
        if (nrow >= 0 && nrow < size && ncol >= 0 && ncol < size) 
          tmpBoard[nrow][ncol] = -1;
        else break;
      }
    }
    tmpBoard[row][col] = 1;
  }
  
  private void solve1WithoutMarking(int row) {
    if (row == size) {
      addSolutions(board);
      return;
    }
    
    for (int c = 0; c < size; c++) {
      if (board[row][c] == 0 && isRowColSafe(row, c, board) && 
          isDiagSafe(row, c, board)) {
        board[row][c] = 1;
        solve1WithoutMarking(row + 1);
        board[row][c] = 0;
      }
    }
  }
  
  private boolean isRowColSafe(int row, int col, int[][] b) {
    for (int i = 0; i < size; i++) {
      if (b[row][i] == 1 && i != col || b[i][col] == 1 && i != row)
        return false;
    }
    return true;
  }
  
  private boolean isDiagSafe(int row, int col, int[][] b) {
    for (int i = 0; i < 4; i++) {
      int nrow = row;
      int ncol = col;
      while (true) {
        nrow += dr[i];
        ncol +=  dc[i];
        if (nrow >= 0 && nrow < size && ncol >= 0 && ncol < size) {
          if (b[nrow][ncol] == 1)
            return false;
        } else break;
      }
    }
    return true;
  }
  
  private void addSolutions(int[][] b) {
    int[] sol = new int[size];
    for (int r = 0; r < size; r++ ) {
      for (int c = 0; c < size; c++) {
        if (b[r][c] == 1) {
          sol[r] = c + 1;
          break;
        }
      }
    }
    solutions.add(sol);
  }
}