NQueens.java

Download 
1/*2 * NQueens.java3 *4 * Computer Science S-22, Harvard University5 */6 7import java.util.*;8 9/** 10 * NQueens - blueprint class for an object that solves the n-queens puzzle 11 * using recursive backtracking. Includes a main() method for using the solver.12 */13public class NQueens {   14    private boolean[][] board;          // 2-D array that keeps track of which15                                        // squares on the board are occupied16    private boolean[] colEmpty;         // keeps track of empty columns17    private boolean[] upDiagEmpty;      // keeps track of empty up-diagonals18    private boolean[] downDiagEmpty;    // keeps track of empty down-diagonals19        20    /** 21     * Constructor - initializes the state of a chess board22     * with the specified boardSize23     */24    public NQueens(int n) {25        this.board = new boolean[n][n];  // initially all false26        this.colEmpty = new boolean[n];27        this.upDiagEmpty = new boolean[2*n - 1];28        this.downDiagEmpty = new boolean[2*n - 1];29        30        /* 31         * set the entries in the the extra bookkeeping arrays to true,32         * since initially everything is empty33         */34        for (int i = 0; i < 2*n - 1; i++) {35            if (i < n) {36                this.colEmpty[i] = true;37            }38            this.upDiagEmpty[i] = true;39            this.downDiagEmpty[i] = true;40        }41    }42    43    /*44     * placeQueen - place a queen at the specified row and column;45     * a private helper method, so we don't need to perform error-checking!46     */47    private void placeQueen(int row, int col) {48        this.board[row][col] = true;49        this.colEmpty[col] = false;50        this.upDiagEmpty[row + col] = false;51        this.downDiagEmpty[(this.board.length - 1) + row - col] = false;52    }53    54    /*55     * removeQueen - remove the queen at the specified row and column;56     * a private helper method, so we don't need to perform error-checking!57     */58    private void removeQueen(int row, int col) {59        this.board[row][col] = false;60        this.colEmpty[col] = true;61        this.upDiagEmpty[row + col] = true;62        this.downDiagEmpty[(this.board.length - 1) + row - col] = true;63    }64    65    /*66     * isSafe - returns true if it is safe to place a queen at the67     * specified square, and false otherwise;68     * a private helper method, so we don't need to perform error-checking!69     */70    private boolean isSafe(int row, int col) {71        return (this.colEmpty[col] && 72                this.upDiagEmpty[row + col]&& 73                this.downDiagEmpty[(this.board.length - 1) + row - col]); 74    }75    76    /*77     * findSolution(int row) - recursive function to search for solutions.78     * Tries to find a safe column in the specified row.79     * If it finds one, it makes a recursive call to handle the next row.80     * If it can't find one, it backtracks by returning from the81     * recursive call.82     * a private helper method, so we don't need to perform error-checking!83     */84    private boolean findSolution(int row) {85        if (row == this.board.length) {  // base case: a solution!86            this.displayBoard();87            return true;88        } 89        90        // Try each column in the current row.91        for (int col = 0; col < this.board.length; col++) {92            if (this.isSafe(row, col)) {93                this.placeQueen(row, col);94                95                // Move onto the next row by making a recursive call.96                // If the call returns true, we've already found the solution,97                // so we just keep returning true. Otherwise, we pick up 98                // where we left off in the current row.99                if (this.findSolution(row + 1)) {100                    return true;101                }102                103                // If we get here, we've backtracked.104                this.removeQueen(row, col);105            }106        }107        108        return false;    // tried all columns in this row, so backtrack!109    }         110    111    /*112     * findSolution() -  public "wrapper" method that takes no parameters.113     * Makes the initial call to the private recursive-backtracking method,114     * and returns whatever it returns.115     * 116     * This is an example of method *overloading* -- since we have two methods 117     * with the same name but different parameter lists.118     */119    public boolean findSolution() {120        boolean foundSol = this.findSolution(0);121        return foundSol;122    }123    124    /**125     * displayBoard - display the current state of the board126     */127    public void displayBoard() {128        // print column indices129        System.out.print("  ");130        for (int c = 0; c < this.board.length; c++) {131            System.out.print(" " + (c % 10));132        }133        System.out.println();134        135        // print the contents of the board136        for (int r = 0; r < this.board.length; r++) {137            System.out.print(" " + (r % 10));   // row index138            for (int c = 0; c < this.board.length; c++) {139                if (this.board[r][c]) {140                    System.out.print(" Q");141                } else {142                    System.out.print("  ");143                }144            }145            System.out.println();146        }147    }148    149    public static void main(String[] args) {150        Scanner console = new Scanner(System.in);151        System.out.print("What is the dimension of the board? ");152        int n= console.nextInt();153        154        NQueens solver = new NQueens(n);155        boolean foundSol = solver.findSolution();156        if (!foundSol) {157            System.out.println("Failed to find a solution!");158        }159    }160}