照例发一下我的java代码吧.很low但是好歹独立解决的. public class Solution { /** * 皇后可以攻击竖着的横着的,左斜线,右斜线的对手. * * @param n * @return */ public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); if (n == 0) return result; Set<Integer> pie = new HashSet<>(); Set<Integer> na = new HashSet<>(); dfs(0,n,pie,na,new HashSet<>(),result,new ArrayList<>()); return result; } private void dfs(int level, int n, Set<Integer> pie, Set<Integer> na,Set<Integer> col,List<List<String>> results, List<String> tempList) { if (level > n - 1) { if (tempList.size() == n){ List<String> result = new ArrayList<>(tempList); results.add(result); } return; } boolean exists = false; // 遍历列 for (int j = 0; j < n; j++) { if (pie.contains(level + j) || na.contains(j - level) || col.contains(j)) {// 会被攻击的位置! continue; } exists = true; pie.add(level + j); na.add(j - level); col.add(j); String temp = getStr(n,j); tempList.add(temp); dfs(level + 1,n,pie,na,col,results,tempList); pie.remove(level + j); na.remove(j - level); col.remove(j); tempList.remove(temp); } if (!exists){ return; } } private String getStr(int n, int j) { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < n; i++) { if (i == j){ stringBuilder.append("Q"); }else stringBuilder.append("."); } return stringBuilder.toString(); } public static void main(String[] args){ Solution solution = new Solution(); System.out.println(solution.solveNQueens(5)); } }

PHP 实现： class Solution { /** * @param Integer $n * @return String[][] */ /** * @var array 结果值 */ public $res = []; /** * @var array 列值 */ public $cols = []; /** * @var array 撇值 */ public $pie = []; /** * @var array 纳值 */ public $na = []; /** * @param $n * @return array */ function solveNQueens($n) { if ($n < 1) return []; $this->queens($n, 0, []); return $this->_generate_result($n); } /** * @param $n 数量 * @param $i 坐标 * @param $curState 结果值 */ function queens($n, $i, $curState) { if ($i == $n) { array_push($this->res, $curState); return; } for ($j = 0; $j < $n; $j++) { if (in_array($j, $this->cols) || in_array($i + $j, $this->pie) || in_array($i - $j + $n, $this->na)) { continue; } array_push($this->cols, $j); array_push($this->pie, $i + $j); array_push($this->na, $i - $j + $n); $curState[$i] = $j; $this->queens($n, $i + 1, $curState); array_pop($this->cols); array_pop($this->pie); array_pop($this->na); } } /** * 拼接结果值 * @param $n 循环的次数 * @return array */ function _generate_result($n) { $ret = []; if (!empty($this->res)) { foreach ($this->res as $v) { for ($i = 0; $i < $n; $i++) { $str = ''; foreach ($v as $val) { if ($val == $i) { $str .= 'Q'; } else { $str .= '.'; } } array_push($ret, $str); } } } return array_chunk($ret, $n); } }

为了简洁而简洁的代码，可读性不好

我觉得虽然网上的那个解法看上去很简洁，但实际开销比作者的更大，一是函数内定义了函数，而是，每次递归调用时都重新生成了数组，这些内部的开销对python 开讲都不小。emmm如果实际用的话我更推荐老师的

感觉体会递归，回溯代码就像练功一样，灵光一闪就打通了，就发现不难了，但这个只能自己体会，光靠看和听不够，得写得分析。贴个c#版本的代码，写得不算好，希望得到指点，谢谢啦 public class Solution { List<IList<string>> returnLt = new List<IList<string>>(); HashSet<int> _lie = new HashSet<int>(); HashSet<int> _pie = new HashSet<int>(); HashSet<int> _na = new HashSet<int>(); Dictionary<int, int> _state = new Dictionary<int, int>(); public IList<IList<string>> SolveNQueens(int n) { Gen(0, n); return returnLt; } void Gen(int row, int n){ if (row == n){ Append(n); return; } for (int i = 0; i < n; i++){ // check if(_lie.Contains(i) || _pie.Contains(row + i) || _na.Contains(row - i)) continue; //store state _lie.Add(i); _pie.Add(row + i); _na.Add(row - i); _state.Add(row, i); Gen(row + 1, n); //reset state _lie.Remove(i); _pie.Remove(row + i); _na.Remove(row - i); _state.Remove(row); } } void Append(int n){ if (_state.Count < n) return; List<string> lt = new List<string>(); for (int i = 0; i < n; i++){ int queenIndex = _state[i]; string str = ""; for (int j = 0; j < n; j++){ str += j == queenIndex ? "Q": "."; } lt.Add(str); } returnLt.Add(lt); } }

想问下老师cur_state在这里有什么用

相当于滚动数组，状态压缩了

为啥分层的遍历就是dfs，难道就是因为使用递归了，不是特别理解为啥要叫DFS，我觉得归为回溯这个议题下是不是更好。

茶艺师学编程： 超哥的板书 51. N 皇后 #1 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: if n < 1: return [] self.result = [] self.cols = set(); self.pie = set(); self.na = set() self.DFS(n, 0, []) return self._generate_result(n) def DFS(self, n, row, cur_state): if row >= n: self.result.append(cur_state) return for col in range(n): if col in self.cols or row + col in self.pie or row - col in self.na: continue self.cols.add(col) self.pie.add(row + col) self.na.add(row - col) self.DFS(n, row + 1, cur_state + [col]) self.cols.remove(col) self.pie.remove(row + col) self.na.remove(row - col) def _generate_result(self, n): board = [] for res in self.result: for i in res: board.append("." * i + "Q" + "." * (n - i - 1)) return [board[i: i + n] for i in range(0, len(board), n)] #2 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def DFS(queens, xy_dif, xy_sum): p = len(queens) if p == n: result.append(queens) return None for q in range(n): if q not in queens and p-q not in xy_dif and p+q not in xy_sum: DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q]) result = [] DFS([], [], []) return [["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

恢复现场那个操作具体作用是什么？如果去掉的话，递归到后面行，怎么匹配与前几行是否冲突，而且如果第一行随便放的话，这个4*4一定是有解的吗