View difference between Paste ID: fa3Rt21q and

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