[cpp]
八皇後問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。計算機發明後，有多種方法可以解決此問題。
我們用圖形來解決之、
看效果
[cpp]
#pragma once
#include<math.h>
namespace Queen {
using namespace System;
using namespace System::ComponentModel;
using namespace System::Collections;
using namespace System::Windows::Forms;
using namespace System::Data;
using namespace System::Drawing;
/// <summary>
/// Form1 摘要
///
/// 警告: 如果更改此類的名稱，則需要更改
/// 與此類所依賴的所有 .resx 文件關聯的托管資源編譯器工具的
/// “資源文件名”屬性。否則，
/// 設計器將不能與此窗體的關聯
/// 本地化資源正確交互。
/// </summary>
public ref class Form1 : public System::Windows::Forms::Form
{
public:
Form1(void)
{
InitializeComponent();
//
//TODO: 在此處添加構造函數代碼
//
}
protected:
/// <summary>
/// 清理所有正在使用的資源。
/// </summary>
~Form1()
{
if (components)
{
delete components;
}
}
private: System::Windows::Forms::ComboBox^ comboBox1;
private: System::Windows::Forms::TextBox^ textBox1;
private: System::Windows::Forms::Button^ button1;
private: System::Windows::Forms::Label^ label1;
private: System::Windows::Forms::Label^ label2;
private:
/// <summary>
/// 必需的設計器變量。
/// </summary>
System::ComponentModel::Container ^components;
#pragma region Windows Form Designer generated code
/// <summary>
/// 設計器支持所需的方法 - 不要
/// 使用代碼編輯器修改此方法的內容。
/// </summary>
void InitializeComponent(void)
{
this->comboBox1 = (gcnew System::Windows::Forms::ComboBox());
this->textBox1 = (gcnew System::Windows::Forms::TextBox());
this->button1 = (gcnew System::Windows::Forms::Button());
this->label1 = (gcnew System::Windows::Forms::Label());
this->label2 = (gcnew System::Windows::Forms::Label());
this->SuspendLayout();
//
// comboBox1
//
this->comboBox1->FormattingEnabled = true;
this->comboBox1->Location = System::Drawing::Point(134, 602);
this->comboBox1->Name = L"comboBox1";
this->comboBox1->Size = System::Drawing::Size(121, 20);
this->comboBox1->TabIndex = 0;
this->comboBox1->SelectedIndexChanged += gcnew System::EventHandler(this, &Form1::comboBox1_SelectedIndexChanged);
//
// textBox1
//
this->textBox1->Location = System::Drawing::Point(321, 602);
this->textBox1->Name = L"textBox1";
this->textBox1->Size = System::Drawing::Size(60, 21);
this->textBox1->TabIndex = 1;
this->textBox1->Text = L"6";
//
// button1
//
this->button1->BackColor = System::Drawing::SystemColors::Control;
this->button1->Location = System::Drawing::Point(396, 602);
this->button1->Name = L"button1";
this->button1->Size = System::Drawing::Size(75, 20);
this->button1->TabIndex = 2;
this->button1->Text = L"確定";
this->button1->UseVisualStyleBackColor = false;
this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System::Drawing::Point(265, 607);
this->label1->Name = L"label1";
this->label1->Size = System::Drawing::Size(53, 12);
this->label1->TabIndex = 3;
this->label1->Text = L"輸入Ｎ：";
//
// label2
//
this->label2->AutoSize = true;
this->label2->Location = System::Drawing::Point(91, 606);
this->label2->Name = L"label2";
this->label2->Size = System::Drawing::Size(41, 12);
this->label2->TabIndex = 3;
this->label2->Text = L"方案：";
//
// Form1
//
this->AutoScaleDimensions = System::Drawing::SizeF(6, 12);
this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
this->ClientSize = System::Drawing::Size(592, 623);
this->Controls->Add(this->label2);
this->Controls->Add(this->label1);
this->Controls->Add(this->button1);
this->Controls->Add(this->textBox1);
this->Controls->Add(this->comboBox1);
this->Name = L"Form1";
this->Text = L"Form1";
this->ResumeLayout(false);
this->PerformLayout();
}
#pragma endregion
static int N=6,num=0;
static array<int>^ site=gcnew array<int>(20);
static array<int,2>^ result=gcnew array<int,2>(1000,1000);
static array<System::Windows::Forms::Button^,2>^ button=gcnew array<System::Windows::Forms::Button^,2>(100,100);
int Isable(int row)
{
for(int i=1;i<row;i++)
if((site[i]==site[row])||(abs(site[i]-site[row])==(row-i)))
return 0;
return 1;
}
void Queen(int row)
{
for(int cols=1;cols<=N;cols++)
{
site[row]=cols;
if(Isable(row))
{
if(row==N)
{
num++;
this->comboBox1->Items->Add("方案 "+num);
for(int i=1;i<=N;i++)
result[num,i]=site[i];
return;
}
Queen(row+1);
}
}
}
void Erase()
{
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
this->Controls->Remove(this->button[i,j]);
this->comboBox1->Items->Clear();
N=Convert::ToInt16(this->textBox1->Text);
num=0;
for(int i=1;i<=N;i++)
site[i]=0;
}
void Show()
{
int a;
a=600/N;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
this->button[i,j] = (gcnew System::Windows::Forms::Button());
this->button[i,j]->Location = System::Drawing::Point((i-1)*a, (j-1)*a);
this->button[i,j]->Name = L"button1";
this->button[i,j]->Size = System::Drawing::Size(a, a);
this->button[i,j]->TabIndex = 2;
this->button[i,j]->Text = L"確定";
this->button[i,j]->UseVisualStyleBackColor = true;
this->Controls->Add(this->button[i,j]);
}
}
void ShowQueen()
{
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
//this->button[i,j]->BackColor=System::Drawing::SystemColors::Control;
this->button[i,j]->UseVisualStyleBackColor = true;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
if(result[this->comboBox1->SelectedIndex+1,i]==j)
this->button[i,j]->BackColor=System::Drawing::Color::Red;
}
}
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
Erase();
Show();
Queen(1);
}
private: System::Void comboBox1_SelectedIndexChanged(System::Object^ sender, System::EventArgs^ e) {
ShowQueen();
}
};
}
