Guest User

Untitled

a guest
Sep 25th, 2011
69
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package edu.mit.yingyin.util;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5.  
  6. public class NQueens {
  7.  
  8.   private int size;
  9.   private int[][] board;
  10.   /**
  11.    * 4 diagonal directions.
  12.    */
  13.   private int[] dr = {-1, -1, 1, 1};
  14.   private int[] dc = {-1, 1, 1, -1};
  15.   private ArrayList<int[]> solutions = new ArrayList<int[]>();
  16.  
  17.   public NQueens(int size) {
  18.     this.size = size;
  19.     board = new int[size][size];
  20.     for (int i = 0; i < size; i++)
  21.       Arrays.fill(board[i], 0);
  22.   }
  23.  
  24.   /**
  25.    * An implementation that marks -1 on the board for positions that are not
  26.    * possible after placing a queen. This is more efficient because subsequent
  27.    * recursive calls only need to check the mark at a particular position
  28.    * without iteration. It requires more memory however because it needs to
  29.    * create a new copy of the board at each recursion level so that we can
  30.    * easily undo the marking.
  31.    *
  32.    * @return all the solutions.
  33.    */
  34.   public ArrayList<int[]> solveWithMarking() {
  35.     solutions.clear();
  36.     solve1WithMarking(0, board);
  37.     return solutions;
  38.   }
  39.  
  40.   /**
  41.    * An implementation that does not mark out invalid positions. Subsequence
  42.    * placement of a queen needs to check conflicts iteratively.
  43.    *
  44.    * @return all the solutions.
  45.    */
  46.   public ArrayList<int[]> solveWithoutMarking() {
  47.     solutions.clear();
  48.     solve1WithoutMarking(0);
  49.     return solutions;
  50.   }
  51.  
  52.  
  53.   public void printBoard(int[][] tmpBoard) {
  54.     for (int r = 0; r < size; r++) {
  55.       for (int c = 0; c < size; c++) {
  56.         System.out.print(String.format("%+d ", tmpBoard[r][c]));
  57.       }
  58.       System.out.println();
  59.     }
  60.     System.out.println();
  61.   }
  62.  
  63.   public int[][] getBoard() {
  64.     return board;
  65.   }
  66.  
  67.   /**
  68.    * Solves one particular row with marking.
  69.    * @param row
  70.    * @param tmpBoard
  71.    */
  72.   private void solve1WithMarking(int row, int[][] tmpBoard) {
  73.     if (row == size) {
  74.       addSolutions(tmpBoard);
  75.       return;
  76.     }
  77.    
  78.     for (int c = 0; c < size; c++) {
  79.       if (tmpBoard[row][c] == 0) {
  80.         int[][] newBoard = copyBoard(tmpBoard);
  81.         markBoard(row, c, newBoard);
  82.         solve1WithMarking(row + 1, newBoard);
  83.       }
  84.     }
  85.   }
  86.  
  87.   /**
  88.    * Creates a deep copy of the current temporary board.
  89.    * @param tmpBoard
  90.    * @return
  91.    */
  92.   private int[][] copyBoard(int[][] tmpBoard) {
  93.     int[][] newBoard = new int[size][size];
  94.     for (int i = 0; i < size; i++)
  95.       System.arraycopy(tmpBoard[i], 0, newBoard[i], 0, size);
  96.     return newBoard;
  97.   }
  98.  
  99.  
  100.   /**
  101.    * Marks a copy of the board with -1 at positions that are in conflict with
  102.    * position (row, col).
  103.    *
  104.    * @param row
  105.    * @param col
  106.    * @param tmpBoard
  107.    */
  108.   private void markBoard(int row, int col, int[][] tmpBoard) {
  109.     for (int i = 0; i < size; i++) {
  110.       tmpBoard[row][i] = -1;
  111.       tmpBoard[i][col] = -1;
  112.     }
  113.     for (int i = 0; i < 4; i++) {
  114.       int nrow = row;
  115.       int ncol = col;
  116.       while (true) {
  117.         nrow += dr[i];
  118.         ncol +=  dc[i];
  119.         if (nrow >= 0 && nrow < size && ncol >= 0 && ncol < size)
  120.           tmpBoard[nrow][ncol] = -1;
  121.         else break;
  122.       }
  123.     }
  124.     tmpBoard[row][col] = 1;
  125.   }
  126.  
  127.   private void solve1WithoutMarking(int row) {
  128.     if (row == size) {
  129.       addSolutions(board);
  130.       return;
  131.     }
  132.    
  133.     for (int c = 0; c < size; c++) {
  134.       if (board[row][c] == 0 && isRowColSafe(row, c, board) &&
  135.           isDiagSafe(row, c, board)) {
  136.         board[row][c] = 1;
  137.         solve1WithoutMarking(row + 1);
  138.         board[row][c] = 0;
  139.       }
  140.     }
  141.   }
  142.  
  143.   private boolean isRowColSafe(int row, int col, int[][] b) {
  144.     for (int i = 0; i < size; i++) {
  145.       if (b[row][i] == 1 && i != col || b[i][col] == 1 && i != row)
  146.         return false;
  147.     }
  148.     return true;
  149.   }
  150.  
  151.   private boolean isDiagSafe(int row, int col, int[][] b) {
  152.     for (int i = 0; i < 4; i++) {
  153.       int nrow = row;
  154.       int ncol = col;
  155.       while (true) {
  156.         nrow += dr[i];
  157.         ncol +=  dc[i];
  158.         if (nrow >= 0 && nrow < size && ncol >= 0 && ncol < size) {
  159.           if (b[nrow][ncol] == 1)
  160.             return false;
  161.         } else break;
  162.       }
  163.     }
  164.     return true;
  165.   }
  166.  
  167.   private void addSolutions(int[][] b) {
  168.     int[] sol = new int[size];
  169.     for (int r = 0; r < size; r++ ) {
  170.       for (int c = 0; c < size; c++) {
  171.         if (b[r][c] == 1) {
  172.           sol[r] = c + 1;
  173.           break;
  174.         }
  175.       }
  176.     }
  177.     solutions.add(sol);
  178.   }
  179. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×