おはやし日記

テーマ……バイク←プログラミング←旅

ナンプレのマス走査方法メモ【C言語】

最近、C言語にナンプレ（ナンバープレイス）（数独）を解かせるのにはまっています。

プログラムにナンプレを解かせたい - その1 - おはやし日記

プログラムにナンプレを解かせたい - その2 - おはやし日記

プログラムにナンプレを解かせたい - その3 - おはやし日記

そのなかで、マス目に入っている数字や候補などをチェックするのに列や行、太枠のブロック、あるいは全体を走査する必要があります。

そのための方法について良いものが思いついたのでメモ。何かの運命でこのブログを見つけた初心者にもわかるように書いた、つもりなので冗長なところもあるけど。

↓クソ長目次許してクレメンス〜〜〜

定義など

マスの呼び方

data[81]で宣言。2次元配列だと色々と厄介なので、1次元配列です。

（最初は2次元配列になると全探索するときfor文が二重になるので1次元配列にしたのです。まあ、あとで2重ループしまくるので、主に配列を関数に渡すときに1次元ならvoid function(data[]);と宣言できるけど2次元配列だとvoid function(data[][9]);と宣言しなくちゃいけなくてなんか美しくない(?)から、ということで。）

行・列・ブロック

横向きに見るのが行。0行目（data[0] ~ data[8]）から8行目（data[72] ~ data[80]）まで。

縦向きに見るのが列。0列目（data[0, 9, 18, 27, 36, 45, 54, 63, 72] <- 雑な表現だが）以下略。

ブロックは下記画像のとおり0ブロック（data[0, 1, 2, 9, 10, 11, 18, 19, 20]）以下略。

単純な走査

普通に考えられるfor文の回し方。上記のナンプレ攻略プログラムでもやっていました。

全体走査

for(i=0; i<81; i++){
    data[ i ];
}

これは改良無しですね。

行内走査

int i, start;
// start = 0, 9, 18, ... 72
for(i=0; i<9; i++){
    data[ start + i ];
}

行の最初になるマスをstartで指定して右に読んでいきます。

列内走査

int i, start;
// start = 0, 1, 2, ... 8
for(i=0; i<81; i+=9){
    data[ start + i ];
}

列の最初になるマスをstartで指定して下に読んでいきます。マスを下に移動するとマスの番号は9増える。

ブロック内走査

int i, j, start;
// start = 0, 3, 6, 27, 30, 33, 54, 57, 60
for(i=0; i<27; i+=9){
    for(j=0; j<3; j++){
        data[ start + i + j ];
    }
}

ブロックの最初になるマスをstartに指定して二重for文で読んでいきます。

改良走査法の概念

先述の単純な走査では走査の回し方によってループ変数i, jの数も増えかたも違うので、一般化がしづらいです。

実際、プログラムにナンプレを解かせたい - その1 - おはやし日記でも走査する対象別で関数を作っています。

これでは、各個別々に書いてあって（素人的に）読みやすいことは読みやすいのですが、プログラムが肥大化します。長々と（ちゃっちいプログラムなので数百行ですが）スクロールするのだるいので嫌ですね。

ということで、改良して共通できるところを共通化し、変数によってそれぞれの走査を管理するようにしました。

改良のためにマスの走査の捉え方をちょっと変えてみます。

行内走査

行を、ナンプレの太線で3つの「小ブロック」に分割してあえて2重ループにします。

大きなループは3ずつ増やし、

小さなループは1ずつ増やします。

列内走査

列を、ナンプレの太線で3つの「小ブロック」に分割して2重ループにします。

大きなループは27ずつ増やし、

小さなループは9ずつ増やします。

ブロック内走査その1

ブロックを横に切って3つの「小ブロック」に分割して2重ループにします。

大きなループは9ずつ増やし、

小さなループは1ずつ増やします。

ブロック内走査その2

ブロックを縦に切って3つの「小ブロック」に分割して2重ループにします。

大きなループは1ずつ増やし、

小さなループは9ずつ増やします。

ブロック内を横以外に縦にも切ったのは、行内走査と列内走査両方と組み合わせる場面があったからです。

改良版の実装

STEP 1

とりあえず上の改良走査法をそのままコードにします。startは走査対象は最初のコードのようにで適宜変えます。

行内走査

int i, j, start;
for(i=0; i<9; i+=3){
    for(j=0; j<3; j+=1){
        data[ start + i + j];
    }
}

iが大きなループを、 jが小さなループを回しています。以下同様です。

列内走査

int i, j, start;
for(i=0; i<81; i+=27){
    for(j=0; j<27; j+=9){
        data[ start + i + j];
    }
}

ブロック内走査その1

int i, j, start;
for(i=0; i<27; i+=9){
    for(j=0; j<3; j+=1){
        data[ start + i + j];
    }
}

ブロック内走査その2

int i, j, start;
for(i=0; i<3; i+=1){
    for(j=0; j<27; j+=9){
        data[ start + i + j];
    }
}

STEP 2

さて、なんか共通部分が多くなってきました。嬉しい！

さらにfor文をいじっていきます。

変数A, Bを追加し、それぞれAが大きなループの増分を、Bが小さなループの増分を示します。これとijを掛けることで対象のマスを走査していきます。

行内走査

int i, j, start, A, B;
A = 3; 
B = 1;
for(i=0; i<3; i++){
    for(j=0; j<3; j++){
        data[ start + i*A + j*B ];
    }
}

マスの数字は 大きなループで3ずつ、 小さなループで1ずつ増えるので

A = 3; B = 1;

となります。以下同様です。

列内走査

int i, j, start, A, B;
A = 27; 
B = 9;
for(i=0; i<3; i++){
    for(j=0; j<3; j++){
        data[ start + i*A + j*B ];
    }
}

ブロック内走査その1

int i, j, start, A, B;
A = 9; 
B = 1;
for(i=0; i<3; i++){
    for(j=0; j<3; j++){
        data[ start + i*A + j*B ];
    }
}

ブロック内走査その2

int i, j, start, A, B;
A = 1; 
B = 9;
for(i=0; i<3; i++){
    for(j=0; j<3; j++){
        data[ start + i*A + j*B ];
    }
}

STEP 3

変数A, Bの違いだけになりました。嬉しい！！

ということでまとめです。

ループを回す共通関数

以上を踏まえて、走査開始マスstartと、走査方法を示す係数A, Bを引数としてナンプレマスを走査する関数roop()を作ります。

void roop(int start, int A, int B){
    int roop;
    for(i=0; i<3; i++){
        for(j=0; j<3; j++){
            roop = start + i*A + j*B;
            data[ roop ];
        }
    }
}

真ん中のdata[ roop ];は、実行したいことに合わせて適宜変更します。

ちょっと便利なマクロ導入

ここで、マクロを使います。マスの番号nから、そのマスが所属する行・列・ブロックの先頭のマスをはじき出すマクロです。

#define LINE_ST(n) ((n)/9*9) //0~81->{0,1,2,3,4,5,6,7,8,9}
#define ROW_ST(n) ((n)%9) //0~81->{0,9,18,27,36,45,54,63,72}
#define BLOCK_ST(n) ((n)/27*27 + (n)%9/3*3) //0~81->{0,3,6,27,30,33,54,57,60}

まあ計算してみるとわかります。

例えば、マス73( 8行 1列 6ブロック )については

LINE_ST(73) = ((73)/9*9) = 72 <- 8行の先頭マス
ROW_ST(73) = ((73)%9) = 1 <- 1列の先頭マス
BLOCK_ST(73) = ((73)/27*27 + (73)%9/3*3) = 54 <- 6ブロックの先頭マス

となります（以下の画像参照）。

走査方法ごとに共通関数の実行

ナンプレ攻略プログラムでは、それぞれのマスに操作したとき（数字を確定させるなど）にそれに応じて走査するので 先のマクロを利用してstartに入れる変数を決めてみました。

roop(LINE_ST(n), 3, 1); //マスnを含む行内の走査
roop(ROW_ST(n), 27, 9); //マスnを含む列内の走査
roop(BLOCK_ST(n), 9, 1); //マスnを含むブロック内の走査その1
roop(BLOCK_ST(n), 1, 9); //マスnを含むブロック内の走査その2

結論風おまけ

さらに、作成した共通関数をちょっとだけコンパクトにします

void roop(int start, int A, int B){
    int roop;
    for(i=0; i<3; i++)for(j=0; j<3; j++){
        roop = start + i*A + j*B;
        data[ roop ];
    }
}

for文は

for(){
    文;
}

の書き換えで

for()文;

と書けます。そんな感じで2重のforループを1列に収められます。

だからなんだという感じですが中の文がちょっと左に寄るので見やすい、というだけです。

ナンプレ攻略プログラムVer.2がいい感じに進化中なので、もう一つくらい機能追加したらまたブログに書こう（メモしよう）と思います

プライバシーポリシー ・お問い合わせはこちら