// 8 queens
#include <stdio.h>
int position[9]; // 第i个皇后的列号是position[i] (i:1-8)

int check(int step){
    int i;
    
    if(position[step]>8) return 0;
    for(i=1; i<step; i++){
        if (position[i] == position[step] ||
            position[i] - position[step] == i - step ||
            position[i] - position[step] == step - i) {
            return 0;
        }
    }
    return 1;
}


int main(){
    
    int step,count,i;
    count = 0;
    
    step = 1;
    position[1] = 1;
    
    while (step>0) {
        if (check(step)) {
            if (step == 8) {
                //输出，回溯到前一个皇后的位置   step--
                count++;
                printf("%d: ",count);
                for(i=1; i<9; i++) printf("%d ",position[i]);
                printf("\n");
                step--;
                position[step]++;
            }
            else{
                //放下一个皇后   step++
                step++;
                position[step]=1;
            }
        }
        else{
           //放下一个位置（如果试探完8列，则应该回溯到前一个皇后 step--）
            if(position[step]>=8) step--;
            position[step]++;
        }
    }
    
    return 0;
}

//递归算法
#include<stdio.h>
#include<time.h>

typedef int Bool;
int a[8][8]={0};
int count=0;

Bool Check(int row,int colum)
{
	int i,j;
	if(row==1)
		return 1;
	for(i=0;i<row-1;i++)
		if(a[i][colum-1]==1)
			return 0;
	i=row-2;
	j=i-(row-colum);
	while(i>=0&&j>=0)
	{
		if(a[i][j]==1)
			return 0;
		j--;
		i--;
	}//检查左上至右下
	i=row-2;
	j=row+colum-i-2;
	while(i>=0&&j<=7)
	{
		if(a[i][j]==1)
			return 0;
		i--;
		j++;
	}//检查右上至左下
	return 1;
}

void Output()
{
	int i,j;
	count++;
	printf("Answer %d:\n ",count);
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
}

void Solve(int row)
{
	int j;
	for(j=0;j<8;j++)
	{
		a[row-1][j]=1;
		if(Check(row,j+1)==1)
		{
			if(row==8)
				Output();
			else
				Solve(row+1);
		}
		a[row-1][j]=0;//回溯
	}
}

int main(void)
{
	clock_t start=clock();
	Solve(1);
	printf("Processor time: %g sec.\n",(clock()-start)/(double)CLOCKS_PER_SEC);
	return 0;
}