精华内容
下载资源
问答
  • 八皇后问题动态演示

    2017-05-06 17:36:52
    八皇后问题动态演示,附博客原文:http://blog.csdn.net/XieNaoban/article/details/71273687
  • [玩耍]八皇后问题动态演示

    千次阅读 2017-05-06 17:31:17
    学校组织的计算机技能大赛,题目解八皇后并做程序演示,顺便就贴博客上来。八皇后问题简述:8*8的棋盘,有八个皇后,每个皇后不能在同一行同一列同一斜线上,问有多少种可能的摆法。答案是92,这大家都知道。解法与...

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

    八皇后问题

    简述: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());
            }
        }
    }

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

    展开全文
  • 八皇后问题:八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一...
  • 八皇后问题动态演示_Qt5实现 1 //核心代码如下 2 //Queen--放置皇后 3 4 #include "queue.h" 5 6 queue::queue() 7 { 8 const int maxn = 9*9; 9 this->QN = 4; 1...

    八皇后问题动态演示_Qt5实现

      1 //核心代码如下
      2 //Queen--放置皇后
      3 
      4 #include "queue.h"
      5 
      6 queue::queue()
      7 {
      8     const int maxn = 9*9;
      9     this->QN = 4;
     10     this->board = new bool[maxn];
     11     for (int i = 0; i < maxn; i++) {
     12         this->board[i] = false;
     13     }
     14     this->judgeRecursion = true;
     15     this->count = 0;
     16 }
     17 
     18 queue::queue(int N)
     19 {
     20     const int maxn = 81;
     21     if (N > 9 || N < 4)
     22         this->QN = 4;    //如果不合法就正规化棋盘
     23     else
     24         this->QN = N;
     25     this->board = new bool[maxn];
     26     for (int i = 0; i < maxn; ++i)  //初始化棋盘,未放置棋子的棋盘设置为false
     27         this->board[i] = false;
     28     this->judgeRecursion = true;
     29     this->count = 0;
     30 }
     31 
     32 bool queue::available (const int Crow, const int Ccol) const  //当前行,当前列
     33 {
     34     for (int hor = 0; hor < Crow; ++hor) {
     35         //纵向查找
     36         if (board[hor * QN + Ccol])     //已经放置皇后的棋盘处为true
     37             return false;               //则返回false--放置不合法
     38     }
     39     int obli = Crow, oblj = Ccol;
     40     while (obli > 0 && oblj > 0) {
     41         if (board[(--obli) * QN + (--oblj)])
     42             return false;              //左斜上查找
     43     }
     44     obli = Crow, oblj = Ccol;
     45     while (obli > 0 && oblj < QN - 1) {
     46         if (board[(--obli) * QN + (++oblj)])
     47             return false;              //右斜上查找
     48     }
     49     return true;                       //都没有,则该位置可以放置皇后
     50 }
     51 
     52 //打印棋盘
     53 void queue::show (bool *Q)
     54 {
     55     const int maxn = 81;
     56     for (int i = 0; i < maxn; i++)
     57         Q[i] = this->board[i];
     58 }
     59 
     60 //重新初始化棋盘
     61 void queue::reset ()
     62 {
     63     const int maxn = 81;
     64     for (int i = 0; i < maxn; i++)
     65         this->board[i] = false;
     66     this->judgeRecursion = true;
     67     this->count = 0;
     68 }
     69 
     70 void queue::reset (int N)
     71 {
     72     const int maxn = 81;
     73     if (N < 4 || N > 9) this->QN = 4;
     74     else
     75         this->QN = N;
     76 
     77     for (int i = 0; i < maxn; i++)
     78         this->board[i] = false;
     79     this->judgeRecursion = true;
     80     this->count = 0;
     81 }
     82 
     83 queue::~queue ()
     84 {
     85     delete []board;
     86     board = nullptr;
     87 }
     88 
     89 /**
     90  * @brief queue::answer --- 放置皇后
     91  * @param solu --- 求解的方法数
     92  * @param Crow --- 当前的行数
     93  * @param Q --- 棋盘,用来打印
     94  */
     95 void queue::answer (int solu, int cur, bool *Q)
     96 {
     97     if (!judgeRecursion)   //递归结束,中断
     98         return;
     99     if (cur == QN) {                  //当前行到最后一行,则一种方案结束
    100         count++;
    101         if (count == solu) {          //递归到第solu方案时停止
    102             this->show (Q);
    103             judgeRecursion = false;   //停止递归
    104             return;
    105         }
    106         return;
    107     }
    108     else
    109     {
    110         for (int col = 0; col < QN; col++)
    111         {
    112             if (available (cur, col))         //检查当前行,列
    113             {
    114                 board[cur * QN + col] = true; //合法则放置皇后
    115                 answer (solu, cur + 1, Q);    //递归下一行
    116                 //如果回溯法中使用了辅助的全局变量,则一定要及时把它们恢复原状.
    117                 //特别的,若函数有多个出口,则需在每个出口处恢复被修改的值
    118                 board[cur * QN + col] = false;
    119             }
    120         }
    121     }
    122 }

    源代码下载地址:链接:https://pan.baidu.com/s/12BTDR8pRMvxpKYNFb988EQ 密码:yk0o

    posted @ 2016-10-06 16:30 douzujun 阅读( ...) 评论( ...) 编辑 收藏
    展开全文
  • 上课时,老师要求的题目。问题很简单,供大家学习。经典的是八皇后问题,我这里设置为n皇后问题,n的值可以自由设置。
  • 这里包含有一份完整的八皇后图形演示的源代码,界面很好,程序比较完善,还有实验报告,具有详细的代码注释。基于VS和EasyX实现,需要事先安装EasyX(非常简便快速,试一下就知道了)。
  • 八皇后(内含动态演示

    千次阅读 2017-09-12 11:03:58
    // 只用C++完成的一个八皇后问题,以图形的形式展示92种结果,以及算法的具体动态演示 几个需要提前注意的问题: 1.由于需要利用C++画图,所以我使用EasyX图形函数库。可以在 EasyX下载 处直接下载,然后识别安装...

    // 只用C++完成的一个八皇后问题,以图形的形式展示92种结果,以及算法的具体动态演示

    // 具体的一些概念可在实验报告文档中查看解释

    一、几个需要提前注意的问题:

    1.由于需要利用C++画图,所以我使用EasyX图形函数库。可以在 EasyX下载 处直接下载,然后识别安装自己的编程软件即可使用。

       在使用此图形库时,需包含 #include "graphics.h" 头文件,依次打开后可以查看到EasyX里面函数的使用(或是安装在桌面也可以查看具体函数及使用)。

    2.几个函数的说明: 延时函数    需要包含头文件 #include <windows.h> ,函数使用  Sleep(1.2 * 1000);//表示在此时暂停1.2秒

                                     清零数组    memset(k, 0, sizeof k); 清除k数组里的所有 //一维 二维 或是二维的某一行都行

                                     暂停函数    system("pause");  

                                     画布的创建与关闭   initgraph(长, 宽);    closegraph();

                                     图片的插入:IMAGE img1; // 定义 IMAGE1 对象
                                                          loadimage(&img1, "D:\\WSX.jpg",400,250); // 读取图片到 img1 对象中
                                                          putimage(801, 0, &img1); // 在左上角的坐标 (801, 0) 位置显示 IMAGE1 对象


    二、核心算法:回溯法的基础代码

    void pan(int curr)//验证curr行的放置
    {
    	if (curr == 8)  //当行数达到边界时,则出现了一个没有冲突符合条件的解
    	{
    		num++; //记录现在满足条件解的个数
    		}
    	else
    	{
    		for (int i = 0; i<8; i++) //循环验证在curr行时,把皇后放置在第i列时
    		{
    			int ok = 1;//标记此行是否放置了皇后
    			memset(k[curr], 0, sizeof k[curr]);//每次重新在此行放置皇后时,清空此行的之前放置的东西
    			k[curr][i] = 1;//标记在curr行i列放置的皇后
    			c[curr] = i;//表示curr行放置皇后的列数
    						for (int j = 0; j<curr; j++)//判断是否与前面的皇后位置有冲突
    			{
    				if (c[curr] == c[j] || curr - c[curr] == j - c[j] || curr + c[curr] == j + c[j])
    				{//判断是否在同一列和是否会在对角线上				
    ok = 0;//如果出现冲突,则将此处的皇后撤掉,表示此行没有放置合适的皇后
    					k[curr][i] = 0;
    					break;//只要出现有冲突的,则跳出判断循环,把此行的皇后放置到下一列
    				}
    			}
    			if (ok)//若是此行已经放置好了合适的皇后
    			{
    				pan(curr + 1);//进行下一行皇后位置的寻找
    						}
    		}
    	}
    }

    只需要在main函数中调用pan(0);函数以及加个自己想要输出的内容函数即可。

      

    三、图形动态化

      只需要使用图形函数编辑,在需要的位置加入延时函数即可。

    四、具体代码

    #define _CRT_SECURE_NO_WARNINGS
    #include "iostream"
    #include "string"
    #include "graphics.h"//其内包含easyx图形函数库
    #include<conio.h>
    #include <cstdlib>
    #include <stdio.h>
    #include <windows.h>//延时函数头文件
    
    using namespace std;
    
    
    int pp = 0;//判断查看怎样的结果,决定了延时位置的不同,则展现结果就不同
    void z0()//pp=0时,查看算法过程的动态演示
    {
    	if (pp == 0)  Sleep(0.4 * 1000);	  //延时函数,延时0.4秒
    }
    
    void z1()//pp=1时,查看符合要求的92种结果
    {
    	if (pp == 1) 	Sleep(1.2 * 1000);
    }
    
    
    int curr;
    int c[8] = { 0 };
    int num = 0;
    char s[5];
    int k[8][8];
    
    void print()
    {
    
    		sprintf(s, "%d", num);//将此时符合条件的解得个数(int)转化格式成为字符串(char s[5])
    
    	outtextxy(1000, 400, s);//将个数输出在屏幕的(1000,400)的位置
    }
    
    
    void pan(int curr)//验证curr行的放置
    {
    	if (curr == 8)  //当行数达到边界时,则出现了一个没有冲突符合条件的解
    	{
    		num++; //记录现在满足条件解的个数
    		print();
    		z1();//延时判断
    	}
    	else
    	{
    		for (int i = 0; i<8; i++) //循环验证在curr行时,把皇后放置在第i列时
    		{
    			int ok = 1;//标记此行是否放置了皇后
    			memset(k[curr], 0, sizeof k[curr]);//每次重新在此行放置皇后时,清空此行的之前放置的东西
    			k[curr][i] = 1;//标记在curr行i列放置的皇后
    			c[curr] = i;//表示curr行放置皇后的列数
    			setfillcolor(BLUE);
    			z0();
    			solidcircle(i * 100 + 50, curr * 100 + 50, 30);//并且将此时位置画上蓝色圆
    			for (int j = 0; j<curr; j++)//判断是否与前面的皇后位置有冲突
    			{
    				if (c[curr] == c[j] || curr - c[curr] == j - c[j] || curr + c[curr] == j + c[j])
    				{//判断是否在同一列和是否会在对角线上
    					
    					setfillcolor(RED);
    					solidcircle(i * 100 + 50, curr * 100 + 50, 30);//若是不合适皇后,则显示红色圆片
    					z0();
    					clearcircle(i * 100 + 50, curr * 100 + 50, 30);
    					ok = 0;//如果出现冲突,则将此处的皇后撤掉,表示此行没有放置合适的皇后
    					k[curr][i] = 0;
    					break;//只要出现有冲突的,则跳出判断循环,把此行的皇后放置到下一列
    				}
    			}
    			if (ok)//若是此行已经放置好了合适的皇后
    			{
    				pan(curr + 1);//进行下一行皇后位置的寻找
    				clearcircle(i * 100 + 50, curr * 100 + 50, 30);//寻找结束之后,清除上一行皇后位置
    			}
    		}
    	}
    }
    
    int main()
    {
    	char p;//判断是否进入程序产看八皇后结果
    	cout << "输入Y进入查看,N退出查看" << endl << "请输入:" << endl;
    	cin >> p;
    	while(p == 'Y')//进入产看选择循环,可多次查看两种结果展示
    	{
    		cout << "请输入1或者0:" << endl;
    		cout << "提示:1查看结果,0查看动态演示" << endl;
    		cin >> pp;
    		memset(k, 0, sizeof k);//清零二维数组
    		initgraph(1200, 800);//定义画布大小1200(长)*800(宽)
    
    		IMAGE img1; // 定义 IMAGE1 对象
    		loadimage(&img1, "D:\\WSX.jpg",400,250); // 读取图片到 img1 对象中
    		putimage(801, 0, &img1); // 在左上角的坐标 (801, 0) 位置显示 IMAGE1 对象
    
    		IMAGE img2; 
    		loadimage(&img2, "D:\\WSX2.jpg", 400, 250); 
    		putimage(801, 250, &img2); 
    
    		IMAGE img3;
    		loadimage(&img3, "D:\\WSX3.jpg", 400, 250); 
    		putimage(801, 500, &img3);
    
    		for (int i = 0; i < 800; i = i + 100)      //创建8*8的白色边框网格棋盘
    		{
    			for (int j = 0; j < 800; j = j + 100)
    			{
    				setfillcolor(WHITE);
    				rectangle(j, i, j + 100, i + 100);
    			}
    		}
    		pan(0);//进入皇后的放置判断
    		//system("pause");
    		closegraph();//关闭画布,继续进入选择
    		system("pause");
    		cout << "继续查看输入Y,退出查看请输入N" << endl << "请输入:" << endl;
    		cin >> p;
    	}
    	
    	cout << "感谢使用!" << endl;
    	system("pause");
    	return 0;
    }

    //选择界面    //过程动态展示   //92种结果查看显示


    展开全文
  • 八皇后动态演示_c/c++

    2018-11-13 20:11:05
    八皇后动态演示,采用图形界面的方式进行演示,可以使用vs之类打开
  • 八皇后演示

    2013-01-10 20:17:20
    用c++6.0写的八皇后,可以动态演示,中间可以控制,图像化显示
  • 八皇后问题是个历史挺悠久的问题,马克斯·贝瑟尔于1848年提出,具体参照百度百科的说明:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆...

    八皇后问题是个历史挺悠久的问题,马克斯·贝瑟尔于1848年提出,具体参照百度百科的说明:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

    在解决这一问题上回溯法变得很有用,回溯法形象点说有点像走迷宫,当这条路走不通时,退回上一次的状态,寻找另一个方向继续走下去。

    在程序设计过程中,过程型语言讲究模块化设计,对象型语言则主张一切皆对象,愚以为二者并非完全对立的两种状态,准确点说应该是,在将一切对象化的过程,问题的解决要模块化,以八皇后问题为例,我们可以设计一个EightQueen类,此为对象化,而EightQueen类内部的问题解决过程则要遵循模块化,解决八皇后问题首先我们需要一个可以判断在某个位置放皇后是否符合条件的函数,然后还需要可以进行回溯于递归的函数,如果还想动态化地演示过程,则还需要一个输出函数,这就是模块化的过程。(这段纯属废话了)

    进入正题,判断皇后都不在同意列上很简单,判断不在同一对角线上也不难,不过分为两种情况:正斜对角线和反斜对角线,判断条件分别为:(r1+c1)==(r2+c2),(r1-c1)==(r2-c2),知道了判断条件,就可以进行函数设计了(我定义了一个全局数组queen用来记录每个皇后的位置,还定义了全局变量_count用于记录所有情况的总数,但我并没有将棋盘可以翻转这个因素考虑进代码,所以最后可能会出现一种摆法转个90度就与另一种摆法相同的结果,在这里不直接用count而用_count的原因是命名空间std里有count的定义了,编译会报错):

     1 bool Is_meet(int row,int col) {
     2     for (int i = 0;i < row;i++) {
     3         if (col == queen[i])
     4             return 0;
     5         if ((row + col) == (i + queen[i]))
     6             return 0;
     7         if ((row - col) == (i - queen[i]))
     8             return 0;
     9     }
    10     queen[row] = col;
    11     return 1;
    12 }

    接下来是承当回溯与递归职能的函数的设计,比较好理解,就不进行过多解释:

     1 void findQueenPosition(int row) {
     2     for (int j_col = 0;j_col < 8;j_col++) {    //j_col变量用于遍历每一列
     3         if (Is_meet(row, j_col)) {
     4             if (row == 7) {            //如果已经是最后一行了就可以退出循环
     5                 break;
     6             }
     7             else {
     8                 findQueenPosition(row + 1);  //进行递归
     9             }
    10         }
    11     }
    12     queen[row] = -1;
    13     return;
    14 }

    为了在控制台动态的演示出过程,我们需设计一下display()函数,在显示过程中为了让我们可以捕捉到变化,我们需调用Sleep()库函数将停留时间变长,Sleep()库函数调用需包含头文件<window.h>,同时也为了实现动态,我们要将旧的输出清零,这就需要用到system("cls")语句,该语句可以将控制台所有输出清零,代码如下:

     1 void display() {
     2     system("cls");
     3     cout << "八皇后问题动态演示:" << endl;
     4     for (int i = 0;i < 8;i++) {
     5         if (queen[i] == -1) {
     6             for (int j = 0;j < 8;j++)
     7                 cout << ". ";
     8             cout << endl;
     9         }
    10         else {
    11             for (int j = 0;j < queen[i];j++) {
    12                 cout << ". ";
    13             }
    14             cout << "# ";
    15             for (int k = queen[i] + 1;k < 8;k++) {
    16                 cout << ". ";
    17             }
    18             cout << endl;
    19         }
    20     }
    21     Sleep(100);//停留时间可以自行更改
    22 }

    既然加入了输出函数,那findQueenPosition()函数也要做出些许变化,修改完如下:

     1 void findQueenPosition(int row) {
     2     for (int j_col = 0;j_col < 8;j_col++) {
     3         if (Is_meet(row, j_col)) {
     4             if (row == 7) {
     5                 display();
     6                 cout << "Case " << ++_count << "." << endl;
     7                 Sleep(3000);//停留时间可以自行更改
     8                 break;
     9             }
    10             else {
    11                 display();
    12                 findQueenPosition(row + 1);
    13             }
    14         }
    15     }
    16     queen[row] = -1;
    17     return;
    18 }

    到这里这个程序就基本完成了,为了便于运行,我将完整代码贴在下面:

     1 #include <iostream>
     2 #include <windows.h>
     3 using namespace std;
     4 
     5 int queen[8]={-1,-1,-1,-1,-1,-1,-1,-1};
     6 int _count = 0;
     7 
     8 bool Is_meet(int row,int col) {
     9     for (int i = 0;i < row;i++) {
    10         if (col == queen[i])
    11             return 0;
    12         if ((row + col) == (i + queen[i]))
    13             return 0;
    14         if ((row - col) == (i - queen[i]))
    15             return 0;
    16     }
    17     queen[row] = col;
    18     return 1;
    19 }
    20 
    21 void display() {
    22     system("cls");
    23     cout << "八皇后问题动态演示:" << endl;
    24     for (int i = 0;i < 8;i++) {
    25         if (queen[i] == -1) {
    26             for (int j = 0;j < 8;j++)
    27                 cout << ". ";
    28             cout << endl;
    29         }
    30         else {
    31             for (int j = 0;j < queen[i];j++) {
    32                 cout << ". ";
    33             }
    34             cout << "# ";
    35             for (int k = queen[i] + 1;k < 8;k++) {
    36                 cout << ". ";
    37             }
    38             cout << endl;
    39         }
    40     }
    41     Sleep(100);//停留时间可以自行更改
    42 }
    43 
    44 void findQueenPosition(int row) {
    45     for (int j_col = 0;j_col < 8;j_col++) {
    46         if (Is_meet(row, j_col)) {
    47             if (row == 7) {
    48                 display();
    49                 cout << "Case " << ++_count << "." << endl;
    50                 Sleep(3000);//停留时间可以自行更改
    51                 break;
    52             }
    53             else {
    54                 display();
    55                 findQueenPosition(row + 1);
    56             }
    57         }
    58     }
    59     queen[row] = -1;
    60     return;
    61 }
    62 
    63 int main() {
    64     findQueenPosition(0);
    65     cout << "The total case of eight queen problem is " << _count << endl;
    66     return 0;
    67 }

     

     

    经过简单的测试,代码应该是没问题了,但仍可能会有错误出现,欢迎指正。

    转载于:https://www.cnblogs.com/TangMoon/p/7643707.html

    展开全文
  • 八皇后问题(难度系数:***) 八皇后问题是一个古老而著名的问题,它是回溯法的典型例题。该问题是德国著名数学家高斯于1850年提出的:在8行8列的国际象棋棋盘上摆放着八个皇后。若两个皇后位于同一行、同一列或同一...
  • 八皇后问题的解和动态演示过程

    千次阅读 2017-09-13 19:18:09
    八皇后问题是回溯法的经典问题,我从另一方面演示了求解八皇后的过程和结果。其中主要用到的是一个图形库:easyx,可以上网搜索下载下来,不过只能装在vc和vs上,dev目前装不了。装好之后就可以查看它所包含的函数了...
  • 算法 数据结构课程设计(C++) 八皇后动态演示原代码
  • 内容是关于“八皇后问题的求解动态图形演示。这个软件采用多线程设计,包含了递归回溯与非递归回溯两种算法,还可随时调整演示速度,界面共有五种前景和五种背景图形。包含所有源程序和资源文件。 以下是软件截图...
  • 八皇后问题 Eight Queen's Problem八皇后问题演示系统
  • 八皇后问题解的演示 多种解直接看 八皇后多解演示的很明白 可以试着自己写下
  • 资源包括了数据结构课程设计八皇后动态演示原代码,其中加有详细得注释,能后运行。以测试过了。绝对经典。
  • 八皇后VC图形演示八皇后VC图形演示八皇后VC图形演示八皇后VC图形演示八皇后VC图形演示
  • 八皇后 VC++图形演示

    2010-06-21 16:58:21
    八皇后VC++图形演示,学VC界面编程,在VC在线上狂看教程,觉得有所长进
  • 八皇后问题演示

    2008-03-16 22:28:57
    本软件运行此程序,可使用安装程序,序列号任意。 本程序演示八皇后问题的求解过程。 不安装也可使用,直接运行EightQueen.exe即可。
  • 数据结构八皇后问题的VC图形演示的源代码!
  • 八皇后动态图形的实现 ... 对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果。下面是笔者用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。
  • 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题...
  • 人工智能 八皇后问题演示.rar 人工智能 八皇后问题演示.rar
  • Delphi制作的八皇后演示程序,可用于演示或教学 注:根据网上程序改编 可以免费当作课件使用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 604
精华内容 241
关键字:

八皇后问题动态演示