学校组织的计算机技能大赛，题目解八皇后并做程序演示，顺便就贴博客上来。

八皇后问题

简述：8*8的棋盘，有八个皇后，每个皇后不能在同一行同一列同一斜线上，问有多少种可能的摆法。答案是92，这大家都知道。

解法与优化

首先肯定是遍历嘛，关键是要剪枝。

1.暴力枚举

8个子所有点遍历一遍，8个嵌套for，一共 C864 种情况。曰曰

2.回溯法

由于每个皇后不能在一行，那八个皇后就在八个不同行上面嘛，对于每个皇后/每一行，采用回溯法先第一行放一个，在第二行剩下7个位置中找第二个皇后可能的位置，以此类推，一共 88=16777216 种情况。

3.全排列

由于每个皇后不同行不同列，那么在每个皇后占一行的基础上，每个皇后在0-7个列只能占一个，就相当于一个全排列，要考虑 A88=8!=40320 种情况，较上述两个方法已经快了很多了。网上也都是回溯和全排列的算法。但是事实上还能再剪枝。

4.全排列再剪枝

对于全排列，依然可以剪枝。例如下图情况： 它的下一个排列是： 但是我们很明显的看到，第一、第二个皇后已经不满足条件了，后面的皇后无需再看了。因此我们直接跳到第1、2个皇后满足条件的排列：

最终，我们只需遍历3576种情况（根据实践得到的数据），这在全排列的基础上又优化了十倍多。这对八皇后适用，对n皇后都适用。

程序实现

概况

使用C#编写，平台是win10，环境是.Net Framework 4.6.1。 下载地址：http://download.csdn.net/download/xienaoban/9835240

特性

按“重置”即重置进度；

按“下一个”查找下一个符合条件的解并展示；

按“直接得出结果”不显示动画直接输出结果；

勾选“显示所有动画情况”演示所有遍历情况，勾选后再次点击“下一个”或“直接得出结果”演示所有遍历的情况；

遍历到当前方案时的遍历次数统计与可行方案统计显示在下方；

演示窗口自适应，修改窗口尺寸时始终保证棋盘最大化地显示在窗口中间；

演示画布采用双缓冲，防止演示动画时的窗口动画闪屏。

代码

八皇后类EnumQueens.cs（实现查找下一排列、重置排列等）：

using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; namespace EightQueen { class EnumQueens { private int[] Board; public EnumQueens() { Board = new int[8]; Reset(); } public void Reset() { for (int i = 0; i < 8; ++i) { Board[i] = i; } } public bool Next() { for (int i = Board.Length - 1; i > 0; --i) { if (Board[i] > Board[i - 1]) { int val = Board[i - 1]; int j = Board.Length - 1; for (; j >= i; --j) { if (Board[j] > val) break; } SwapBoard(i - 1, j); int l = i; int r = Board.Length - 1; while (l < r) { SwapBoard(l, r); l++; r--; } return true; } } Reset(); return false; } public Point Check() { Point ans = new Point(); for (int i = 0; i < Board.Length; ++i) { for (int j = i + 1; j < Board.Length; ++j) { if (Math.Abs(i - j) == Math.Abs(Board[i] - Board[j])) { ans.X = i;ans.Y = j; return ans; } } } ans.X = -1; ans.Y = -1; return ans; } public int Get(int i) { return Board[i]; } private void SwapBoard(int i, int j) { int t = Board[i]; Board[i] = Board[j]; Board[j] = t; } } }

含棋盘的演示窗口：MainForm.cs：

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Runtime.InteropServices; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Windows.Forms; namespace EightQueen { public partial class MainForm : Form { private int FrameLength = 30; private int Fwidth, Fheight, Fleft, Fright, Ftop, Fbottom, Flength, Fdiameter; private float Dif; [DllImport("user32 ")] private static extern IntPtr FindWindow(string lpClassName, string lpWindowName); [DllImport("user32 ")] private static extern IntPtr SetParent(IntPtr hWndChild, IntPtr hWndNewParent); public MainForm() { InitializeComponent(); Dif = 0.8f; Width = 400; Height = 600; PannelForm pForm = new PannelForm(); pForm.Show(); } private void MainForm_SizeChanged(object sender, EventArgs e) { if (Program.Board.Get(0) == 0 && Program.Board.Get(1) == 1) PaintQueens(Color.Orange); else PaintQueens(Color.LightGreen); } private void MainForm_Paint(object sender, PaintEventArgs e) { if (Program.Board.Get(0) == 0 && Program.Board.Get(1) == 1) PaintQueens(Color.Orange); else PaintQueens(Color.LightGreen); } public void PaintQueens(Color c) { Bitmap bmp = new Bitmap(Width, Height); Graphics grp = Graphics.FromImage(bmp); grp.Clear(Color.Azure); Pen pen; CalFrame(); pen = new Pen(Brushes.DeepSkyBlue, Flength / 160); for (int i = 1; i < 8; ++i) { grp.DrawLine(pen, new Point(Fleft + i * Fdiameter, Ftop), new Point(Fleft + i * Fdiameter, Fbottom)); grp.DrawLine(pen, new Point(Fleft, Ftop + i * Fdiameter), new Point(Fright, Ftop + i * Fdiameter)); } pen = new Pen(Brushes.DodgerBlue, Flength / 100); grp.DrawLine(pen, new Point(Fleft, Ftop), new Point(Fright, Ftop)); grp.DrawLine(pen, new Point(Fright, Ftop), new Point(Fright, Fbottom)); grp.DrawLine(pen, new Point(Fleft, Fbottom), new Point(Fright, Fbottom)); grp.DrawLine(pen, new Point(Fleft, Ftop), new Point(Fleft, Fbottom)); SolidBrush brush = new SolidBrush(c); Rectangle rect; int dif = (int)((1.0f - Dif) * Fdiameter/2); for (int i = 0; i < 8; ++i) { rect = new Rectangle(Fleft + Program.Board.Get(i) * Fdiameter + dif, Ftop + i * Fdiameter + dif, Fdiameter - 2 * dif, Fdiameter - 2 * dif); grp.FillEllipse(brush, rect); } this.CreateGraphics().DrawImage(bmp, 0, 0); } private void CalFrame() { int width = this.Width - 17; int height = this.Height - 40; Fwidth = width - FrameLength * 2; Fheight = height - FrameLength * 2; Flength = (Math.Min(Fwidth, Fheight) / 8) * 8; Fleft = (width - Flength) / 2; Fright = Fleft + Flength; Ftop = (height - Flength) / 2; Fbottom = Ftop + Flength; Fdiameter = Flength / 8; } } }

控制面板窗口PannelForm.cs：

using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Windows.Forms; namespace EightQueen { public partial class PannelForm : Form { private Button button1; private Button button2; private Label label1; private Label label2; private Label label3; private Label label4; public int Ergodic, Solution; private Button button3; private Button button4; private Button button5; private CheckBox checkBox1; public PannelForm() { InitializeComponent(); } private void InitializeComponent() { this.button1 = new System.Windows.Forms.Button(); this.button2 = new System.Windows.Forms.Button(); this.label1 = new System.Windows.Forms.Label(); this.label2 = new System.Windows.Forms.Label(); this.label3 = new System.Windows.Forms.Label(); this.label4 = new System.Windows.Forms.Label(); this.button3 = new System.Windows.Forms.Button(); this.button4 = new System.Windows.Forms.Button(); this.checkBox1 = new System.Windows.Forms.CheckBox(); this.button5 = new System.Windows.Forms.Button(); this.SuspendLayout(); // // button1 // this.button1.FlatStyle = System.Windows.Forms.FlatStyle.Flat; this.button1.Font = new System.Drawing.Font("微软雅黑", 15F); this.button1.ForeColor = System.Drawing.SystemColors.HotTrack; this.button1.Location = new System.Drawing.Point(12, 12); this.button1.Name = "button1"; this.button1.Size = new System.Drawing.Size(268, 51); this.button1.TabIndex = 0; this.button1.Text = "重置"; this.button1.TextAlign = System.Drawing.ContentAlignment.MiddleLeft; this.button1.UseVisualStyleBackColor = true; this.button1.Click += new System.EventHandler(this.button1_Click); // // button2 // this.button2.BackgroundImageLayout = System.Windows.Forms.ImageLayout.None; this.button2.FlatStyle = System.Windows.Forms.FlatStyle.Flat; this.button2.Font = new System.Drawing.Font("微软雅黑", 15F); this.button2.ForeColor = System.Drawing.SystemColors.HotTrack; this.button2.Location = new System.Drawing.Point(12, 69); this.button2.Name = "button2"; this.button2.Size = new System.Drawing.Size(268, 51); this.button2.TabIndex = 1; this.button2.Text = "下一个"; this.button2.TextAlign = System.Drawing.ContentAlignment.MiddleLeft; this.button2.UseVisualStyleBackColor = true; this.button2.Click += new System.EventHandler(this.button2_Click); // // label1 // this.label1.AutoSize = true; this.label1.Font = new System.Drawing.Font("微软雅黑", 15F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134))); this.label1.ForeColor = System.Drawing.SystemColors.HotTrack; this.label1.Location = new System.Drawing.Point(17, 231); this.label1.Name = "label1"; this.label1.Size = new System.Drawing.Size(132, 27); this.label1.TabIndex = 2; this.label1.Text = "遍历次数统计"; this.label1.Click += new System.EventHandler(this.label1_Click); // // label2 // this.label2.AutoSize = true; this.label2.Font = new System.Drawing.Font("华文彩云", 60F); this.label2.ForeColor = System.Drawing.SystemColors.HotTrack; this.label2.Location = new System.Drawing.Point(23, 258); this.label2.Name = "label2"; this.label2.Size = new System.Drawing.Size(80, 83); this.label2.TabIndex = 3; this.label2.Text = "0"; this.label2.Click += new System.EventHandler(this.label2_Click); // // label3 // this.label3.AutoSize = true; this.label3.Font = new System.Drawing.Font("微软雅黑", 15F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134))); this.label3.ForeColor = System.Drawing.SystemColors.HotTrack; this.label3.Location = new System.Drawing.Point(17, 377); this.label3.Name = "label3"; this.label3.Size = new System.Drawing.Size(132, 27); this.label3.TabIndex = 4; this.label3.Text = "可行方案统计"; // // label4 // this.label4.AutoSize = true; this.label4.Font = new System.Drawing.Font("华文彩云", 71.99999F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134))); this.label4.ForeColor = System.Drawing.SystemColors.HotTrack; this.label4.Location = new System.Drawing.Point(23, 404); this.label4.Name = "label4"; this.label4.Size = new System.Drawing.Size(97, 100); this.label4.TabIndex = 5; this.label4.Text = "0"; this.label4.Click += new System.EventHandler(this.label4_Click); // // button3 // this.button3.BackgroundImageLayout = System.Windows.Forms.ImageLayout.None; this.button3.FlatStyle = System.Windows.Forms.FlatStyle.Flat; this.button3.Font = new System.Drawing.Font("微软雅黑", 15F); this.button3.ForeColor = System.Drawing.SystemColors.HotTrack; this.button3.Location = new System.Drawing.Point(12, 227); this.button3.Name = "button3"; this.button3.Size = new System.Drawing.Size(268, 140); this.button3.TabIndex = 6; this.button3.TextAlign = System.Drawing.ContentAlignment.MiddleLeft; this.button3.UseVisualStyleBackColor = true; // // button4 // this.button4.BackgroundImageLayout = System.Windows.Forms.ImageLayout.None; this.button4.FlatStyle = System.Windows.Forms.FlatStyle.Flat; this.button4.Font = new System.Drawing.Font("微软雅黑", 15F); this.button4.ForeColor = System.Drawing.SystemColors.HotTrack; this.button4.Location = new System.Drawing.Point(12, 373); this.button4.Name = "button4"; this.button4.Size = new System.Drawing.Size(268, 140); this.button4.TabIndex = 7; this.button4.TextAlign = System.Drawing.ContentAlignment.MiddleLeft; this.button4.UseVisualStyleBackColor = true; // // checkBox1 // this.checkBox1.Font = new System.Drawing.Font("微软雅黑", 9F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(134))); this.checkBox1.ForeColor = System.Drawing.SystemColors.HotTrack; this.checkBox1.Location = new System.Drawing.Point(17, 194); this.checkBox1.Name = "checkBox1"; this.checkBox1.Size = new System.Drawing.Size(123, 21); this.checkBox1.TabIndex = 0; this.checkBox1.Text = "显示所有遍历情况"; this.checkBox1.UseVisualStyleBackColor = true; this.checkBox1.CheckedChanged += new System.EventHandler(this.checkBox1_CheckedChanged); // // button5 // this.button5.BackgroundImageLayout = System.Windows.Forms.ImageLayout.None; this.button5.FlatStyle = System.Windows.Forms.FlatStyle.Flat; this.button5.Font = new System.Drawing.Font("微软雅黑", 15F); this.button5.ForeColor = System.Drawing.SystemColors.HotTrack; this.button5.Location = new System.Drawing.Point(12, 126); this.button5.Name = "button5"; this.button5.Size = new System.Drawing.Size(268, 51); this.button5.TabIndex = 8; this.button5.Text = "直接得出结果"; this.button5.TextAlign = System.Drawing.ContentAlignment.MiddleLeft; this.button5.UseVisualStyleBackColor = true; this.button5.Click += new System.EventHandler(this.button5_Click); // // PannelForm // this.BackColor = System.Drawing.Color.Azure; this.ClientSize = new System.Drawing.Size(292, 535); this.Controls.Add(this.button5); this.Controls.Add(this.checkBox1); this.Controls.Add(this.label4); this.Controls.Add(this.label3); this.Controls.Add(this.label2); this.Controls.Add(this.label1); this.Controls.Add(this.button2); this.Controls.Add(this.button1); this.Controls.Add(this.button3); this.Controls.Add(this.button4); this.DoubleBuffered = true; this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle; this.Name = "PannelForm"; this.Text = "控制面板"; this.Load += new System.EventHandler(this.PannelForm_Load); this.ResumeLayout(false); this.PerformLayout(); } private void button2_Click(object sender, EventArgs e) { if (!Next()) { label4.Text = (Solution).ToString(); label2.Text = (Ergodic).ToString(); MessageBox.Show("所有情况已遍历！", "Duang！！！"); Reset(); } else { label4.Text = (Solution).ToString(); label2.Text = (Ergodic).ToString(); Program.mForm.PaintQueens(Color.LightGreen); } } private void button5_Click(object sender, EventArgs e) { while (Next()) { if (checkBox1.Checked) { label4.Text = (Solution).ToString(); label2.Text = (Ergodic).ToString(); Program.mForm.PaintQueens(Color.LightGreen); } } label4.Text = (Solution).ToString(); label2.Text = (Ergodic).ToString(); Program.mForm.PaintQueens(Color.LightGreen); MessageBox.Show("所有情况已遍历！", "Duang！！！"); Reset(); } private void button1_Click(object sender, EventArgs e) { Reset(); } private void label1_Click(object sender, EventArgs e) { } private void PannelForm_Load(object sender, EventArgs e) { } public bool Next() { while (Program.Board.Next()) { ++Ergodic; Point index = Program.Board.Check(); if (index.X != -1) { Point val = new Point(); val.X = Program.Board.Get(index.X); val.Y = Program.Board.Get(index.Y); bool flg = true; while (flg = Program.Board.Next()) { if (Program.Board.Get(index.X) != val.X|| Program.Board.Get(index.Y) != val.Y) { break; } } if (!flg) break; if(checkBox1.Checked) Program.mForm.PaintQueens(Color.Orange); } if (index.X != -1) { index = Program.Board.Check(); } if (index.X == -1) { ++Solution; return true; } } return false; } private void label4_Click(object sender, EventArgs e) { } private void label2_Click(object sender, EventArgs e) { } private void checkBox1_CheckedChanged(object sender, EventArgs e) { } public void Reset() { label2.Text = (Ergodic = 0).ToString(); label4.Text = (Solution = 0).ToString(); Program.Board.Reset(); Program.mForm.PaintQueens(Color.Orange); } } }

程序入口Program.cs：

using System; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks; using System.Windows.Forms; namespace EightQueen { static class Program { /// <summary> /// 应用程序的主入口点。 /// </summary> static public EnumQueens Board; static public MainForm mForm; [STAThread] static void Main() { Board = new EnumQueens(); Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(mForm = new MainForm()); } } }

其他系统自动产生的文件代码不贴了。