import java.util.Random; /** * A recursive solver for the N Queens problem * * @author gtowell * Created: April 2, 2021 * Modified: Oct 23, 2021 * **/ public class NQueens { /** * Create a new N Quees chessboard * @param size the size of the board to be created (8 is normal) * @param initial the number of queens to put onto the board * @return the board so created. */ private char[][] newBoard(int size, int initial) { char[][] board = new char[size][size]; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { board[i][j] = '.'; } } Random r = new Random(); for (int i = 0; i < initial; i++) { int row = r.nextInt(size); int col = r.nextInt(size); board[row][col] = 'A'; } return board; } /** * Start solving. * Just call the internal recursive solver. * @param board the initial board to solve * @return the solution, or null is no solution */ public char[][] doQueens(char[][] board) { return doQueensUtil(board, 0); } /** * return the numbe rof queens in the column * @param cc the column to be checked * @return the numbe rof queens in the column */ private int checkCol(char[][] board, int cc) { int fc = 0; for (int row = 0; row < board.length; row++) { if (board[row][cc] == 'Q' || board[row][cc] == 'A') fc++; } return fc; } /** * Check a diagonal * Works from row 0 down to size -1, going down one row at a time * @param strt the starting column number. Note that this may be off of the board * @param ci the direction to move ... columnwise (+1 or -1) * @return the number of quees on the diagonal */ int checkDiag(char[][] board, int strt, int ci) { int fc = 0; int row = 0; int col = strt; for (int i = 0; i < board.length; i++) { if (col >= 0 && col < board.length) { if (board[row][col] == 'Q' || board[row][col] == 'A') fc++; } row++; col += ci; } return fc; } /** * Return true iff the board is legal. That is, if no queen and take another * @return true iff the board is legal */ private boolean OKBoard(char[][]board) { for (int c = 0; c < board.length; c++) { boolean badCol = checkCol(board, c) > 1; if (badCol) return false; } for (int d = -board.length; d < board.length; d++) { boolean baddiag = checkDiag(board, d, 1) > 1; if (baddiag) return false; } for (int d = 0; d < board.length * 2; d++) { boolean baddiag = checkDiag(board, d, -1) > 1; if (baddiag) return false; } return true; } /** * Return true if there already is a queen in the row. This will only be true due to the * initial, randomly placed queen. * @param row * @return */ private boolean rowOccupied(char[][] board, int row) { for (int c = 0; c < board.length; c++) { if (board[row][c] == 'Q' || board[row][c] == 'A') return true; } return false; } /** * Copy the chess board and add a queen to the copy * @param oldBoard the board to be copied * @param qRow row for the new queen * @param qCol col for the new qieen * @return the new board */ private char[][] copyBoard(char[][] oldBoard, int qRow, int qCol) { char[][] board = new char[oldBoard.length][oldBoard[0].length]; for (int r = 0; r < oldBoard.length; r++) { for (int c = 0; c < oldBoard[r].length; c++) { board[r][c] = oldBoard[r][c]; } } board[qRow][qCol] = 'Q'; return board; } /** * The recursaive solver. This works by starting with the top row. * In that row work across the columns, recursing on a copy of the * bioard with a queen put in the column * @param board the current board * @param cc the row to work with * @return true if a solution has been found. false otherwise */ private char[][] doQueensUtil(char[][] board, int roww) { if (roww >= board.length) return board; if (rowOccupied(board, roww)) return doQueensUtil(board, roww + 1); for (int col = 0; col < board[roww].length; col++) { if (OKBoard(board)) { // recurse; going to the next row. char[][] v = doQueensUtil(copyBoard(board, roww, col), roww + 1); if (v!=null) return v; } else { //System.out.println("NOT OK"); //showBoard(board); //System.out.println("NOT OK" + roww + " " + col); } } return null; } public void showBoard(char[][] board) { for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[r].length; c++) { System.out.print(board[r][c]); } System.out.print("\n"); } } public static void main(String[] args) { NQueens nq = new NQueens(); char[][] startBoard = nq.newBoard(8, 2); char[][] rslt = nq.doQueens(startBoard); if (rslt != null) { System.out.println("SOLVED!!!!"); nq.showBoard(rslt); } else { System.out.println("NO Solution"); nq.showBoard(startBoard); } } }