一、用枚举法实现
思路：枚举所有的可能来，可以看成一个树形结构，到了叶子节点再去判断是不是可行解
二、用回溯法实现
思路：在枚举法的基础上先进行判断是不是可以放的点，再去进行递归
三、实现用了2种方法，一个是一维数组，一个是二维数组。一维数组中数组下标为皇后坐标的行，数组中对应的值为皇后坐标的列
四、以下是代码部分，并且实现了动态寻找解（ios界面）
代码在最下面，可供参考
#include"iostream"
using namespace std;
int cnt=0;
int n;
//*********************蛮力法
int judge(int a[])
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(abs(a[j] - a[i]) == abs(j-i)||a[j] == a[i])
return false;
}
}
return true;
}
void queen(int a[],int temp)
{
if(temp==n)
{
if(judge(a))
{
cnt++;
//cout<<"为八皇后的解"<<endl;
}
}
else
{
for(int i=0;i<n;i++)
{
a[temp]=i;
queen(a, temp+1);
}
}
}
//**********************************
//回溯法
bool CanPlace(int row,int col,int **chess)
{
for(int i=0;i<n;i++){
if(chess[i][col]==1){//check col
return false;
}
if(chess[row][i]==1){//check row
return false;
}
}
for(int i=0;i<n;i++){//check left-front
if(row-i<0||col-i<0){
break;
}
if(chess[row-i][col-i]==1){
return false;
}
}
for(int i=0;i<n;i++){//check right-front
if(row-i<0||col+i>n-1){
break;
}
if(chess[row-i][col+i]==1){
return false;
}
}
for(int i=0;i<n;i++){//check left-below
if(row+i>n-1||col-i<0){
break;
}
if(chess[row+i][col-i]==1){
return false;
}
}
for(int i=0;i<n;i++){//check right-below
if(row+i>n-1||col+i>n-1){
break;
}
if(chess[row+i][col+i]==1){
return false;
}
}
return true;
}
//回溯法递归
void EightQueen(int row,int col,int **chess)
{
//temp 2Darray
int **chess2=new int*[n];
for(int i=0;i<n;i++)
chess2[i]=new int[n];
//put last scene to temp 2Darray
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
chess2[i][j]=chess[i][j];
}
}
if(row==n)
{
cnt++;
}
else
{
for(int j=0;j<n;j++)
{
if(CanPlace(row, j, chess2))
{
chess2[row][j]=1;
EightQueen(row+1, j, chess2);
chess2[row][j]=0;
}
}
}
}
int main()
{
cout<<"请输入n皇后"<<endl;
cin>>n;
//********************蛮力法
// int *a=new int[n];
//// int a[8]={4,2,7,3,6,8,5,1};
// double start=clock();
// queen(a, 0);
// double end=clock();
// printf("%f",end-start);
// cout<<endl;
//*********************
//回溯法************
int **chess=new int*[n];
for(int i=0;i<n;i++)
chess[i]=new int[n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
chess[i][j]=0;
double start=clock();
EightQueen(0, 0, chess);
double end=clock();
printf("%f\n",end-start);
//******************
return 1;
}
八皇后02.gif
[图片上传中...(八皇后.gif-9e5819-1509702099883-0)]
五、下面是枚举法实现ios动态寻找解的界面
实现的语言：oc和c++
//
// ViewController.m
// 八皇后问题
//
// Created by tao on 2017/10/27.
// Copyright © 2017年 LiuTao. All rights reserved.
//
#import "ViewController.h"
#include<iostream>
using namespace std;
@interface ViewController ()
@property(nonatomic,strong)NSMutableArray *array;
@property(nonatomic,assign)int g_count;
@property(nonatomic,assign)int n;
@property(nonatomic,strong)UILabel *l;
@property(nonatomic,strong)UILabel *text;
@end
@implementation ViewController
-(NSMutableArray *)array
{
if(_array==nil)
{
_array=[NSMutableArray array];
}
return _array;
}
- (void)viewDidLoad {
[super viewDidLoad];
[self start];
cout<<_g_count<<endl;
}
-(void)start
{
_g_count=0;
_n=8;
_l=[[UILabel alloc]init];
self.view.backgroundColor=[UIColor grayColor];
int i,j;
for(i=0;i<_n;i++)
{
for(j=0;j<_n;j++)
{
UILabel *label=[[UILabel alloc]initWithFrame:CGRectMake(30+j*40, 80+i*40, 40, 40)];
label.layer.borderColor=[[UIColor blackColor]CGColor];
label.layer.borderWidth=1;
label.backgroundColor=[UIColor whiteColor];
label.layer.masksToBounds=YES;
label.tag=i*_n+j+1;
label.userInteractionEnabled=YES;
[self.array addObject:label];
[self.view addSubview:label];
}
}
[self begin];
}
-(void)begin
{
_text=[[UILabel alloc]initWithFrame:CGRectMake(40, 500, 300, 100)];
_text.backgroundColor=[UIColor whiteColor];
_text.text=@"八皇后第一次解";
_text.textAlignment=NSTextAlignmentCenter;
_text.font=[UIFont systemFontOfSize:20];
_text.textColor=[UIColor blackColor];
[self.view addSubview:_text];
dispatch_async(dispatch_get_global_queue(0, 0), ^{
int *a=new int[8];
[self queen:a and1:0 ];
});
}
-(int) check:(int *)a and1:(int)n
{
int i,j;
for(i=2;i<=n;i++)
{
for(j=1;j<=i-1;j++)
{
if(a[i]==a[j]||(abs(a[i]-a[j])==abs(i-j)))
return 0;
}
}
return 1;
}
-(bool) judge:(int*)a
{
for(int i=0;i<8;i++)
{
for(int j=i+1;j<8;j++)
{
if(abs(a[j] - a[i]) == abs(j-i)||a[j] == a[i])
return false;
}
}
return true;
}
-(void)queen:(int*)a and1:(int)temp
{
if(temp==8)
{
if([self judge:a])
{
dispatch_async(dispatch_get_main_queue(), ^{
NSString *str=[NSString stringWithFormat:@"八皇后的第%d次解",_g_count];
_text.text=str;
[NSThread sleepForTimeInterval:2];
});
_g_count++;
}
}
else
{
for(int i=0;i<8;i++)
{
a[temp]=i;
dispatch_async(dispatch_get_main_queue(), ^{
_l=[_array objectAtIndex:temp*8+i];
_l.backgroundColor=[UIColor blackColor];
});
[NSThread sleepForTimeInterval:0.2];
[self queen:a and1:temp+1];
dispatch_async(dispatch_get_main_queue(), ^{
_l=[_array objectAtIndex:temp*8+i];
_l.backgroundColor=[UIColor whiteColor];
});
}
}
}
- (void)didReceiveMemoryWarning {
[super didReceiveMemoryWarning];
// Dispose of any resources that can be recreated.
}
@end
六、下面是回溯法实现ios动态寻找解的界面
实现的语言：oc和c++
八皇后.gif
//
// ViewController.m
// 八皇后问题
//
// Created by tao on 2017/10/27.
// Copyright © 2017年 LiuTao. All rights reserved.
//
#import "ViewController.h"
#include<iostream>
using namespace std;
@interface ViewController ()
@property(nonatomic,strong)NSMutableArray *array;
@property(nonatomic,assign)int g_count;
@property(nonatomic,assign)int n;
@property(nonatomic,strong)UILabel *l;
@property(nonatomic,strong)UILabel *text;
@end
@implementation ViewController
-(NSMutableArray *)array
{
if(_array==nil)
{
_array=[NSMutableArray array];
}
return _array;
}
- (void)viewDidLoad {
[super viewDidLoad];
[self start];
}
-(void)start
{
_g_count=1;
_n=8;
_l=[[UILabel alloc]init];
self.view.backgroundColor=[UIColor grayColor];
int i,j;
for(i=0;i<_n;i++)
{
for(j=0;j<_n;j++)
{
UILabel *label=[[UILabel alloc]initWithFrame:CGRectMake(30+j*40, 80+i*40, 40, 40)];
label.layer.borderColor=[[UIColor blackColor]CGColor];
label.layer.borderWidth=1;
label.backgroundColor=[UIColor whiteColor];
label.layer.masksToBounds=YES;
label.tag=i*_n+j+1;
label.userInteractionEnabled=YES;
[self.array addObject:label];
[self.view addSubview:label];
}
}
[self begin];
}
-(void)begin
{
_text=[[UILabel alloc]initWithFrame:CGRectMake(40, 500, 300, 100)];
_text.backgroundColor=[UIColor whiteColor];
_text.text=@"八皇后第一次解";
_text.textAlignment=NSTextAlignmentCenter;
_text.font=[UIFont systemFontOfSize:20];
_text.textColor=[UIColor blackColor];
[self.view addSubview:_text];
dispatch_async(dispatch_get_global_queue(0, 0), ^{
int **chess=new int*[_n];
for(int i=0;i<_n;i++)
chess[i]=new int[_n];
for(int i=0;i<_n;i++)
for(int j=0;j<_n;j++)
chess[i][j]=0;
[self EightQueen:0 and1:0 and2:chess];
});
}
-(bool) CanPlace:(int)row and1:(int)col and2:(int **)chess
{
for(int i=0;i<_n;i++){
if(chess[i][col]==1){//check col
return false;
}
if(chess[row][i]==1){//check row
return false;
}
}
for(int i=0;i<_n;i++){//check left-front
if(row-i<0||col-i<0){
break;
}
if(chess[row-i][col-i]==1){
return false;
}
}
for(int i=0;i<_n;i++){//check right-front
if(row-i<0||col+i>_n-1){
break;
}
if(chess[row-i][col+i]==1){
return false;
}
}
for(int i=0;i<_n;i++){//check left-below
if(row+i>_n-1||col-i<0){
break;
}
if(chess[row+i][col-i]==1){
return false;
}
}
for(int i=0;i<_n;i++){//check right-below
if(row+i>_n-1||col+i>_n-1){
break;
}
if(chess[row+i][col+i]==1){
return false;
}
}
return true;
}
-(void) EightQueen:(int)row and1:(int)col and2:(int **)chess
{
//temp 2Darray
int **chess2=new int*[_n];
for(int i=0;i<_n;i++)
chess2[i]=new int[_n];
//put last scene to temp 2Darray
for(int i=0;i<_n;i++)
{
for(int j=0;j<_n;j++)
{
chess2[i][j]=chess[i][j];
}
}
if(row==_n)
{
_g_count++;
dispatch_async(dispatch_get_main_queue(), ^{
NSString *str=[NSString stringWithFormat:@"八皇后的第%d次解",_g_count];
_text.text=str;
[NSThread sleepForTimeInterval:2];
});
cout<<_g_count<<endl;
}
else
{
for(int j=0;j<_n;j++)
{
if([self CanPlace:row and1:j and2:chess2])
{
chess2[row][j]=1;
dispatch_async(dispatch_get_main_queue(), ^{
_l=[_array objectAtIndex:row*_n+j];
_l.backgroundColor=[UIColor blackColor];
// [NSThread sleepForTimeInterval:1];
});
[NSThread sleepForTimeInterval:0.2];
[self EightQueen:row+1 and1:j and2:chess2];
chess2[row][j]=0;
dispatch_async(dispatch_get_main_queue(), ^{
_l=[_array objectAtIndex:row*_n+j];
_l.backgroundColor=[UIColor whiteColor];
});
[NSThread sleepForTimeInterval:0.2];
}
}
}
}
- (void)didReceiveMemoryWarning {
[super didReceiveMemoryWarning];
// Dispose of any resources that can be recreated.
}
@end
网友评论