本文主要是介绍leetcode：N-Queens 【Java】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、问题描述
The 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:
[[".Q..", // Solution 1"...Q","Q...","..Q."],["..Q.", // Solution 2"Q...","...Q",".Q.."] ]
二、问题分析
1、采用回溯算法；
2、找到一个可行解之后，还需要继续搜索。
三、算法代码
public class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> result = new ArrayList<>();if (n <= 0) return result;char[][] board = new char[n][n];for (char[] row : board) {Arrays.fill(row, '.');}boolean[] col_occupied = new boolean[n];placeQueen(result, board, col_occupied, 0, n);return result;}private void placeQueen(List<List<String>> result, char[][] board, boolean[] col_occupied, int rowNum, int n) {if (rowNum == n) {List<String> list = new ArrayList<String>();for (char[] row : board) {list.add(new String(row));}result.add(list);return;}for (int colNum=0; colNum<n; colNum++) {if (isValid(board, col_occupied, rowNum, colNum, n)){board[rowNum][colNum] = 'Q';col_occupied[colNum] = true;placeQueen(result, board, col_occupied, rowNum+1, n);board[rowNum][colNum] = '.'; //回溯，尝试皇后rowNum的下一个位置col_occupied[colNum] = false;}}}private boolean isValid(char[][]board, boolean[] col_occupied, int row, int col, int n) {if (col_occupied[col]) return false;for (int i=1; row-i>=0 && col-i>=0; i++) {if (board[row-i][col-i] == 'Q') return false;//反对角斜线}for (int i=1; row-i>=0 && col+i<n; i++) {if (board[row-i][col+i] == 'Q') return false;//正对角斜线}return true;}
}这篇关于leetcode：N-Queens 【Java】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
