题解 | #N皇后问题#

package main

/**
 * 
 * @param n int整型 the n
 * @return int整型
*/
func Nqueen( n int ) int {
    tmp:=make([][]int,n)
    for i:=range tmp{
        tmp[i]=make([]int,n)
    }
    return dfs(tmp,0,n)
}

func dfs(tmp [][]int,level int,n int)int{
    if level>=n{return 1}
    sum:=0
    for j:=0;j<n;j++{
        if check(tmp, level, j, n){
            tmp[level][j]=1
            sum+=dfs(tmp,level+1,n)
            tmp[level][j]=0
        }
    }
    
    return sum
}

func check(tmp [][]int,y,x,n int)bool{
    for i:=0;i<y;i++{
        if tmp[i][x]==1{
            return false
        }
    }
    i:=y-1
    j:=x-1
    for i>=0&&j>=0{
        if tmp[i][j]==1{
            return false
        }
        i=i-1
        j=j-1
    }
    i=y+1
    j=x+1
    for i<n&&j<n{
        if tmp[i][j]==1{
            return false
        }
        i=i+1
        j=j+1
    }
    i=y-1
    j=x+1
    for i>=0&&j<n{
        if tmp[i][j]==1{
            return false
        }
        i=i-1
        j=j+1
    }
    i=y+1
    j=x-1
    for i<n&&j>=0{
        if tmp[i][j]==1{
            return false
        }
        i=i+1
        j=j-1
    }
    return true
}