八皇后问题,C#语言的实现

作者: 药药耀耀 | 来源:发表于2016-04-12 15:44 被阅读473次
(首先 不懂国际象棋走法的朋友,这里先普及一下国际象棋的规则,国际象棋在一个8*8格子的棋盘上进行,皇后是国际象棋中威力最大的棋子(估计是因为欧洲很多女皇的原因吧),等同于中国象棋中的车,不过,皇后比车还要厉害 因为她还可以斜着走,上图就是一种解法)

八皇后问题问题描述:
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。之后陆续有数学家对其进行研究,其中包括高斯和康托(高斯认为有76种方案)并且将其推广为更高级的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更高级的n皇后摆放问题的人之一。1874年,S.冈德尔提出了一个通过行列式来求解的方法,这个方法后来又被J.W.L.格莱舍加以改进。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

网上有很多关于C++和JAVA的算法实现 下面我们用C#语言实现这个问题。
C#的解决算法:
using System;
using System.Collections.Generic;
namespace QueensSolution
{
class Program
{
static int count = 0;
static void Main(string[] args)
{
int n = Int32.Parse(Console.ReadLine());
List<int> queen = new List<int>(n);
for (int i = 1; i <= n; i++)
{
queen.Add(0);
}
PutQueen(n, queen, 0);
Console.WriteLine(count);
Console.ReadKey();
}
private static void PutQueen(int n, List<int> queen, int row)
{
for (queen[row] = 1; queen[row] <= n; queen[row]++)
{
if (CheckQueens(queen, row))
{
row++;
if (row < n)
{
PutQueen(n, queen, row);
}
else
{
count++;
for (int i = 0; i < n; i++)
{
Console.Write(queen[i].ToString() + " ");
}
Console.WriteLine();
}
row--;
}
}
}
private static bool CheckQueens(List<int> queen, int row)
{
for (int i = 0; i < row; i++)
{
if (Math.Abs(queen[i] - queen[row]) == Math.Abs(i - row) || queen[i] == queen[row])
{
return false;
}
}
return true;
}
}
}
解释:
1.要想解出在n*n的棋盘上到底有多少种放置皇后的方法,主要用到两个方法,放皇后的PutQueen方法,检查皇后的CheckQueens方法。
2.在Main函数里对动态数组进行初始化,这个动态数组用来记录N皇后中每一行所放置的皇后的位置(1就代表放置在该行第一列,n就代表放置在该行的第n列)。
3.row代表的是八皇后棋盘的每一行。
4.在Main函数中对动态数组进行了一下初始化,这一步是必须的,否则运行结果报错。
5.变量count(解的个数)声明在Main函数外,是静态的。
6.PutQueen方法采用递归思想——放皇后(该行中每一列都要放置),检查放皇后的位置是否合理,如果合理则到下一行,判断下一行是否存在,如果存在——放皇后(该行中每一列都要放置),检查放皇后的位置是否合理,如果合理则……直到不存在下一行为止每一行都已经放置好了皇后,这时我们将解的个数记录一下(count++),然后打印该种解法。
7.在递归结束后,一定要记得返回到上一行(row--),这样才能让“for (queen[row] = 1; queen[row] <= n; queen[row]++)”生效,实现每一行中的每一列都放置过皇后。一定要注意row--的位置要放在整个if-else语句块的后面!因为整个if-else语句块形成了对递归过程中状态的判断,有两种状态,第一种状态是皇后当前在第2到n-1行,这时候如果想返回上一行,“row--”的位置其实可以写在if语句块中"PutQueen(n, queen, row);"这一句的后面;第二种状态是皇后当前在最后一行(也就是第n行),这时候如果想返回上一行,“row--”的位置其实可以写在else语句块中。因此,我们才将“row--”的位置移到了整个if-else语句块的后面。

此时 我们运行程序,可以得到八皇后的正解92

QQ图片20160412154725.jpg

当然我们使用了递归的算法 所以 问题可以扩展到十皇后到N皇后(当然了 一般家用台式机,十皇后以后的计算就非常耗时,对计算机的运算能力是个挑战)

相关文章

  • 八皇后问题,C#语言的实现

    八皇后问题问题描述:八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔...

  • 八皇后和约瑟夫问题

    今天在写C语言报告的时候,收获了两种算法的实现,分别是八皇后和约瑟夫问题。 八皇后:总的来说,八皇后问题就是一种b...

  • 八皇后问题 Python实现

    八皇后问题 Python实现 田田田 八皇后问题:国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子。皇后这种棋...

  • 使用java语言实现八皇后问题

    八皇后问题,在一个8X8的棋盘中,放置八个棋子,每个棋子的上下左右,左上左下,右上右下方向上不得有其他棋子。正确答...

  • 八皇后问题c语言算法

    目录[TOC] 问题分析: 相信八皇后规则的问题,大家都很熟悉,接下来是如何分析回溯法的应用。回溯法与图里面的深度...

  • 八皇后,回溯与递归(Python实现)

    八皇后问题是十九世纪著名的数学家高斯1850年提出 。以下为python语言的八皇后代码,摘自《Python基础教...

  • 八皇后问题

    采用试探回溯策略,通过栈记录查找结果,实现八皇后问题求解。 测试代码

  • 11.数据结构—八皇后问题(回溯法)

    11.1 八皇后问题 八皇后问题是以国际象棋为背景的问题:有八个皇后(可以当成八个棋子),如何在 88 的棋盘中放...

  • 八皇后问题之java实现

    1.八皇后指在八行八列的的矩阵上放八个皇后,任意两个皇后不在同一行或同一列,或同一斜线上。 2.代码实现

  • c语言 递归实现八皇后算法

网友评论

    本文标题:八皇后问题,C#语言的实现

    本文链接:https://www.haomeiwen.com/subject/ypcwlttx.html