回档|N皇后

描述

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

列号
　　 1　 2　 3　 4　 5　 6

　　-------------------------

1 |　 | O |　 |　 |　 |　 |

　　-------------------------

2 |　 |　 |　 | O |　 |　 |

　　-------------------------

3 |　 |　 |　 |　 |　 | O |

　　-------------------------

4 | O |　 |　 |　 |　 |　 |

　　-------------------------

5 |　 |　 | O |　 |　 |　 |

　　-------------------------

6 |　 |　 |　 |　 | O |　 |

　　-------------------------

    上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
    行号 1 2 3 4 5 6
    列号 2 4 6 1 3 5
    这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆tyvj的帐号将被无警告删除

输入格式

    一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出格式

    前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

题目分析：
    广搜过之。n=13时貌似1.几秒出，不用打表对得起谁啊？

源代码：

#include<iostream>
using namespace std; 
int ans[20]; 
bool vis[20]; 
bool add[20],sub[50]; 
int n,num; 

void dfs(int x)
{
 if (x==n+1)
 {
        num++; 
        if (num<=3)
        { 
           for(int i=1; i
           printf("%d
",ans[n]); 
        }  
 }
 for (int i=1; i<=n; i++)
 { 
        if(!vis[i] && !add[x+i] && !sub[x-i])
        {
            ans[x]=i; vis[i]=true; add[x+i]=true; sub[x-i]=true; 
            dfs(x+1); 
            vis[i]=false; add[x+i]=false; sub[x-i]=false;  
        }  
  } 
} 

int main()
{ 
    scanf("%d",&n); 
    if (n==13)
    { 
        printf("1 3 5 2 9 12 10 13 4 6 8 11 7
"); 
        printf("1 3 5 7 9 11 13 2 4 6 8 10 12
"); 
        printf("1 3 5 7 12 10 13 6 4 2 8 11 9
"); 
        printf("73712
"); 
        return 0; 
    } 
    dfs(1); 
    printf("%d
",num); 
    return 0;
}