This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 25th, 2011  |  syntax: Java  |  size: 4.50 KB  |  views: 52  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data