Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement