本文中的代码在文章最后提供下载链接。

关于八皇后的问题，自己百度。回溯法的概念也可以自己维基百科中查看。

回溯法无非就是遍历解空间，如果合适的话就继续，不合适的话就放弃当前节点。可以采用递归实现。八皇后问题的经典算法就是采用回溯法。网上也有许多版本的解法，但是C#版本的似乎很少。笔者在此奉献上。

此处八皇后的算法的伪代码如下：

在第row行放置皇后(row)

{

for 第row行的格子

{           

把当前位置加入作为候选解加入解决方案中

   If 目前解决方案没有问题

           {

            再下一行放皇后，递归调用PlaceQueen(row+1);

           如果是最后一行放完了，则成功，打印棋盘

            }

    else

                          将位置（row,col）上的皇后取走，尝试下一列位置  //回溯

    }

伪代码的算法能理解之后，就可以写代码了。

对于棋盘，可以使用二维数组实现，但是本例中使用的是一个List序列，序列中有64个格子的信息。每个格子的定义如下。

//格子类。坐标x，y

   

 
  
     
   
  1. public class position  
    2.  
   
  2.    {  
    3.  
   
  3.         public int x { set; get; }   
    4.  
   
  4.         public int y { set; get; }   
    5.  
   
  5.         public override string ToString()   
    6.  
   
  6.        {  
    7.  
   
  7.             return string.Format("[{0},{1}]", x, y);   
    8.  
   
  8.        }  
    9.  
   
  9.    }  
    10.  
  
 
  
 
 
  
初始化格子的代码如下：
 
  
 
 
  
 
  
     
   
  1. #region 初始化格子  
    2.  
   
  2.              for (int i = 1; i <= dimension; i++)   
    3.  
   
  3.             {  
    4.  
   
  4.                  for (int j = 1; j <= dimension; j++)   
    5.  
   
  5.                 {  
    6.  
   
  6.                      lstAllPosition.Add(new position { x = i, y = j });   
    7.  
   
  7.                 }  
    8.  
   
  8.              }  
    9.  
   
  9.             #endregion 
    10.  
  
 
  
 
 
  
这样的话lstAllPosition就存放了64个格子了。由于采用了C#作为实现的语言，因此尽情的使用他的一些优点，比如采用Linq和拉姆达表达式来选定特定的行的元素。此处，需要有C#的一些知识。
 
  
对于放置皇后的实现。本人写了2种方法，2中方法本质都是一样的，只不过理解起来稍微有些不同。
 
  
第一种方法中规中矩。
 
  
看如下代码和注释： 
 
  
 
  
     
   
  1. static void PlaceQueen(int row)  
    2.  
   
  2.          {  
    3.  
   
  3.             #region 实现方法一  
    4.  
   
  4.              //当前行的元素   
    5.  
   
  5.             var currentrow = lstAllPosition.Where(m => m.x == row).ToList();  
    6.  
   
  6.              for (int index = 0; index < currentrow.Count;index++ )   
    7.  
   
  7.             {  
    8.  
   
  8.                  //加入一个元素   
    9.  
   
  9.                 solution.Add(currentrow[index]);  
    10.  
   
  10.                  //如果有效的话，继续下面的递归   
    11.  
   
  11.                  if (Valid(solution))   
    12.  
   
  12.                 {  
    13.  
   
  13.                      //如果row是最后一行了，说明已经满足。打印。   
    14.  
   
  14.                      if (row == dimension)   
    15.  
   
  15.                     {  
    16.  
   
  16.                         print(solution);  
    17.  
   
  17.                          //找到一组解之后，删除该元素，继续下一组解的查找   
    18.  
   
  18.                         solution.Remove(solution.Last());  
    19.  
   
  19.                     }  
    20.  
   
  20.                      else  
    21.  
   
  21.                     {  
    22.  
   
  22.                          //递归调用下一行   
    23.  
   
  23.                         PlaceQueen(row + 1);  
    24.  
   
  24.                     }  
    25.  
   
  25.                 }  
    26.  
   
  26.                  else  
    27.  
   
  27.                 {  
    28.  
   
  28.                     solution.Remove(currentrow[index]);  
    29.  
   
  29.                 }  
    30.  
   
  30.                  //如果该行的元素每个都被试过了，但是还是没能运行到print(solution)方法中去，则该方法即将运行结束，结束前，把最后一个元素也删掉。   
    31.  
   
  31.                  //由于该方法是递归的，因此结束之后，会继续重新下一个元素。   
    32.  
   
  32.                  if (index == dimension-1 && solution.Count > 0)   
    33.  
   
  33.                 {  
    34.  
   
  34.                     solution.Remove(solution.Last());  
    35.  
   
  35.                 }  
    36.  
   
  36.              }  
    37.  
   
  37.             #endregion  
    38.  
   
  38.         }  
    39.  
   
  39.  
    40.  
  
 
  
 
 
  
            第二种方法也很好理解，只是把solution.Remove(item);删除元素的语句写到外面，表示，无论怎样，都会把刚加入的元素删除。
 
  
但是在删除元素之前，由于递归调用的结果，在某些情况下solution列的元素加满到8个时候，还没删除元素。这是就直接打印出结果，然后再删除最后一个元素。很容易推断，到最后一个元素放入solution的时候，肯定是递归嵌套了8层了。  
 
  
 
  
     
   
  1. static void PlaceQueen(int row)  
    2.  
   
  2.          {  
    3.  
   
  3.             #region 实现方法二  
    4.  
   
  4.              foreach (var item in lstAllPosition.Where(m =&gt; m.x == row).ToList())   
    5.  
   
  5.             {  
    6.  
   
  6.                  //Console.WriteLine("-------");   
    7.  
   
  7.                 solution.Add(item);  
    8.  
   
  8.                  //solution.ForEach(m =&gt; Console.Write(m.ToString()));   
    9.  
   
  9.                  //Console.WriteLine();   
    10.  
   
  10.                  //如果有效的话，继续下面的递归   
    11.  
   
  11.                  if (Valid(solution))   
    12.  
   
  12.                 {  
    13.  
   
  13.                      //如果row是最后一行了，说明已经满足。打印。   
    14.  
   
  14.                      if (row == dimension)   
    15.  
   
  15.                     {  
    16.  
   
  16.                         print(solution);  
    17.  
   
  17.                     }  
    18.  
   
  18.                      else  
    19.  
   
  19.                     {  
    20.  
   
  20.                          //递归调用下一行   
    21.  
   
  21.                         PlaceQueen(row + 1);  
    22.  
   
  22.                     }  
    23.  
   
  23.                 }  
    24.  
   
  24.                  //Console.WriteLine("***");   
    25.  
   
  25.                  //把当前元素去除，尝试下一个元素。此语句，每一轮都会执行，除非该轮的调用，   
    26.  
   
  26.                  //每次递归调用PlaceQueen时Valid(solution)都是true，也就是说找到符合条件的结果集,打印完后。   
    27.  
   
  27.                  //还是会继续删除最厚放入的元素，继续尝试下一个元素是否匹配。   
    28.  
   
  28.                 solution.Remove(item);  
    29.  
   
  29.                //solution.ForEach(m =&gt; Console.Write(m.ToString()));   
    30.  
   
  30.                  //Console.WriteLine();   
    31.  
   
  31.                  //Console.WriteLine("-------");   
    32.  
   
  32.              }  
    33.  
   
  33.             #endregion  
    34.  
   
  34.         }  
    35.  
   
  35.  
    36.  
  
 
  
其中 验证当前集合是否有效的函数如下：
 
  
  //验证有效性
 
  
       
 
  
 
  
     
   
  1. static bool Valid(List<position> solve)  
    2.  
   
  2.        {  
    3.  
   
  3.            var item2 = solve.Last();  
    4.  
   
  4.             foreach (var item1 in solve)//把最后加入的元素后之前每一个元素做比较。   
    5.  
   
  5.            {  
    6.  
   
  6.                 if (item1 == item2)   
    7.  
   
  7.                {  
    8.  
   
  8.                     break;   
    9.  
   
  9.                }  
    10.  
   
  10.                 if (item1.y == item2.y)//y轴相同   
    11.  
   
  11.                {  
    12.  
   
  12.                     return false;   
    13.  
   
  13.                }  
    14.  
   
  14.                 else if (Math.Abs(decimal.Parse((item1.y - item2.y).ToString()) / (item1.x - item2.x)) == 1)//斜线   
    15.  
   
  15.                {  
    16.  
   
  16.                     return false;   
    17.  
   
  17.                }  
    18.  
   
  18.            }  
    19.  
   
  19.             return true;   
    20.  
   
  20.        } 
    21.  
  
 
  
打印棋盘的方法如下，使用了Linq和拉姆达表达式。
 
  
//打印棋盘
 
  
       
 
  
 
  
     
   
  1. static void print(List<position> solve)  
    2.  
   
  2.        {  
    3.  
   
  3.            Console.ForegroundColor = ConsoleColor.Gray;  
    4.  
   
  4.             Console.WriteLine("-----" + (count++) + "-------");   
    5.  
   
  5.             for (int i = 1; i <= dimension; i++)   
    6.  
   
  6.            {  
    7.  
   
  7.                 foreach (var item in lstAllPosition.Where(m => m.x == i).ToList())   
    8.  
   
  8.                {  
    9.  
   
  9.                     if (solve.Contains(item))   
    10.  
   
  10.                    {  
    11.  
   
  11.                        Console.ForegroundColor = ConsoleColor.Yellow;  
    12.  
   
  12.                         Console.Write("1 ");   
    13.  
   
  13.                    }  
    14.  
   
  14.                     else  
    15.  
   
  15.                    {  
    16.  
   
  16.                        Console.ForegroundColor = ConsoleColor.Gray;  
    17.  
   
  17.                         Console.Write("0 ");   
    18.  
   
  18.                    }  
    19.  
   
  19.                }  
    20.  
   
  20.                Console.WriteLine();  
    21.  
   
  21.            }  
    22.  
   
  22.        } 
    23.  
  
 
  
 结果如下：共92个解。
 
  
image
 
  
所有的解集如下：
 
  
-----1------- 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----2------- 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----3------- 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 -----4------- 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----5------- 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 -----6------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 -----7------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----8------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----9------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 -----10------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----11------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----12------- 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 -----13------- 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----14------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----15------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 -----16------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 -----17------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----18------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 -----19------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 -----20------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 -----21------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 -----22------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 -----23------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 -----24------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----25------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 -----26------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----27------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----28------- 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----29------- 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----30------- 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 -----31------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----32------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----33------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 -----34------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----35------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----36------- 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 -----37------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----38------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----39------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 -----40------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----41------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----42------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 -----43------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 -----44------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 -----45------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----46------- 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----47------- 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 -----48------- 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----49------- 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----50------- 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----51------- 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 -----52------- 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
 -----53------- 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----54------- 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----55------- 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 -----56------- 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 -----57------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 -----58------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----59------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----60------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 -----61------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 -----62------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 -----63------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----64------- 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 -----65------- 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 -----66------- 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 -----67------- 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 -----68------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----69------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 -----70------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----71------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 -----72------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 -----73------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----74------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----75------- 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----76------- 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 -----77------- 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 -----78------- 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 -----79------- 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 -----80------- 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 -----81------- 
 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----82------- 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----83------- 
 0 0 0 0 0 0 1 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 -----84------- 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 1 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----85------- 
 0 0 0 0 0 0 1 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 1 0 0 0 0 
 -----86------- 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----87------- 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 0 1 
 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 -----88------- 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
 -----89------- 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----90------- 
 0 0 0 0 0 0 0 1 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 0 0 0 0 0 1 0 0 
 -----91------- 
 0 0 0 0 0 0 0 1 
 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 1 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 1 0 0 0 0 
 -----92------- 
 0 0 0 0 0 0 0 1 
 0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
 0 0 1 0 0 0 0 0 
 0 0 0 0 0 1 0 0 
 0 1 0 0 0 0 0 0 
 0 0 0 0 0 0 1 0 
 0 0 0 0 1 0 0 0