//用来存放一组结果，下标为行，值为列，存储Q的位置
var temp []int
//存储最终结果数组
var res [][]string
var N int

func solveNQueens(n int) [][]string {
	N = n
	temp = make([]int, N)
	for i := 0; i < N; i++ {
		temp[i] = -1
	}
	res =[][]string{}
	findCurrentRowPosition(0)
	return res
}

func findCurrentRowPosition(row int) {
	//遍历到最后一行，对结果进行存储
	if row == N {
		save(temp)
		return
	}
	for column := 0; column < N; column++ {
		//如果该位置可以放置，则放置完以后检查下一行
		if isOk(row, column) {
			temp[row] = column
			findCurrentRowPosition(row + 1)
		}
	}
}

//检查该位置是否可以放置
func isOk(row int, column int) bool {
	preColumn := column - 1
	nextColumn := column + 1
	for i := row - 1; i >= 0; i-- {
		//检查正上方是否有棋子
		if temp[i] == column {
			return false
		}
		//检查左上方对角线是否有棋子
		if preColumn >= 0 {
			if temp[i] == preColumn {
				return false
			}
		}
		//检查右上方对角线是否有棋子
		if nextColumn < N {
			if temp[i] == nextColumn {
				return false
			}
		}
		preColumn--
		nextColumn++
	}

	return true
}

//用来存储最终结果
func save(temp []int) {
	var tRes = make([]string, N)
	//处理每一行
	for row, column := range temp {
		//处理每一列
		for i := 0; i < N; i++ {
			if column == i {
				tRes[row] += "Q"
			} else {
				tRes[row] += "."
			}
		}
	}
	res = append(res, tRes)
}