八皇后问题

//
// Created by yuanhao on 2019-9-3.
//
#include <iostream>

using namespace std;

class Solution {
    long long n;     //n个皇后
    long long total; //总共的解法
    int *c;
public:

    explicit Solution(long long n) : n(n), total(0), c(new int[n]) {

    }

    ~Solution() {
        delete[] c;
    }

    long long getTotal() {
        maxQueen(0);
        return total;
    }

    //八皇后问题共有92种解法(回溯法、递归实现)
    void maxQueen(int row) {
        if (row == n) {
            total++;
        } else {
            for (int col = 0; col != n; col++) {
                c[row] = col;
                if (isOk(row)) {
                    maxQueen(row + 1); //递归调用，进行下一行的安排
                }
            }
        }
    }

    //判断一个位置是否可以放置皇后
    bool isOk(int row) {
        for (int j = 0; j != row; j++) {
            if ((c[row] == c[j]) || (row - c[row] == j - c[j]) || (row + c[row] == j + c[j]))
                return false;
        }
        return true;
    }
};

//八皇后问题，是一个古老而著名的问题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。利用回溯算法我们能很快的得到共有92种互不相同的解（独立解有12种）。当棋盘变成n行，n列，且皇后也有n个的时候（n<=20），问有多少种不同的解？
//
//输入描述:
//一行，一个正整数n(1<=n<=20)
//
//
//输出描述:
//输出一个整数，代表解的个数。
//示例1
//输入
//8
//输出
//92
//示例2
//输入
//20
//输出
//39029188884
int main() {
    long long n = 0;
    cin >> n;
    // Solution s(n);
    // cout << s.getTotal() << endl;
    // 普通的解法肯定超时，最牛的大牛求解16皇后都要十几秒时间，更别说一秒钟之内求解20皇后问题了
    // 所以，下面是唯一的办法了。。。
    // 查表法，先全部算好，直接查表就行
    // ^(^.^)^
    long long a[20] = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104,
                       666090624, 4968057848, 39029188884};
    cout << a[n - 1] << endl;
}

#include<bits/stdc++.h>
using namespace std;
int hashtable[15]={0};
int p[15];
void DFS(int x,int d,int& count){
	if(x==d+1){
		count++;
		return;
	}else{
		for(int i=1;i<=d;i++){
			if(hashtable[i]==false){
				bool flag=true;
				for(int pre=1;pre<x;pre++){
					if(abs(x-pre)==abs(i-p[pre])){
						flag=false;
						break;
					}
				}
				if(flag==true){
					p[x]=i;
					hashtable[i]=true;
					DFS(x+1,d,count);
					hashtable[i]=false;
				}
			}
		}
	}
}
int main(){
	int n;
	cin>>n;
	int count=0; 
	DFS(1,n,count);
	cout<<count<<endl;
}

/*用循环递归实现
可惜大数还是超时（ac 65%）
*/
import java.util.Scanner;
public class Main{
    public static void main(String []Args)
    {
        Scanner in=new Scanner(System.in);
        int num=in.nextInt();//行数
        int count=0;    //计数
        chess queen=new chess(num);
        int n=0;//当前行号（0~~num-1）
        int m=0;//当前列号
        if(num==1)
        {
            System.out.println("1");
            return ;
        }
        while(!(n==0&&m>=num))//终点为第一行的所有元素都已经用完
        {
            if(m>=num)  //返回时过界(m进行了+1动作)
            {
                m=queen.element[--n]+1;
                continue;
            }
            //(1)当前行列号能使用
            if(queen.set(n,m)==true)
            {
                if(n==num-1)//到达最后一行,记录该方式，回退(下一步让前驱值＋1)
                {
                    count++;
                    m=queen.element[--n]+1;//前一值往后走
                    continue;
                }
                else//往下一行走
                {
                    n++;//前进
                    m=0;//后一值重新考虑所有情况
                    continue;
                }
            }
            //(2)当前行列号不能使用
            else
            {
                if(m==num-1)//当前列无可再选，回退
                {
                    if(n==0)//当前0行，无可再选
                    {
                        break;
                    }
                    m=queen.element[--n]+1;//前一值往后走
                    continue;
                }
                else{//往下列走
                    m++;
                    continue;
                }
            }
        }
        System.out.println(count);
    }
}
class chess{
    int[]element;
    int length;
    public chess(int n)
    {
        this.element=new int[n];
        this.length=n;
    }
    public boolean set(int n,int m)//判断当前序号下标为n的地方能否插入m
    {
        if(n>=this.length||m>=this.length||n<0||m<0)//边界条件
        {
            return false;
        }
        for(int i=0;i<n;i++)
        {
            if(m==this.element[i]||(m-n)==(this.element[i]-i)||(n+m)==(this.element[i]+i))//斜角及同列判断
            {
                return false;    //当前位置不合适，返回
            }
        }//判断结束，可插入
        this.element[n]=m;
        return true;//当前位置不能插入返回错误
    }

}

var n = parseInt(readline());
var method = 0;
function queen(pos){
    if(pos.length===n){
        // console.log(pos);
        method++;
    }else{
        for(var i=0; i<n; i++){
            var status = true;
            for(var j=0; j<pos.length; j++){
                if(pos[j]===i || pos[j]-i === pos.length-j || pos[j]-i===j-pos.length){
                    status = false;
                    break;
                }
            }
            if(status){
                queen(pos.concat([i]));
            }
        }
    }
}
if(n<=12){
    queen([]);
}else{
    switch(n){
        case 13:
            method = 73712;
            break;
        case 14:
            method = 365596;
            break;
        case 15: 
            method = 2279184;
            break;
        case 16: 
            method = 14772512;
            break;
        case 17:
            method = 95815104;
            break;
        case 18:
            method = 666090624;
            break;
        case 19:
            method = 4968057848;
            break;
        case 20:
            method = 39029188884;
    }
}
print(method);

#栈代替递归
#木大木大，该超时还是超时...

n=int(input())
A, ans=[-1], 0                              # 初始list，第n个元素为i，代表第n行第i列，注释中假设以最下面为第0行
while len(A):                               # list空后结束，即第一行（第0行）所有列的所有可能都已搜索完毕了
    for A[-1] in range(A[-1]+1,n):          # list中最后一个数字，即循环到的最高一行的列数继续递增
        for row in range(len(A)-1):         # 这一行和下面一行用来检测纵横斜有没有皇后
            if A[row] == A[-1] or abs(A[-1] - A[row]) == len(A) - 1 - row: break    # 有皇后break弹出（即不是成功循环结束，不运行循环结束的代码块）
        else:                               # 如果循环成功没有皇后
            if len(A)==n: ans+=1             # 如果达到n层就输出
            else: A += [-1]; break          # 没达到则把A往上加一行，break弹出（即不是成功循环结束，不运行循环结束的代码块），加的最上面一行开始寻找
    else: A.pop()                           # 该行的列数成功循环到上限，就把这行pop掉，在次行继续搜索
print(ans)