求思路！！用的是搜索的知识，会的就请进！！！
小主教问题是一个在正方格板上玩的国际象棋游戏。一个主教只可以在当前位置的对角线上移动。如果一个主教处在另一主教的对角线上，那么两个主教就会相互攻击。在下面的图中，深色的方格表示主教1 可以达到的位置。图中还说明主教1 和主教2 处在相互攻击的位置上，而主教B1和主教3彼此不会攻击，而且主教2和主教3也不处在相互攻击的位置上。_ _ _ _ _ _ _
_ _ _ 3 _ 2 _
_ _ _ _ _ _ _
_ _ _ 1 _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ _
（‘-’代表一空格）
假设给定两个数n和k，现在需要确定把k个主教放在n × n大小的棋盘上，且任意两个主教都不会发生相互攻击，那么请编程算出共有多少种可能的放置方法。
输入：
输入可能包含多组测试用例。每组测试用例占一行，且包含两个整数n（1<=n<=8）和k（0 <= k <= n2）。
如果测试用例包含两个数字零，则表示终止输入，且不需处理此次输入。
输出：
对应每组测试输入有一个表示解决放置方法总数量的输出。此数值不大于1015。
思路是怎样走的？
