[LeetCode][JavaScript]N-Queens II

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

https://leetcode.com/problems/n-queens-ii/

有了上一道的基础，这道就是送的。

http://www.cnblogs.com/Liok3187/p/4558502.html

test case也不是很强，我本地试14就要等10多秒，再往上就炸了。

 1 /**
 2  * @param {number} n
 3  * @return {string[][]}
 4  */
 5 var totalNQueens = function(n) {
 6     var map = [];
 7     var count = 0;   
 8     buildMap();
 9     dfs(0);
10     return count;
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){ //found
21             map[row][candidates[0]] = 'Q';
22             count++;
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 };