51.N皇后问题

leetcode

回溯法解题。

1. 考虑给每行设置皇后在哪一列，所以维护一个列数组表示哪些列有皇后了，则这些列不能再分配皇后。
2. 皇后所在的斜线上也不能有皇后，斜线规律为行数和列数之差相等以及行数和列数之和相等，故维护一个行数列数之差的map以及行数列数之和的map。
3. 递归遍历每行的列，看是否能够在该行该列防止皇后。
4. 每层递归结束记得还原现场，即修改列数组和斜线map。

   func solveNQueens(n int) [][]string {
       columns := make([]bool, n)
       crossL := make(map[int]bool)
       crossR := make(map[int]bool)
   
       results := [][]int{}
   
       var backtrack func([]int, int)
   
       backtrack = func(queens []int, row int){
           if (row >= n) {
   	        // 注意二维数组的slice赋值最好新建对象
               results = append(results, append([]int{}, queens...))
               // fmt.Printf("results: %v\n", results)
               return
           }
           for col := 0; col < n; col++ {
               // fmt.Printf("row: %v col: %v\n", row, col)
               if c, ok := crossL[row - col]; ok && c {
                   continue
               }
   
               if c, ok := crossR[row + col]; ok && c {
                   continue
               }
   
               if !columns[col]  {
                   columns[col] = true
                   crossL[row - col] = true
                   crossR[row + col] = true
                   queens := append(queens, col)
                   // fmt.Printf("queens: %v\n", queens)
                   backtrack(queens, row + 1)
                   // 还原现场
                   columns[col] = false
                   crossL[row - col] = false
                   crossR[row + col] = false
               }
           }
       }
   
       backtrack([]int{}, 0)
       
       ans := [][]string{}
   
       for _, result := range results {
           a := make([]string, n)
           for row := 0; row < n; row++ {
               for col := 0; col < n; col++ {
                   if col == result[row] {
                       a[row] = a[row] + "Q"
                   } else {
                       a[row] = a[row] + "."
                   }
               }
           }
           ans = append(ans, a)
       }
   
       return ans
   }
   
   <!-- more -->