题解 | #N皇后问题#

package main

/**
 * 
 * @param n int整型 the n
 * @return int整型
*/
func Nqueen( n int ) int {
    // write code here
	res := make([][]string, 0)
	var dfs func(total int, currLevel int, tmp []int)
	dfs = func(total int, currLevel int, tmp []int) {
		if currLevel == total {
			strs := make([]string, 0)
			for row := 0; row < total; row++ {
				str := ""
				for col := 0; col < total; col++ {
					if col == tmp[row] {
						str += "Q"
					} else {
						str += "."
					}
				}
				strs = append(strs, str)
			}
			res = append(res, strs)
			return
		}
		//每层从第一个开始放
		for i := 0; i < total; i++ {
			tmp[currLevel] = i
			//是否符合条件
			if isPass(currLevel, tmp) {
				dfs(total, currLevel+1, tmp)
			}
		}
	}
	tmp := make([]int, n)
	dfs(n, 0, tmp)
	return len(res)
}


func isPass(currLevel int, arr []int) bool {
	for i := 0; i < currLevel; i++ {
		if arr[currLevel] == arr[i] || (abs(currLevel, i) == abs(arr[currLevel], arr[i])) {
			return false
		}
	}
	return true
}

func abs(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}