|
| 1 | +package Backtracking; |
| 2 | + |
| 3 | +import java.util.ArrayList; |
| 4 | +import java.util.List; |
| 5 | + |
| 6 | +/** |
| 7 | + * Problem statement: |
| 8 | + * Given a N x N chess board. Return all arrangements in which N queens can be placed on the board such no two queens attack |
| 9 | + * each other. |
| 10 | + * Ex. N = 6 |
| 11 | + * Solution= There are 4 possible ways |
| 12 | + * Arrangement: 1 |
| 13 | + * ".Q....", |
| 14 | + * "...Q..", |
| 15 | + * ".....Q", |
| 16 | + * "Q.....", |
| 17 | + * "..Q...", |
| 18 | + * "....Q." |
| 19 | + * <p> |
| 20 | + * Arrangement: 2 |
| 21 | + * "..Q...", |
| 22 | + * ".....Q", |
| 23 | + * ".Q....", |
| 24 | + * "....Q.", |
| 25 | + * "Q.....", |
| 26 | + * "...Q.." |
| 27 | + * <p> |
| 28 | + * Arrangement: 3 |
| 29 | + * "...Q..", |
| 30 | + * "Q.....", |
| 31 | + * "....Q.", |
| 32 | + * ".Q....", |
| 33 | + * ".....Q", |
| 34 | + * "..Q..." |
| 35 | + * <p> |
| 36 | + * Arrangement: 4 |
| 37 | + * "....Q.", |
| 38 | + * "..Q...", |
| 39 | + * "Q.....", |
| 40 | + * ".....Q", |
| 41 | + * "...Q..", |
| 42 | + * ".Q...." |
| 43 | + * |
| 44 | + * Solution: |
| 45 | + * Brute Force approach: |
| 46 | + * |
| 47 | + * Generate all possible arrangement to place N queens on N*N board. |
| 48 | + * Check each board if queens are placed safely. |
| 49 | + * If it is safe, include arrangement in solution set. Otherwise ignore it |
| 50 | + * |
| 51 | + * Optimized solution: |
| 52 | + * This can be solved using backtracking in below steps |
| 53 | + * |
| 54 | + * Start with first column and place queen on first row |
| 55 | + * Try placing queen in a row on second column |
| 56 | + * If placing second queen in second column attacks any of the previous queens, change the row in second column |
| 57 | + * otherwise move to next column and try to place next queen |
| 58 | + * In case if there is no rows where a queen can be placed such that it doesn't attack previous queens, then go back to previous column and change row of previous queen. |
| 59 | + * Keep doing this until last queen is not placed safely. |
| 60 | + * If there is no such way then return an empty list as solution |
| 61 | + */ |
| 62 | +public class NQueens { |
| 63 | + |
| 64 | + public static void main(String[] args) { |
| 65 | + placeQueens(1); |
| 66 | + placeQueens(2); |
| 67 | + placeQueens(3); |
| 68 | + placeQueens(4); |
| 69 | + placeQueens(5); |
| 70 | + placeQueens(6); |
| 71 | + } |
| 72 | + |
| 73 | + public static void placeQueens(final int queens) { |
| 74 | + List<List<String>> arrangements = new ArrayList<List<String>>(); |
| 75 | + getSolution(queens, arrangements, new int[queens], 0); |
| 76 | + if (arrangements.isEmpty()) { |
| 77 | + System.out.println("There is no way to place " + queens + " queens on board of size " + queens + "x" + queens); |
| 78 | + } else { |
| 79 | + System.out.println("Arrangement for placing " + queens + " queens"); |
| 80 | + } |
| 81 | + arrangements.forEach(arrangement -> { |
| 82 | + arrangement.forEach(row -> System.out.println(row)); |
| 83 | + System.out.println(); |
| 84 | + }); |
| 85 | + } |
| 86 | + |
| 87 | + /** |
| 88 | + * This is backtracking function which tries to place queen recursively |
| 89 | + * @param boardSize: size of chess board |
| 90 | + * @param solutions: this holds all possible arrangements |
| 91 | + * @param columns: columns[i] = rowId where queen is placed in ith column. |
| 92 | + * @param columnIndex: This is the column in which queen is being placed |
| 93 | + */ |
| 94 | + private static void getSolution(int boardSize, List<List<String>> solutions, int[] columns, int columnIndex) { |
| 95 | + if (columnIndex == boardSize) { |
| 96 | + // this means that all queens have been placed |
| 97 | + List<String> sol = new ArrayList<String>(); |
| 98 | + for (int i = 0; i < boardSize; i++) { |
| 99 | + StringBuilder sb = new StringBuilder(); |
| 100 | + for (int j = 0; j < boardSize; j++) { |
| 101 | + sb.append(j == columns[i] ? "Q" : "."); |
| 102 | + } |
| 103 | + sol.add(sb.toString()); |
| 104 | + } |
| 105 | + solutions.add(sol); |
| 106 | + return; |
| 107 | + } |
| 108 | + |
| 109 | + // This loop tries to place queen in a row one by one |
| 110 | + for (int rowIndex = 0; rowIndex < boardSize; rowIndex++) { |
| 111 | + columns[columnIndex] = rowIndex; |
| 112 | + if (isPlacedCorrectly(columns, rowIndex, columnIndex)) { |
| 113 | + // If queen is placed successfully at rowIndex in column=columnIndex then try placing queen in next column |
| 114 | + getSolution(boardSize, solutions, columns, columnIndex + 1); |
| 115 | + } |
| 116 | + } |
| 117 | + } |
| 118 | + |
| 119 | + /** |
| 120 | + * This function checks if queen can be placed at row = rowIndex in column = columnIndex safely |
| 121 | + * @param columns: columns[i] = rowId where queen is placed in ith column. |
| 122 | + * @param rowIndex: row in which queen has to be placed |
| 123 | + * @param columnIndex: column in which queen is being placed |
| 124 | + * @return true: if queen can be placed safely |
| 125 | + * false: otherwise |
| 126 | + */ |
| 127 | + private static boolean isPlacedCorrectly(int[] columns, int rowIndex, int columnIndex) { |
| 128 | + for (int i = 0; i < columnIndex; i++) { |
| 129 | + int diff = Math.abs(columns[i] - rowIndex); |
| 130 | + if (diff == 0 || columnIndex - i == diff) { |
| 131 | + return false; |
| 132 | + } |
| 133 | + } |
| 134 | + return true; |
| 135 | + } |
| 136 | +} |
0 commit comments