Nクイーン問題の回答をパッパッと表示するiPhoneアプリ(C++)のサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
#include <iostream>
#include <list>
using namespace std;
@class ViewController;
class QueensSolver {
public:
static const int N = 5;
int position[N];
void solve(int);
private:
bool isSafe(int, int);
};
bool QueensSolver::isSafe(int queen_number, int row_position) {
for (int i=0; i<queen_number; i++) {
int other_row_pos = position[i];
if (other_row_pos == row_position ||
other_row_pos == row_position – (queen_number – i) ||
other_row_pos == row_position + (queen_number – i))
return false;
}
return true;
}
void QueensSolver::solve(int k) {
if (k == N) {
if(k != 0)[[NSNotificationCenter defaultCenter] postNotificationName:@”mymessage” object:@(–1)];
for (int i=0; i<N; i++)
[[NSNotificationCenter defaultCenter] postNotificationName:@”mymessage” object:@(position[i])];
} else {
for (int i=0; i<N; i++) {
if (isSafe(k, i)) {
position[k] = i;
solve(k + 1);
}
}
}
}
@interface ViewController ()
@property (nonatomic) std::shared_ptr<QueensSolver> cppClass;
@property (nonatomic, strong) NSMutableArray *boardMap;
@property (nonatomic) int counter;
@property (nonatomic) int column;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor blackColor];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(solvePosition:)
name:@”mymessage”
object:nil];
[self createChessboard];
}
– (void)createChessboard {
self.boardMap = [NSMutableArray array];
for (int i=0; i<25; i++) {
float s = 50;
float x = (i % 5) * s + 60;
float y = (i / 5) * s + 50;
UIView *v = [[UIView alloc] initWithFrame:CGRectMake(x, y, s * 0.9, s * 0.9)];
v.backgroundColor = i % 2 == 0 ? [UIColor whiteColor] : [UIColor brownColor];
[self.view addSubview:v];
[self.boardMap addObject:v];
}
}
#define QUEEN_TAG 1
– (void)solvePosition:(NSNotification *)note {
++self.counter;
if ([note.object intValue] < 0) {
self.counter += 5;
self.column = 0;
float dt = 0.1 * (float)self.counter;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(dt * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
for (UIView *v in self.view.subviews) {
if (v.tag == QUEEN_TAG) {
[v removeFromSuperview];
}
}
});
} else {
__block int col = self.column;
float dt = 0.1 * (float)self.counter;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(dt * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
UIView *queen = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 30, 30)];
queen.tag = QUEEN_TAG;
queen.layer.cornerRadius = 10;
queen.backgroundColor = [UIColor blackColor];
int no = [note.object intValue];
queen.center = ((UIView *)self.boardMap[no + 5 * col]).center;
[self.view addSubview:queen];
});
self.column++;
}
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
std::shared_ptr<QueensSolver> cppClass(new QueensSolver());
cppClass->solve(0);
}
@end