Leetcode 51. N-Queens

2019-11-08 02:32:34

字體：大中小

供稿：網(wǎng)友

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

解題思路：深度優(yōu)先搜索，進(jìn)行遍歷，若當(dāng)前位置可以放“皇后”，則對(duì)下一行的位置進(jìn)行遍歷。下面給出代碼：

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; }//通過(guò)recorder 的記錄給出其中一個(gè)可能的棋盤(pán)擺放結(jié)果 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); } } }}

這里寫(xiě)圖片描述