LC51 - N 皇后

package Backtrack

import (
    "math"
    "strings"
)

func solveNQueens(n int) [][]string {
    result := make([][]string, 0)
    distribution := make([]int, 0)
    var f func(int)
    f = func(index int) {
        if index == n {
            curAns := getAns(n, distribution)
            result = append(result, curAns)
            return
        }
        for curPos := 0; curPos < n; curPos++ {
            isValid := true
            for prevIndex, prevPos := range distribution {
                if curPos == prevPos || diagnol(index, curPos, prevIndex, prevPos) {
                    isValid = false
                    break
                }
            }
            if isValid {
                distribution = append(distribution, curPos)
                f(index + 1)
                distribution = distribution[:len(distribution)-1]
            }
        }
    }
    f(0)
    return result
}

func diagnol(index1, pos1, index2, pos2 int) bool {
    return math.Abs(float64(pos1-pos2)) == math.Abs(float64(index1-index2))
}

func getAns(n int, distribution []int) []string {
    result := make([]string, 0)
    str := strings.Repeat(".", n)
    for _, pos := range distribution {
        tmp := []byte(str)
        tmp[pos] = 'Q'
        result = append(result, string(tmp))
    }
    return result
}