Title: N-Queens Source: leetcode.com
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
image source: leetcode.com
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
|
1 2 3 4 5 6 7 8 9 10 11 |
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] |
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
/* https://leetcode.com/problems/n-queens/ */ class NQueens { private static final int N = 8; private int[][] board; public NQueens() { board = new int[N][N]; } public static void main(String args[]) { NQueens n = new NQueens(); for(int i=0;i<N;i++) { n.solve(i,8); n.clearBoard(); } } public boolean isSafe(int x, int y) { if(isSafeRow(x, y) && isSafeUpperDiagonal(x, y) && isSafeLowerDiagonal(x, y)) return true; return false; } private boolean isSafeRow(int r, int c) { for(int i=0;i<N;i++) { if(board[r][i]==1) return false; } return true; } //NorthWest diagonal private boolean isSafeUpperDiagonal(int r, int c) { for(int row=r, col=c; row>=0 && col>=0;row--, col--) { if(board[row][col]==1) return false; } return true; } //SouthWest Diagonal private boolean isSafeLowerDiagonal(int r, int c) { for(int row=r, col=c;col>=0 && row<N;row++,col--) { if(board[row][col]==1) return false; } return true; } public boolean solve(int col, int count) { if(count==0) { printBoard(); //clearBoard(); return true; } for(int row = 0;row<N;row++) { if(isSafe(row, col)) { board[row][col] = 1; if(solve((col+1)%N, count-1)) return true; board[row][col] = 0; //return false; } } return false; } public void printBoard() { for(int[] row: board) { for(int col: row) { System.out.print(col+" "); } System.out.println(); } System.out.println(); } public void clearBoard() { board = new int[N][N]; } } |