he n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
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:
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]Understand the problem:
It is a classic N-queue problem. The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3.
Solution:
This is again a classic permutation and combination problem. So we can still apply the same recursive approach.
Code (Java):
public class Solution { public List<String[]> solveNQueens(int n) { List<String[]> result = new ArrayList<String[]>(); if (n == 0 || n == 2 || n == 3) { return result; } solveNqueensHelper(n, 0, new int[n], result); return result; } private void solveNqueensHelper(int n, int row, int[] cols, List<String[]> result) { if (row == n) { String[] solution = new String[n]; for (int i = 0; i < n; i++) { StringBuilder temp = new StringBuilder(); for (int j = 0; j < n; j++) { if (cols[i] == j) { temp.append('Q'); } else { temp.append('.'); } } solution[i] = temp.toString(); } result.add(solution); return; } for (int j = 0; j < n; j++) { if (isValid(j, row, cols) == true) { cols[row] = j; solveNqueensHelper(n, row + 1, cols, result); } } } private boolean isValid(int col, int row, int[] cols) { for (int i = 0; i < row; i++) { if (col == cols[i] || row - i == Math.abs(col - cols[i])) { return false; } } return true; } }
No comments:
Post a Comment