前からナンプレが好きで、それなりに難しいのを解ける腕はあるつもりなんですが、人間なので時々見落としが発生するんですよね
プログラムならそんな見落としはないので、ちょっとパソコンに解かせてみたいなぁと思って作ることにしました
Cしかまともに知らないので言語はC。とりあえず解けることを目標にしているので計算効率とかそういうのは知らんです
なんつうか、あとで見返して自分が参考にできるレベルのメモ。
全体
ここにあります。
基本動作
実行ファイルが置いてあるディレクトリでmake do
で開始(後述makefileによる)、$ $
のところが入力位置。順番に数字を埋めていくと、確定したところは自動で埋められる。中級くらいのナンプレなら確実に全部埋まる。
gif、なんとなくの動き。
プログラム
計算パート
実質的な動作をする
ヘッダファイル
- 各マスの情報を示す
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
を候補にもつマスがなければn
は1
に確定する)
とりあえずまとめ
改めて見直したら無駄がかなりあることに気づいた。 なんでncursesをインクルードしてるんかなと思ったけどvoid reset();void showAllTest();void showAllKouho(int);で使ってた。まあ残しといていいかな
とりあえずここらで投稿。
リンクつなげて伸ばしていきます。 次: