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.."]]
传说中的N皇后问题，据说AC了这题就能掌握图论搜索，进而称霸算法，然后迎娶白富美，走上人生巅峰。
不就是dfs嘛。
一行行地做dfs。每一轮先找这一行有哪些地方可以放Queen，把这些点置成Q，循环递归这些点，最后不要忘记把默认值'.'写回去。
如果到了最后一行，并且可以放得下Queen，这就是一个正确的解。
因为每一行只能放一个，如果遇到放不下的情况，说明已经错了。
找行上的候选人的时候，第一眼看上去要找8个方向。
但首先，行上就不用找了，列方向上和2个斜的方向上只需要找上半部分，因为下面都没开始放Q，肯定不冲突的。
1 /** 2 * @param {number} n 3 * @return {string[][]} 4 */ 5 var solveNQueens = function(n) { 6 var map = []; 7 var result = []; 8 buildMap(); 9 dfs(0);10 return result;11 12 function dfs(row){13 var i = 0, j = 0;14 var candidates = [];15 for(i = 0; i < n; i++){16 if(canPlaceQueen(row, i)){17 candidates.push(i);18 }19 }20 if(row === n -1 && candidates.length !== 0){ //found21 map[row][candidates[0]] = 'Q';22 result.push(formatMap(map));23 map[row][candidates[0]] = '.';24 return;25 }26 for(i = 0; i < candidates.length; i++){27 map[row][candidates[i]] = 'Q';28 dfs(row + 1);29 map[row][candidates[i]] = '.';30 }31 }32 function canPlaceQueen(x, y){33 var cell = "";34 var i = 0, j = 0;35 for(i = 0; i < n; i++){36 cell = map[i][y];37 if(cell === 'Q'){38 return false;39 } 40 }41 for(i = x, j = y; i >=0 && j >= 0; i--, j--){42 cell = map[i][j];43 if(cell === 'Q'){44 return false;45 } 46 }47 for(i = x, j = y; i >=0 && j < n; i--, j++){48 cell = map[i][j];49 if(cell === 'Q'){50 return false;51 } 52 }53 return true;54 }55 function buildMap(){56 var i = 0, j = 0;57 for(i = 0; i < n; i++){58 map[i] = [];59 }60 for(i = 0; i < n; i++){61 for(j = 0; j < n; j++){62 map[i][j] = '.';63 }64 }65 }66 function formatMap(map){67 var res = [];68 var i = 0, j = 0;69 for(i = 0; i < n; i++){70 var tmp = "";71 for(j = 0; j < n; j++){72 tmp += map[i][j];73 }74 res.push(tmp);75 }76 return res;77 }78 };