import java.util.Random; /** * A recursive solver for the N Queens problem * * @author gtowell * Created: April 2, 2021 * **/ public class NQueens { // The board on which queens will be put private char[][] board; // the size of the board private int size = 0; /** * Constructor. Initialized the board * The board is an array of chars. * . means it has never been tried, * Q means a queen is there * - means it was tried at least once and rejected. * A a part of initialization, put a queen on a random square. * @param siz the size of the problem */ public NQueens(int siz) { size = siz; board = new char[siz][siz]; for (int i = 0; i < siz; i++) { for (int j = 0; j < siz; j++) { board[i][j] = '.'; } } Random r = new Random(); int row = r.nextInt(size); int col = r.nextInt(size); board[row][col] = 'Q'; } /** * Start solving. * Just call the internal recursive solver. */ public void doQueens() { doQueensUtil(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(int cc) { int fc = 0; for (int row = 0; row < size; row++) { if (board[row][cc] == 'Q') 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(int strt, int ci) { int fc = 0; int row = 0; int col = strt; for (int i = 0; i < size; i++) { if (col >= 0 && col < size) { if (board[row][col] == 'Q') 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() { for (int c = 0; c < size; c++) { boolean badCol = checkCol(c) > 1; if (badCol) return false; } for (int d = -size; d < size; d++) { boolean baddiag = checkDiag(d, 1) > 1; if (baddiag) return false; } for (int d = 0; d < size * 2; d++) { boolean baddiag = checkDiag(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(int row) { for (int c = 0; c < size; c++) { if (board[row][c] == 'Q') return true; } return false; } /** * The recursaive solver. This works by starting with the top row. * In that row work across the columns, placing a queen and recursing.If get back a bad, pick up the queen and move it one column * over. In this way will eventually check every * position in a row. * @param cc the row to work with * @return true if a solution has been found. false otherwise */ private boolean doQueensUtil(int roww) { if (roww >= size) return true; if (rowOccupied(roww)) return doQueensUtil(roww + 1); for (int col = 0; col < size; col++) { board[roww][col] = 'Q'; if (OKBoard()) { boolean v = doQueensUtil(roww + 1); if (v) return true; } else { System.out.println("NOT OK"); showBoard(); System.out.println("NOT OK" + roww + " " + col); } board[roww][col] = '-'; } return false; } public void showBoard() { for (int r = 0; r < size; r++) { for (int c = 0; c < size; c++) { System.out.print(board[r][c]); } System.out.print("\n"); } } public static void main(String[] args) { int n = 8; NQueens nq = new NQueens(n); nq.doQueens(); nq.showBoard(); } }