おはやし日記

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

プログラムにナンプレを解かせたい - その1

前からナンプレが好きで、それなりに難しいのを解ける腕はあるつもりなんですが、人間なので時々見落としが発生するんですよね

プログラムならそんな見落としはないので、ちょっとパソコンに解かせてみたいなぁと思って作ることにしました

Cしかまともに知らないので言語はC。とりあえず解けることを目標にしているので計算効率とかそういうのは知らんです

なんつうか、あとで見返して自分が参考にできるレベルのメモ。

全体

github.com

ここにあります。

基本動作

実行ファイルが置いてあるディレクトリでmake doで開始(後述makefileによる)、$ $のところが入力位置。順番に数字を埋めていくと、確定したところは自動で埋められる。中級くらいのナンプレなら確実に全部埋まる。

gif、なんとなくの動き。

プログラム

計算パート

実質的な動作をする

sudoku/ver.1/calc

ヘッダファイル

  • 各マスの情報を示すmasu_s型構造体

numが確定した数字(0~8)、nが候補にある/ない でkouho[n]1/0

struct masu_s{
    int num;
    int kouho[9];
} masu[81];

numは1~9にしてnum=0を空きにすればよかった

kouho[num]の形で使いたかったからnumを0~8にしたんだった

→べつにkouho[10]にして最初を使わなければ良いのでは?というかkouho[0]numとして使えばいいのでは?そうしたら構造体にする必要もなくなるし読みやすくなる!!!

  • マスnの所属する列行ブロックを出すマクロ
#define LINE(i) ((i)/9)
#define ROW(i) ((i)%9)
#define BLOCK(i) (LINE(i)/3*3 + ROW(i)/3)

マクロはとにかく()で囲う。誤動作防止。

  • n/m*m の意味

m = 3

n 0 1 2 3 4 5 6 7 8 9
n/m 0 0 0 1 1 1 2 2 2 3
n/m*m 0 0 0 3 3 3 6 6 6 9

m分割した時各ブロックの頭になる数字を出す

calc.c

  • void reset() === すべてのマスをリセット(num = NO_NUM (=-1))、すべてのマスの候補を1にする(=どの数字も候補になる)
  • void showAllTest(); === まだ完成版ではない(候補の表示を改良したい)のでTest。
  • void showAllKouho(int); === 引数nが候補で入るマスを全て表示する。
  • int sumKouho(int); === 候補フラグの数を数える
  • void checkNum(int);・void checkNumAll();
void checkNum(int n){
    int i;
    if(sumKouho(n) == 1){
        for(i=0; i<9; i++){
            if(masu[n].kouho[i]){
                inputNum(n, i+1);
                return;
            }
        }
    }
    masu[n].num = NO_NUM;
}

候補が一つしかなかったら、確定なのでフラグが立っているところを見つけてinputNum(後述)する

checkNumAllはマス0~80にcheckNumを走らせるだけ

  • int lineStart(int);・int rowStart(int);・int blockStart(int); === 引数nの列・行・ブロックの先頭となるマスの数を返す。マクロでも良かった
int lineStart(int n){
    return LINE(n) * 9; //= n/9*9
}
int rowStart(int n){
    return ROW(n) % 9; //= n%9%9
}
int blockStart(int n){
    return LINE(n)/3*27 + ROW(n)/3*3; //= n/9/3*27 + n%9/3*3
}

何回も使う気がしたから展開して長くなるマクロじゃなくて関数にしてみたけど普通に下記のマクロでよかった

#define LINE_START(n) ((n)/9*9)
#define ROW_START(n) ((n)%9) //or ROW(n)
#define BLOCK_START(n) ((n)/27*27 + (n)%9/3*3)
  • void dltKouho(int, int);・void deleteLine(int);・void deleteRow(int);・void deleteBlock(int);
void dltKouho(int n, int k_dlt){
    masu[n].kouho[k_dlt] = 0;
}
void deleteLine(int n){
    int i;
    int ls = lineStart(n);
    for(i=0; i<9; i++){
        if(ls+i == n){
            continue;
        }
        dltKouho(ls+i, masu[n].num);
    }
}

マスnにはk_dltは入らないよっていう。残りのdelete系は、列・行・ブロックに対して走査してdleKouhoする

  • void inputNum(int, int); === プログラムの核。
void inputNum(int n, int input0_9){
    int i, input;
    input = input0_9 - 1;
    masu[n].num = input;
    for(i=0; i<9; i++){
        if(i == input)masu[n].kouho[i] = 1;
        if(i != input)masu[n].kouho[i] = 0;
    }
    if(input > NO_NUM){
        deleteLine(n);
        deleteRow(n);
        deleteBlock(n);
    }
}

マスnに、input0_9を確定させる。キーボードからの入力は0~9だけど、現在masu.numには-1~8で入れてるのでinput = input0_9 - 1;している。

  • int isFindKouho(int, int); === 使ってない。たぶん使おうと思ったけど関数にするほどでもないので使ってなかった。要らん。
  • int isOnlyOneInLine(int, int);・int isOnlyOneInRow(int, int);・int isOnlyOneInBlock(int, int);・int isOnlyOne(int, int); === マスnの候補k_fが列・行・ブロックで唯一の候補であるか
int isOnlyOneInLine(int n, int k_f){
    int i;
    int sum = 0;
    int ls = lineStart(n);
    for(i=0; i<9; i++){
        if(masu[ls+i].kouho[k_f])sum++;
    }
    if(sum == 1){
        return 1;
    }
    return 0;
}

横1列走査して、k_fを候補に持つマスが1つなら(マスnのみ)そのマスは確定(もしマスnの候補が1,3,5でも、列の中に1を候補にもつマスがなければn1に確定する)

とりあえずまとめ

改めて見直したら無駄がかなりあることに気づいた。 なんでncursesをインクルードしてるんかなと思ったけどvoid reset();void showAllTest();void showAllKouho(int);で使ってた。まあ残しといていいかな

とりあえずここらで投稿。

リンクつなげて伸ばしていきます。 次:

o-treetree.hatenablog.com

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