前回のあらすじ： Objective-C はじめた。
でも、始めたばかりでどこから手をつけてよいのか分からない。
行きつけのジュンク堂書店をひたすら徘徊した結果、わかりやすそうな本を見つけたのでつい買ってしまった。
 |
| 『世界一わかりやすい Objective‐C プログラミングの授業』 ¥2,480 （税別） |
iPhone アプリを製作できる環境が調っておらず、今のところ言語仕様そのものを学ぶしかないので、混じりっ気のない入門書の中でできるだけ解り易いものを買ってきた。さすが（自称）世界一わかりやすいというだけあって、即日読了。
ただ、ぼくの頭が悪いせいで、わかったようなわからないような。
理解度を確かめるために、先日書いた《ナンバープレイスを解答するプログラム》を Objective-C に移植してみた。
まずは第一版。ほとんど C のスタイルである。
#import <Foundation/Foundation.h>
#define FIELD_SIZE 9
#define BLOCK_SIZE 3
unsigned char field[FIELD_SIZE * FIELD_SIZE];
void printField() {
int i, j;
for(i = 0; i < FIELD_SIZE; ++i) {
for(j = 0; j < FIELD_SIZE; ++j) {
if(field[i*FIELD_SIZE + j] == 0)
NSLog(@" ");
else NSLog(@"%d ", field[i*FIELD_SIZE + j]);
}
NSLog(@"\n");
}
NSLog(@"\n\n");
}
// 暫定的な答えチェック関数。
// 引数：
// int loc ... フィールドの対象セル
// int num ... 代入候補の数値
// 戻り値：
// YES ... 妥当な場合
// NO ... 妥当ではない場合
BOOL checkAnswer(int loc, int num) {
int row = loc / FIELD_SIZE;
int col = loc % FIELD_SIZE;
int i, j;
int index;
// 行と列のチェック
for(i = 0; i < FIELD_SIZE; ++i) {
// 行のチェック
index = row * FIELD_SIZE + i;
// 同じ数字が見つかったらエラー
if(field[index] == num)
return NO;
// 列のチェック
index = i * FIELD_SIZE + col;
// 同じ数字が見つかったらエラー
if(field[index] == num)
return NO;
}
// ブロックのチェック
int blockRow = row / BLOCK_SIZE * BLOCK_SIZE;
int blockCol = col / BLOCK_SIZE * BLOCK_SIZE;
for(i = blockRow; i < blockRow + BLOCK_SIZE; ++i) {
for(j = blockCol; j < blockCol + BLOCK_SIZE; ++j) {
index = i * FIELD_SIZE + j;
if(field[index] == num)
return NO;
}
}
return YES;
}
// 数独を解き、答えを出力する関数。
// 引数：
// int loc ... フィールドの対象セル
// （最初は0を渡す）
void solve(int loc) {
int i;
// 答えが見つかった場合はそれを出力
if (loc == FIELD_SIZE * FIELD_SIZE)
return printField();
// もともと数字が入っている場合は飛ばして次へ
if (field[loc] != 0) return solve(loc+1);
// 空欄の場合は力ずくでサーチ
for(i = 1; i < FIELD_SIZE + 1; ++i) {
// 入れようとしている数字に重複がなければ…
if(checkAnswer(loc, i)) {
field[loc] = i; // その数字を解と仮定して
solve(loc+1); // 次へ進む
field[loc] = 0; // ダメなら空欄に戻す
}
}
}
int main() {
NSAutoreleasePool *pool
= [[NSAutoreleasePool alloc] init];
int i;
// フィールド初期化
for(i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i)
field[i] = 0;
/* ここで問題を設定してね♪ */
// 問題出力
NSLog(@"【Question】\n");
printField();
// 解く。
NSLog(@"【Answer】\n");
solve(0);
[pool release];
return 0;
}
このプログラムは、もちろん正常にコンパイルできる。……が、以前のソースとほとんど変わっていないため、あまり勉強した気にならない。
【オブジェクト指向でGO!!】
上記ソースをクラスベースに書き換えてみる事にする。
どう考えても、まず《フィールドの状態を管理するクラス》が必要だ。
このクラスのインスタンス変数は、フィールドの状態を表現する 1 次元配列とする。
メソッドは基本的なアクセサと description メソッド（Java における toString に相当）を定義する。
#import <Foundation/Foundation.h>
// 定数マクロ（これホントはよくないんだよねー）
#define FIELD_SIZE 9
#define BLOCK_SIZE 3
// ===============================================
// Field クラス（インタフェース部）
// ===============================================
@interface Field : NSObject {
unsigned char field[FIELD_SIZE * FIELD_SIZE];
}
// イニシャライザ
- (id) initWithFieldState: (unsigned char [])data;
// インスタンスの文字列表現
- (NSMutableString *) description;
// フィールドの状態を表す1次元配列を取得
- (unsigned char *) field;
@end
// ===============================================
// Field クラス（実装部）
// ===============================================
@implementation Field
// イニシャライザ
- (id) initWithFieldState: (unsigned char [])data {
int i;
self = [super init];
if (self != nil) {
for(i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i) {
// ちゃんと適正な範囲かどうかをチェック
if (data[i] <= FIELD_SIZE) {
field[i] = data[i];
} else {
field[i] = 0;
}
}
}
return self;
}
// インスタンスの文字列表現
- (NSMutableString *) description {
NSMutableString *retVal = [NSMutableString stringWithCapacity:1];
int i, j, index;
for(i = 0; i < FIELD_SIZE; ++i) {
for(j = 0; j < FIELD_SIZE; ++j) {
index = i * FIELD_SIZE + j;
if(field[index] == 0)
[retVal appendString:@" "];
else
[retVal appendString:
[NSString stringWithFormat:
@"%d ", field[index]]];
}
[retVal appendString:@"\n"];
}
[retVal appendString:@"\n"];
return retVal;
}
// フィールドの状態を表す1次元配列を取得
- (unsigned char *) field {
return field;
}
@end
次に、解の探索を行うクラス NumberPlace を定義する。
// ===============================================
// NumberPlace クラス（インタフェース部）
// ===============================================
@interface NumberPlace : NSObject {
// 一時用
unsigned char field[FIELD_SIZE * FIELD_SIZE];
}
// イニシャライザ
- (id) initWithField: (Field *)question;
// フィールドの状態を出力する
- (void) printField;
// 数独を解き、答えを列挙する再帰関数
- (void) solve;
- (void) solve:(int)loc;
// 暫定的な答えチェック関数
- (BOOL) checkAnswer:(int)loc number:(int)num;
@end
// ===============================================
// NumberPlace クラス（実装部）
// ===============================================
@implementation NumberPlace
// イニシャライザ
- (id) initWithField: (Field *)question {
int i;
self = [super init];
if(self != nil) {
for(i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i)
field[i] = *([question field]+i);
}
return self;
}
// フィールドの状態を出力する
- (void) printField {
int i, j, index;
for(i = 0; i < FIELD_SIZE; ++i) {
for(j = 0; j < FIELD_SIZE; ++j) {
index = i*FIELD_SIZE + j;
if(field[index] == 0)
printf(" ");
else printf("%d ", field[index]);
}
printf("\n");
}
printf("\n\n");
return;
}
// 数独を解き、答えを列挙する再帰メソッド
- (void) solve {
printf("【問題】\n");
[self printField];
printf("【解答】\n");
[self solve:0];
}
- (void) solve:(int)loc {
int i;
// 答えが見つかった場合はそれを出力
if (loc == FIELD_SIZE * FIELD_SIZE) {
[self printField];
return;
}
// もともと数字が入っている場合は飛ばして次へ
if (field[loc] != 0) {
[self solve:loc+1];
return;
}
// 空欄の場合は力ずくでサーチ
for(i = 1; i < FIELD_SIZE + 1; ++i) {
// 入れようとしている数字に重複がなければ…
if([self checkAnswer:loc number:i]) {
field[loc] = i; // その数字を解と仮定して
[self solve:loc+1]; // 次へ進む
field[loc] = 0; // ダメなら空欄に戻す
}
}
}
// 暫定的な答えチェック関数
- (BOOL) checkAnswer:(int)loc number:(int)num {
int row = loc / FIELD_SIZE;
int col = loc % FIELD_SIZE;
int i, j;
int index;
// 行と列のチェック
for(i = 0; i < FIELD_SIZE; ++i) {
// 行のチェック
index = row * FIELD_SIZE + i;
// 同じ数字が見つかったらエラー
if(field[index] == num)
return NO;
// 列のチェック
index = i * FIELD_SIZE + col;
// 同じ数字が見つかったらエラー
if(field[index] == num)
return NO;
}
// ブロックのチェック
int blockRow = row / BLOCK_SIZE * BLOCK_SIZE;
int blockCol = col / BLOCK_SIZE * BLOCK_SIZE;
for(i = blockRow; i < blockRow + BLOCK_SIZE; ++i) {
for(j = blockCol; j < blockCol + BLOCK_SIZE; ++j) {
index = i * FIELD_SIZE + j;
if(field[index] == num)
return NO;
}
}
return YES;
}
@end
このクラスは、イニシャライザに Field 型の問題を渡し、solve メソッドを呼び出すと解の探索及び列挙を行ってくれる。
このまで作って気付いたのだが、かなりの冗長設計である。 Field クラスが無くとも解の探索は可能であるし、あるいは逆に、解の探索メソッドを Field クラスに組み込んでもよかったような気もする。
しかし、敢えて NumberPlace クラスで包む事によって、たとえば《解の候補が見つかった時点で、それらを Field インスタンスにしてリストに集成する》といった拡張が容易になる。これなら、全ての解候補をしかるべきデータ構造のまま保持できるので、他のプログラムに解を引き渡す場合などに有用であろう。
どうでもいい main 関数（テスト用）。やたら長いので折りたたんでおいた。
main() {
unsigned char field[FIELD_SIZE * FIELD_SIZE];
Field *question;
NumberPlace *numberPlace;
// フィールド初期化
int i;
for(i = 0; i < FIELD_SIZE * FIELD_SIZE; ++i)
field[i] = 0;
// 問題設定
field[0] = 5;
field[1] = 3;
field[4] = 7;
field[9] = 6;
field[12] = 1;
field[13] = 9;
field[14] = 5;
field[19] = 9;
field[20] = 8;
field[25] = 6;
field[27] = 8;
field[31] = 6;
field[35] = 3;
field[36] = 4;
field[39] = 8;
field[41] = 3;
field[44] = 1;
field[45] = 7;
field[49] = 2;
field[53] = 6;
field[55] = 6;
field[60] = 2;
field[61] = 8;
field[66] = 4;
field[67] = 1;
field[68] = 9;
field[71] = 5;
field[76] = 8;
field[79] = 7;
field[80] = 9;
question = [[Field alloc] initWithFieldState: field];
numberPlace = [[NumberPlace alloc] initWithField: question];
[numberPlace solve];
return 0;
}
問題データを力づくでセットしているが、インタフェースを工夫すればユーザに優しいアプリケーションに化けそうだ。
実行すると、こんな感じでちゃんと答えが出た。わーい。
