Leetcode 51. N-Queens

2019-11-08 02:32:34

字体：大中小

来源：转载

供稿：网友

Leetcode

51. N-Queens

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..”] ] 原题可以查看 https://leetcode.com/problems/n-queens/?tab=Description

解题思路：深度优先搜索，进行遍历，若当前位置可以放“皇后”，则对下一行的位置进行遍历。下面给出代码：

public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); int[] recorder = new int[n+1]; dfs(1,n,recorder,result); return result; }//通过recorder 的记录给出其中一个可能的棋盘摆放结果 private List<String> generateBlock(int []recorder,int n){ List<String> block = new ArrayList<String>(); for(int i=1;i<=n;i++){ StringBuilder strBuilder = new StringBuilder(); for(int j=1;j<=n;j++){ if(recorder[i]==j){ strBuilder.append("Q"); }else{ strBuilder.append("."); } } block.add(strBuilder.toString()); } return block; }//检查第x行，第y列能否放“皇后” private boolean put(int x,int y,int[]recorder){ for(int i=1;i<x;i++){ int dx = Math.abs(x-i); int dy = Math.abs(y-recorder[i]); if(dx==dy||dy==0) return false; } return true; }//深度搜索 private void dfs(int row,int n,int[]recorder,List<List<String>> result){ if(row>n){ result.add(generateBlock(recorder,n)); return; } for(int i=1;i<=n;i++){ if(put(row,i,recorder)){ recorder[row]=i; dfs(row+1,n,recorder,result); } } }}

这里写图片描述