最近はHTML+CSS+JavaScriptに手を出しています。
そこでXMLHttpRequestを使ってみた時、「localhostがどうのこうの」、というシーンがありました。
その挙動についてメモ。
/Users/~~~/localhosttest | |- index.html |- main.js |- oha.txt
全てlocalhosttestディレクトリの中で行う。
どうでもいいんですが、gistってアルファベット順に並ぶのでこのファイル名はいい感じの順番になってくれてちょっと嬉しいです
続きを読むこんにちは。
そういうのって、ガチ勢じゃないと歯が立たないのかと思ってたら、初心者でもできるレベルから問題があると知ったので。
今まで3回やりましたが、Cまでは解けて、Dは、言われればそうかぁって感じだけど解けない。って感じ。
提出した解答と、反省を書く
4/19(sun)のABC163（4回目）から。
昼間寝ちゃって、起きたら21:10くらいでした。ABC163は21時からなので、出遅れた！と思って開始。
今回Unratedでした。悲しい。
AC
Submission #12120122 - AtCoder Beginner Contest 163
#include <stdio.h> #include <math.h> int main(){ int R; scanf("%d", &R); printf("%lf\n", (double)R*2*M_PI); return 0; }
最初IEが出ては？ってなったけど通ってた。めでたし。
AC
Submission #12127805 - AtCoder Beginner Contest 163
#include <stdio.h> typedef long long LL; int main(){ LL N, M; scanf("%lld%lld", &N, &M); LL buf, shukudai = 0; for(LL i=0; i<M; i++){ scanf("%lld", &buf); shukudai += buf; } LL ans = N-shukudai; printf("%lld\n", ans>-1 ? ans: -1); return 0; }
コメントすることなし。めでたし。
AC
Submission #12131466 - AtCoder Beginner Contest 163
#include <stdio.h> int main(){ int N, buf; scanf("%d", &N); int A[300000] = {}; for(int i=0; i<N-1; i++){ scanf("%d", &buf); A[buf]++; } for(int i=1; i<=N; i++){ printf("%d\n", A[i]); } return 0; }
最初、Aを入れる配列を
int A[N+1] = {};
ってやってコンパイルしたらエラー↓
c.c:6:11: error: variable-sized object may not be initialized
int A[N+1] = {};
が出たので（可変長配列は初期化できない）、確かに。と思って
int A[N+1];
にしたら、forループで初期化してないのにインクリメントして変になった（それはそう）ので結局デカ目に用意した。
めでたし。
解説は本家を見てもらうとして、その方針はバッチリだったんですけど…………
WA
Submission #12142614 - AtCoder Beginner Contest 163
回答が、109+7で割ったあまりを要求しているので
#define LIMIT 1000000007
として計算するたびに%LIMITをかましていたんですけど、うまくいかんかったです。（これは入力例3も通ってなかったけど一応提出したやつ）
結論としては、計算は間違っていないので%LIMITをとるのを一番最後だけにしました
AC
Submission #12152031 - AtCoder Beginner Contest 163
時間外ですが通過！めでたし。
どうやら、mstdn.jpの人にお伺いを立てたところ、むやみに剰余をとったためバグったようです。
結局最後に剰余とるだけでいいということは、計算途中ではオーバーフローしてないんすねぇ。
今回は計算途中で出てくる可能性がある値は
1から2x105の和 ≒ 2x1010 これはlong long でおさまる（このスケールがでてくる時はkがでかいので、最大値と最小値で差し引きすると"被り"が大きくて大した値にならない（下のグラフでもわかる））
ループの中で加算する値（buf = summax(k, N) - summin(k) + 1;）はNを固定してkを変えるとx>0で単調減少する
結局ループで足した結果もlong longで余裕でおさまる
説明不足が過ぎるが、個人的に納得したのでおしまい！！！
最終回。↓のつづき。
プログラムがパワーアップした後の要点は、
ここ↑で書いたcalc.cの計算部分と
ここ↑で書いたfileio.cのファイル入出力です。
今回は、なんとなく作ったログ書き出しプログラムについて書きます。あと、makefileについて。
全体のプログラムはこちら↓
GitHub - oha-yashi/sudoku: ナンプレ攻略プログラム
（追記@2020/5月） これをJavaScriptに移植したwebバージョンができてます！詳しくは ↓
githubからcloneしたあと（詳細はプログラムにナンプレを解かせたい - その4 - おはやし日記）
$ make log
でコンパイル。
logdataフォルダに、盤面データtest↓をいれて
%1d 000 400 065 080 000 000 700 090 000 000 000 120 065 008 000 004 000 000 000 600 009 100 000 700 000 005 000
$ ./log test (auto)
で実行。（autoを加えるとステップごとにEnterを叩く必要がなくなる）
Enterを叩いていくとこのように表示され、logdata/test_logが作成される。中身は↓のようになります（クソ長い）
gistbeaa9476c970a13069f85a74f521a2d5
解答ステップごとに、全ての候補が書き出されています。さらに、前のステップから変更があったマスについてはマスの下の線が
^^^^^
となって示されています。
log.cはなんとなくあったらいいかも知れんと思って突貫で作ったので割と作りが雑です。
for(i=0;i<9;i++){ fprintf(fp, "%d:@", i); for(j=0;j<3;j++){ roop = i*9 + j*3; fprintf(fp, "|%c %c %c|%c %c %c|%c %c %c|@", PUT_LOG(roop , 1), PUT_LOG(roop , 2), PUT_LOG(roop , 3), PUT_LOG(roop+1, 1), PUT_LOG(roop+1, 2), PUT_LOG(roop+1, 3), PUT_LOG(roop+2, 1), PUT_LOG(roop+2, 2), PUT_LOG(roop+2, 3) ); } fprintf(fp, "\n "); fprintf(fp, "%d:@", i); for(j=0;j<3;j++){ roop = i*9 + j*3; fprintf(fp, "|%c %c %c|%c %c %c|%c %c %c|@", PUT_LOG(roop , 4), PUT_LOG(roop , 5), PUT_LOG(roop , 6), PUT_LOG(roop+1, 4), PUT_LOG(roop+1, 5), PUT_LOG(roop+1, 6), PUT_LOG(roop+2, 4), PUT_LOG(roop+2, 5), PUT_LOG(roop+2, 6) ); } fprintf(fp, "\n "); fprintf(fp, "%d:@", i); for(j=0;j<3;j++){ roop = i*9 + j*3; fprintf(fp, "|%c %c %c|%c %c %c|%c %c %c|@", PUT_LOG(roop , 7), PUT_LOG(roop , 8), PUT_LOG(roop , 9), PUT_LOG(roop+1, 7), PUT_LOG(roop+1, 8), PUT_LOG(roop+1, 9), PUT_LOG(roop+2, 7), PUT_LOG(roop+2, 8), PUT_LOG(roop+2, 9) ); } fprintf(fp, "\n ");
roopはマスの番号。PUT_LOGはマクロ。数字or空白の表示なのでfprintfの%cに突っ込む。
#define PUT_LOG(n, i) FLAG(data[n], i) ? i+'0' : ' '
if(i==2||i==5||i==8){ fprintf(fp, "@@@@"); AT_LINE(i*9+0);AT_LINE(i*9+1);AT_LINE(i*9+2); fprintf(fp, "@@"); AT_LINE(i*9+3);AT_LINE(i*9+4);AT_LINE(i*9+5); fprintf(fp, "@@"); AT_LINE(i*9+6);AT_LINE(i*9+7);AT_LINE(i*9+8); fprintf(fp, "@\n "); }else{ fprintf(fp, "----"); DASH_LINE(i*9+0);DASH_LINE(i*9+1);DASH_LINE(i*9+2); fprintf(fp, "--"); DASH_LINE(i*9+3);DASH_LINE(i*9+4);DASH_LINE(i*9+5); fprintf(fp, "--"); DASH_LINE(i*9+6);DASH_LINE(i*9+7);DASH_LINE(i*9+8); fprintf(fp, "@\n "); }
3列ごとに@で太い線を、その他は-で細い線を引く。AT_LINEとDASH_LINEはマクロ。
#define AT_LINE(n) data[n]==buf[n] ? fprintf(fp, "@@@@@@") : fprintf(fp, "^^^^^@") #define DASH_LINE(n) data[n]==buf[n] ? fprintf(fp, "------") : fprintf(fp, "^^^^^-")
さっきみたいにfprintfの中身だけ変えればよかったな、まあええわ。要は、前ステップのデータbuf[]と操作後のデータdata[]が違っていれば何かしら変更があったということなので横線を^^^^^にして示す。
前に作ったmenu.c/menu()をログ書き込みに特化させた
void menu_log(){ int cnt = 1, ssK = sumsumKouho(); while(cnt < LIMIT){ if(ssK==81) break; /* 判定処理 */ only_two_pair_all(); if(ssK > sumsumKouho()){ /* 処理で候補を減らせたら */ write_log(cnt, 1, "two pairs -> delete num except pair"); move_data(data, buf); ssK = sumsumKouho(); }if(ssK==81) break; findPairAll(); if(ssK > sumsumKouho()){ write_log(cnt, 2, "two pairs -> delete pair in LineRowBlock"); move_data(data, buf); ssK = sumsumKouho(); }if(ssK==81) break; read_and_delete(); if(ssK > sumsumKouho()){ write_log(cnt, 3, "read LineRowBlock and delete"); move_data(data, buf); ssK = sumsumKouho(); }if(ssK==81) break; findAllOnlyOne(); if(ssK > sumsumKouho()){ write_log(cnt, 4, "onlyone in LineRowBlock -> input"); move_data(data, buf); ssK = sumsumKouho(); }if(ssK==81) break; checkNumAll(); if(ssK > sumsumKouho()){ write_log(cnt, 5, "onlyone in data -> input"); move_data(data, buf); ssK = sumsumKouho(); }if(ssK==81) break; if(isauto){}else getch(); cnt++; } }
# define LIMIT 30回まで処理。用意した処理で対応できずに詰んだら無限ループになってしまうので。ssk=sumsumKouho()は、盤面全体で候補のフラグが立っている数。全マスが埋まればssK=81となって終了。
isautoはグローバル変数でisauto=0。ここ、if(!isauto)getch();でよかったな…………。コマンドライン引数の3つ目にautoを入れていればgetch()不要で次のステップに進む。
make は、コマンドをmakefileに書き込んでおくと短い呼び出しでそれをやってくれる機能（？多分結構違う）です。
なんか解説することあるかなと思ったけどmakefileにメモってあるから要らんかなw
ファイル構造が
sudoku
|
|- makefile
|
|- source
|
|- calc.c
|- calc.h
...
ってなっているので、コンパイルに使うファイルの探し先として
VPATH = source
としています。
プログラム君がどう動いているのか知りたかったので作ってみただけです。
おしまい！！！
ここに載せた以外にもあるんですけど、大学や高専の情報科か何かのページが多いのでリンク貼っていいのかわからんのもあったり…………まあ検索すれば出て来ます。
トリビアなmakefile入門 http://www.jsk.t.u-tokyo.ac.jp/~k-okada/makefile/
GNU make 日本語訳(Coop編) - 目次 https://www.ecoop.net/coop/translated/GNUMake3.77/make_toc.jp.html
Makefileの書き方に関する備忘録 - minus9d's diary https://minus9d.hatenablog.com/entry/20140203/1391436293
相変わらず暇なので書きます。ナンプレ攻略プログラムについて。
↑の続き。今回はファイル入出力とメニュー表示。
ファイル入出力をする。
#define SAVE_FILE "np/save.dat" #define DIR_NP "np/"
セーブファイルの名前と、データを入れるディレクトリ
%1d 123456789 < 81個の数字0~9 >
1行目に、変換指定子%1dを書き、2行目から盤面の数字を入れる。
%1d 123 456 789 456 789 123 ...
のように整形してもいいし、極端に言えば81桁の数字にしても良い。
%x 1234 5678 90ab cdef 1234 5678 90ab cdef 1234 < 16進数のdata空白区切りで81個 >
int read_np(const char *filename){ FILE *fp; if( (fp = fopen(filename, "r")) ==NULL){ printw("%s file open error!!", filename); fclose(fp); return -1; } int i, buf; char format[50], fbuf[50]; if(fscanf(fp, "%%%s", fbuf)){ /* なにかしら変換指定子の存在を確認 */ /* "%hoge"の形式のみ通過 fbufには"hoge"のみ入る */ sprintf(format, "%%%s", fbuf); /* "hoge" で格納されているのを "%hoge" に戻してformatに入れる */ for(i=0; i<81; i++){ fscanf(fp, format, &buf); if(!strcmp(format, "%1d")){ inputNum(i, buf); }else if(!strcmp(format, "%x") || !strcmp(format, "%4x")){ data[i] = buf; } } }else{ printw("in %s, no format!", filename); fclose(fp); return -1; } fclose(fp); return 0; }
データが1桁なのか16進法なのかわからんといけないのでif(fscanf(fp, "%%%s", fbuf))でデータ1行目の変換指定子を読んで判定する。
1桁の盤面データであればinputNumし、16進数データなら直接dataに突っ込む
void read_file(){ char fname[FILENAME_MAX]; char buf[FILENAME_MAX]; printw("\n%s[filename] -> %s", DIR_NP, DIR_NP); echo(); scanw("%s", buf); noecho(); sprintf(fname, "%s%s", DIR_NP, buf); int r = read_np(fname); if(r==0) printw("read %s", fname); getch(); } void read_save(){ addch('\n');//read_fileと改行数を合わせる int r = read_np(SAVE_FILE); if(r==0) printw("read %s", SAVE_FILE); getch(); }
read_file()はファイル名を指定して読み込む。read_save()はセーブファイルを読み込む。//改行数を合わせるというのは表示上の話
void save_data(){ addch('\n');//read_fileと改行数を合わせる FILE *fp; if( (fp = fopen(SAVE_FILE, "w")) ==NULL){ addstr("file open error!!"); return; } fprintf(fp, "%%x\n"); /*再読み込みで必要な変換指定子 %x を書き込む*/ for(int i=0; i<81; i++){ fprintf(fp, "%04x ", data[i]); //ここは%04x固定で if(i%9==8)fputc('\n', fp); } /*10行目時間情報書き込み*/ time_t now = time(NULL); struct tm *timer = localtime(&now); fprintf(fp, "saved at %4d/%02d/%02d %02d:%02d:%02d", timer->tm_year + 1900, timer->tm_mon + 1, timer->tm_mday, timer->tm_hour, timer->tm_min, timer->tm_sec ); fclose(fp); printw("write %s", SAVE_FILE); }
セーブする。おしまい。
基本ループのmenu()。入力分岐でqが入るまでループして盤面処理をする。
どのように表示されるかについては
こちら参照。
void menu(){ int i, ch, now; ch = now = 0; reset(data);reset(buf);reset(save); while(1){ /* 盤面, メニュー表示 */ showAll(); markKouho2or3(); mark_data_void(); mark(now, 2, '$'); printmenu(now); /* 入力分岐 */ ch = getch(); if(ch == 'q') break; if(ch == 'c'){changeKouho(&now); continue;} if(ch == 'b'){move_data(buf, data); continue;} if(ch == 'd'){move_data(data, buf); delete_data(now); continue;} if(ch == 'x'){move_data(data, buf); reset(data); now=0; continue;} if(ch == 'i'){read_file(); continue;} if(ch == 'w'){save_data(); continue;} if(ch == 'r'){read_save(); continue;} if(ch == 'k'){ for(i=1; i<=9; i++){ showAllKouho(i); getch(); } } if(ch == ' '){ now++; if(now==81)now=0; } if(KEY_DOWN <= ch && ch <= KEY_RIGHT){ udrl(ch, &now); } if('0' <= ch && ch <= '9'){ move_data(data, buf); inputNum(now, ch - '0'); now++; if(now==81)now=0; } /* 判定処理 */ only_two_pair_all(); findPairAll(); read_and_delete(); findAllOnlyOne(); checkNumAll(); } }
以下、menu()で使う順に
void showAll(){ int i, j; move(0,0); for(i=0;i<81;i++){ if(NUM(data[i])){ printw("[%d] ", NUM(data[i])); }else{ printw("[ ] "); } if(ROW(i)==2 || ROW(i)==5)addstr("@ "); if(ROW(i) == 8)addstr("@\n"); if(i%27==26){ for(j=0;j<YOKO;j++)addch('='); addch('\n'); } } refresh(); }
全マス書き出し。
void mark(int n, int cp, char c){ /* マス n の枠を色番号 cp の文字 c で囲む */ attron(COLOR_PAIR(cp)); mvprintw(LS[LINE(n)], RS[ROW(n)]-1, "%c", c); mvprintw(LS[LINE(n)], RS[ROW(n)]+1, "%c", c); attron(COLOR_PAIR(1)); } void markKouho2or3(){ for(int i=0; i<81; i++){ if(sumKouho(i) == 2) mark(i, 4, '!'); if(sumKouho(i) == 3) mark(i, 3, '?'); } } void mark_data_void(){ // 確定なしで候補全滅だと0x0000になる。間違い。 for(int i=0; i<81; i++){ if(data[i] == 0x0000) mark(i, 2, 'X'); } }
候補の数2, 3であるものをマーク、間違った盤面入力によって候補が全滅したマスをマークする。
void printmenu(int now){ int i; move(12,0); printw("now(%2d: %04x)", now, data[now]); if(NUM(data[now]) > 0){ printw("[%d] < ", NUM(data[now])); }else{ printw("[_] < "); } for(i=1; i<=9; i++){ if(FLAG(data[now], i)){ printw("%d ", i); } } addstr(">\n"); addstr("[^] [v] [<] [>] [Space] ["); addstr_rev_nml("K", "ouho] ["); addstr_rev_nml("C", "hange]\n["); addstr_rev_nml("B", "ack] ["); addstr_rev_nml("D", "elete] ["); addstr_rev_nml("X", ":reset] ["); addstr_rev_nml("I", "mport]\n["); addstr_rev_nml("W", "rite_save] ["); addstr_rev_nml("R", "ead_save] ["); addstr_rev_nml("Q", "uit]"); refresh(); } void addstr_rev_nml(char *r, char *n){ reverse(ON);addstr(r);reverse(OFF);addstr(n); } //setting.c void reverse(int OnOff){ if(OnOff)attron(A_REVERSE); if(!OnOff)attrset(0); }
メニュー表示。addstr_rev_nml(char *r, char *n)は、rを白黒反転表示してnを通常表示する。
//if(ch == 'c'){changeKouho(&now); continue;} void changeKouho(int *n){ int now = *n; int i, change; move(12,0); for(i=1; i<=9; i++){ if(FLAG(data[now], i)){ printw("%d ", i); } } addstr("whitch to change -> "); change = getch() - '0'; if(1 <= change && change <= 9){ if(FLAG(data[now], change)){ flag_off(data[now], change); }else{ flag_on(data[now], change); } } }
なぜ参照渡しにしたのかはわからんが、現在立っている候補を列挙し、選択した候補のフラグを逆転させる。
//if(ch == 'b'){move_data(buf, data); continue;} //if(ch == 'd'){move_data(data, buf); delete_data(now); continue;} //if(ch == 'x'){move_data(data, buf); reset(data); now=0; continue;} void move_data(np from[], np to[]){ for(int i=0; i<81; i++){ to[i] = from[i]; } }
データのコピー。なんか操作するときは一度bufに保存しているので1つ戻るくらいはできる
/* if(ch == 'k'){ for(i=1; i<=9; i++){ showAllKouho(i); getch(); } } */ void showAllKouho(int k){ int i, j; move(0,0); for(i=0;i<81;i++){ if(FLAG(data[i],k) && !NUM(data[i])){ attron(COLOR_PAIR(3)); printw("<%d> ", k); attron(COLOR_PAIR(1)); }else if(NUM(data[i]) != 0){ printw("[%d] ", NUM(data[i])); }else{ printw("[ ] "); } if(i%3==2)addstr("@ "); if(ROW(i) == 8)addch('\n'); if(i%27==26){ for(j=0;j<41;j++)addch('='); addch('\n'); } } refresh(); }
showAll()の変形で、1~9まで順番に、候補があるマスを緑色で表示する。
/* if(KEY_DOWN <= ch && ch <= KEY_RIGHT){ udrl(ch, &now); } */ void udrl(int ch, int *n){ int now = *n; switch(ch){ case KEY_UP: *n = LINE(now)!=0 ? now-9 : now+72; break; case KEY_DOWN: *n = LINE(now)!=8 ? now+9 : now-72; break; case KEY_LEFT: *n = ROW(now)!=0 ? now-1 : now+8; break; case KEY_RIGHT: *n = ROW(now)!=8 ? now+1 : now-8; break; } }
これは、矢印キーが入力された時に現在地nowを変更する関数なので参照渡しにする必要がある。
ファイル入出力ができて嬉しい！！！
おしまい。
コロナで暇なので書きます。
↑の続き。とりあえず根幹の計算部分から。要点、というかコード見てすぐにわかりそうにないところを抜き出して解説、というかメモを加える。
プログラムはgithubにあります。
GitHub - oha-yashi/sudoku: ナンプレ攻略プログラム
ナンプレ盤面のデータの取り扱いをする
typedef unsigned short np;
盤面データは前回書いた通り16ビットのビット列で扱うのでunsigned shortをnp型として使う
/* d にはdataをいれる, nにはマスの数字を入れる iにはマスに入れる数字1~9を入れる*/ /* d から定数を返す */ #define np_reset 0x03fe //0000,0011,1111,1110 #define NUM(d) ((d)>>12) #define FLAG(d, i) ((d)>>i & 1) /* d に操作をする */ #define set_num(d, i) d = d & 0x0fff | (i<<12) /* 0x**** -> 0x0*** -> 0xi*** */ #define flag_on(d, i) d |= 1<<i // i桁目1にする #define flag_off(d, i) d &= ~(1<<i) // i桁目0にする /* n から定数を返す */ #define LINE(n) ((n)/9) #define ROW(n) ((n)%9) #define BLOCK(n) (LINE(n)/3*3 + ROW(n)/3) #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} #define BLOCK_N_ST(n) ((n)/3*27 + (n)%3*3) //0~8->{0,3,6,27,30,33,54,57,60}
見たまま。関数にするほどでもないものをマクロで定義している。
#define FLAG(d, i) ((d)>>i & 1)は、条件式に突っ込むだけならd & (1 << i)でも良いんだけど、あとでフラグの数を数えるので1/0で返るようにした。
0b1000 & (1 << 4) --> 0b1000 & 0b1000 --> 0b1000 0b1000 >> 4 & 1 --> 0b0001 & 1 --> 0b0001
#define BLOCK_N_ST(n) ((n)/3*27 + (n)%3*3)は、0~8のブロック番号から、そのブロックの開始マスを得る。
int sumKouho(int n){ int sum = 0; for(int i=1; i<=9; i++){ sum += FLAG(data[n],i); } return sum; }
さっきフラグを数えるといっていたやつ。マス目の候補の数を求める。
void checkNumAll(){for(int n=0;n<81;n++)if(sumKouho(n)==1)for(int j=1;j<=9;j++)if(FLAG(data[n],j))inputNum(n,j);}
ふざけて1行にしただけ。見やすくするとこうなる
void checkNumAll(){ for(int n=0;n<81;n++){ if(sumKouho(n)==1){ for(int j=1;j<=9;j++){ if(FLAG(data[n],j)){ inputNum(n,j); } } } } }
全部、直接のネストなので1行にまとめられる
void delete_data(int n){ ...
マスnを削除する。単にそのマスを消すだけだと、周辺で消してしまった候補を復活させられないので、一旦全部のマスの数字（空きor確定数字）を保存しておいて、全部リセットして書き直す
void delete_lrb(int n, int byA, int byB, char c){ int i, j, start, roop; switch(c){ case 'l': start = LINE_ST(n); break; case 'r': start = ROW_ST(n); break; case 'b': start = BLOCK_ST(n); break; } for(i=0; i<3; i++)for(j=0; j<3; j++){ roop = start + i*byA + j*byB; if(roop == n){ continue; }else{ flag_off(data[roop], NUM(data[n])); } } }
走査は前に書いたナンプレの走査法でやる
マスnに対して、そのマスが含まれる行・列・ブロックでNUM(data[n]) = マスnに確定した数字を候補から外す。
関数の名前に_lrbをつけているのは、走査方法を指定して行・列・ブロックに適用できる関数で、変数を変えてそれぞれの方向に走査する。
void delete_check(int n){ delete_lrb(n, 3, 1, 'l'); delete_lrb(n, 27, 9, 'r'); delete_lrb(n, 9, 1, 'b'); }
↑これ。行に対してdelete_lrbをやるのがdelete_lrb(n, 3, 1, 'l');。
以下略。
/* マスn に input を確定させる 0~9を入れる */ void inputNum(int n, int input){ // D=****,****,****,*****, input=5 if(input != 0){ set_num(data[n], input);// D=0101,****,****,**** flag_on(data[n], input);// D=0101,****,**1*,**** for(int i=1; i<=9; i++){ if(i != input)flag_off(data[n], i); }// D=0101,**00,0010,000* delete_check(n); }else if(input == 0){ data[n] = np_reset;// D=0000,0011,1111,1110 } }
根幹の、数字を確定させる関数。
int isOnlyOneIn_lrb(int start, int find, int byA, int byB){ int sum = 0; for(int i=0; i<3; i++)for(int j=0; j<3; j++){ if(FLAG(data[start+i*byA+j*byB], find)) sum++; } return (sum==1) ? 1 : 0 ; }
行・列・ブロックの中で、findを候補とするマスが1つしかない時、1を返す。
void findAllOnlyOne(){
...
全マス全候補1~9で全方向に走査して、どれかの方向でOnlyOneと判断したらinputNumする
ここからは、数字を確定させるのではなく、候補を消していくための関数。
文で説明するとややこしいのでとりあえず図を。
ここでは説明のために、数字3について候補になるところは全部書いている。
さて、この局面では緑マスの候補3は消去できる。左のブロックも、右のブロックも2,3段目に3を入れるしかないので、真ん中のブロックでは2,3段目に3が入ることはできない。
しかし、ここまでの関数では候補を消せず、手動での候補の変更が必要だった。
と言うことでread_delete_lrb関数はこういう局面での候補削減をする。
図の再掲。まず青と黄で塗られた行を見ると、3が候補になるマスは黄色の所のみ。
その行では真ん中のブロックにのみ候補があるので、黄色マスのどこかに3が入るから、真ん中ブロックを見ると緑のマスでは候補3を消せる。
行方向にreadしてブロック方向にdeleteする関数、と言うこと。
void read_delete_lrb(int start, int kouho, int byA, int byB, int byC, char c)
引数について。走査用の変数についてはこちらも参照。「小ブロック」は↓のページで使っている概念。
03319上図の局面を解決するためには
read_delete_lrb(0, 3, 3, 1, 9, 'b')
を呼び出す。解説つきで関数の動作を確認。
void read_delete_lrb(int start, int kouho, int byA, int byB, int byC, char c){ int sum[3] = {}; int keep[3] = {}; // sum[]は各小ブロックでの候補の数 int i, j, k, roop, sum_all, cont; sum_all = cont = 0; for(i=0; i<3; i++){ for(j=0; j<3; j++){ roop = start + i*byA + j*byB; // 赤矢印と青矢印で走査 if(NUM(data[roop]) == kouho) return; // 探している候補がすでに確定していたら終了 sum[i] += FLAG(data[roop], kouho); // 探している候補があったらsum[i]に入れる // sum[0]=0, sum[1]=3, sum[2]=0となる } sum_all += sum[i]; } // sum_all=3 for(i=0; i<3; i++){ if(sum[i] == sum_all){ // どこかの小ブロックに候補が集まっている // 今回はsum[1]==sum_all==3で通過 for(j=0; j<3; j++){ roop = start + i*byA + j*byB; keep[j] = roop; // その小ブロックの位置(黄色マス)をkeep[]に保存 } cont = i+1; // contは小ブロックの位置1~3 // 今回はcont=2 break; } } if(!cont--) return; // contが増えなければcont=0なのでreturn // contに1~3が入っていれば通過させ、contをデクリメントして0~2にする // 今回は通過してcont=1となる switch(c){ case 'l': start = LINE_ST(start + cont*byA); break; case 'r': start = ROW_ST(start + cont*byA); break; case 'b': start = BLOCK_ST(start + cont*byA); break; } // 候補を見つけた小ブロックの位置、走査の方向に応じて、次の走査の開始マスを指定する // 今回はstart=0,c='b' <- マス0から行走査で、これからブロック走査 // cont=1なのでstart=BLOCK_ST(3)=3 <- 黄色マスのあるブロックの開始マス for(i=0; i<3; i++)for(j=0; j<3; j++){ roop = start + i*byB + j*byC; // 青矢印と緑矢印で走査 for(k=0; k<3; k++){ if(roop == keep[k]) goto NEXT; // keepに入れた黄色マスだったらcontinue // continueだとバグ？わからん } flag_off(data[roop], kouho); // 緑マスではkouho=3を消す NEXT:; } }
このような局面では、まず青マスがあるブロック[0]を走査して、横並びの黄色マスに3が候補として入っているのでその右の緑マスで候補3を消去できる。
これを解決するには
read_delete_lrb(BLOCK_N_ST(0), 3, 9, 1, 3, 'l')
を呼び出す。ブロック[0]の開始マスをstartとして候補3を探索。走査用の変数はブロックを走査するために9, 1、さらに行方向に走査するために3, 'l'を与える。
全部まとめると
void read_and_delete(){ for(int lrb=0; lrb<9; lrb++){ for(int kouho=1; kouho<=9; kouho++){ read_delete_lrb(lrb*9, kouho, 3, 1, 9, 'b'); read_delete_lrb(lrb, kouho, 27, 9, 1, 'b'); read_delete_lrb( BLOCK_N_ST(lrb), kouho, 9, 1, 3, 'l'); read_delete_lrb( BLOCK_N_ST(lrb), kouho, 1, 9, 27, 'r'); } } }
こうなる。
void findPair(int start, int byA, int byB){ int i, j, k, l, roop, roop2, cnt; for(i=0;i<3;i++)for(j=0;j<3;j++){ roop = start + i*byA + j*byB; cnt = 0; if(sumKouho(roop)==2){ //data[roop]が候補2つ for(k=0;k<3;k++)for(l=0;l<3;l++){ roop2 = start + k*byA + l*byB; if(data[roop]==data[roop2])cnt++; } if(cnt==2){ //data[roop]のペアがブロックを独占 for(k=0;k<3;k++)for(l=0;l<3;l++){ roop2 = start + k*byA + l*byB; if(data[roop2]!=data[roop]){ data[roop2] &= ~(data[roop]); //data[roop]のフラグを消す } } } } } }
これは、
の我流解法テクニックBの実装。
data[roop]の候補が2つあって、もう一度走査してdata[roop]と同じdataが2つあったら（data[roop]自体ともう一つ）、再度走査してdata[roop]と中身が同じでないマスで~data[roop]との論理積をとって余計な候補をつぶす。
void only_two_pair_lrb(int start, int byA, int byB){ int i, j, k, l, roop, cnt; int q_k[10] = {}; for(k=1;k<=9;k++){ for(i=0;i<3;i++)for(j=0;j<3;j++){ roop = start + i*byA + j*byB; if(FLAG(data[roop], k))q_k[k]++; } } int pair_k_in[10][2] = {}; for(k=1; k<=9; k++){ cnt = 0; if(q_k[k] == 2){ for(i=0;i<3;i++)for(j=0;j<3;j++){ roop = start + i*byA + j*byB; if(FLAG(data[roop], k)){ pair_k_in[k][cnt] = roop; cnt++; } } } } //ブロック内で2箇所のみkが入るマスがpair_k_in[k][2]に入った for(k=1; k<=9; k++){ if(q_k[k] == 2){ for(l=k+1; l<=9; l++){ if(pair_k_in[k][0] == pair_k_in[l][0] && pair_k_in[k][1] == pair_k_in[l][1]){ //pairの組が一致したらそこでkとlが独占 data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] = 0x0; data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] |= 1<<k; data[ pair_k_in[k][0] ] = data[ pair_k_in[k][1] ] |= 1<<l; //フラグ立てをkとlのみにする } } } } }
| k-> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 候補 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| data[0] | - | - | 3 | - | - | - | - | - | 9 | 3,9 | |
| data[1] | - | 2 | 3 | - | - | - | - | - | 9 | 2,3,9 | |
| data[2] | 1 | 2 | 3 | - | - | - | - | - | 9 | 1,2,3,9 | |
| data[3] | - | - | 4 |
5 |
- | - | - | 3,4,5,6 | |||
| data[4] | - | - | - | - | - | - | - | 8 | - | 8(確定) | |
| data[5] | 1 | 2 | 3 | - | - | 6 | - | - | 9 | 1,2,3,6,9 | |
| data[6] | - | - | - | - | - | - | 7 | - | - | 7(確定) | |
| data[7] | - | 4 |
5 |
- | - | - | - | 2,3,4,5 | |||
| data[8] | 1 | 2 | 3 | - | - | 6 | - | - | - | 1,2,3,6 | |
| q_k | 3 | 5 | 7 | 2 | 2 | 3 | 1 | 1 | 5 | ||
| pair_k_in[k][0] | - | - | - | 3 | 3 | - | - | - | - | ||
| pair_k_in[k][1] | - | - | - | 7 | 7 | - | - | - | - |
上の表の局面を考える。data[0~8]は走査した9マスを示す。q_kは候補kが走査した中にある数。
kがある数q_kを求める（表を縦に見る）q_k=2となるkについて、その候補があるマスの場所をpair_k_in[k][2]に格納q_k=2となるkについて、l = k+1 ~ 9を走査してpair_k_inの組が一致したら、一致したマスで候補をk, lのみにする以上。これでかなり強力な数独攻略プログラムになった。
「候補を消す関数」ができたので詰むことがなくなって嬉しい。逆に言えば、findPair()やonly_two_pair_lrb()が無いと解けない問題があったことに感謝である。
_lrb式の走査法↓を思いついたのも運がよかった。これがなければコードがクソ長くなってしまっていただろう。
改良版で重要な要素は、あとはファイル入出力くらいかと思うので次はそれについて書こうと思う。
おしまい。
3x3のブロックに分けられた9x9のマス目があり、行・列・ブロックの中に1~9の数字を重複しないように入れていくパズルです。
ナンプレの解き方、ネットで調べるとなんか難しいのばっかりで、そんなレアケース見つかんねぇよ！って感じのばっかりなのですが、僕がやっている解法は割と見つけやすくて、連鎖的にサクサク埋まりがちだと思うので紹介しようと思います。
盤面の画像がサイズまちまちで見づらいのは許してくだせぇ
初歩。メインではない。ぱっと見でわかる人は飛ばしてください。 盤面を見ていって数字を埋めるまでの思考を紹介します。
右から左に見ていって、
上のブロックに注目して、
緑のマスに注目して、
ちょっと見つけにくいテクニックですが紹介
一番上の列をを見て、
左上のブロック、
どう見ても緑のマスに4入れるしかないじゃん！（書くの飽きた）
数字を直接確定させるのはまあみんな分かりますよね。はい。
続きを読むプログラム（C言語）にナンプレ（数独）を解かせる↓の続編です。
パワーアップして、それなりに満足できるクォリティに仕上がったので。
丁寧なメモ・雑な説明、という感じで連載します。
今回はgithubにデータを置いています。要らない記述が残ってたり（後で見返すときのためコメント付きで）なんか整ってない部分とかありますが、後々説明するか、こそっと書き換えます笑
GitHub - oha-yashi/sudoku: ナンプレ攻略プログラム
そこにも書いてありますが、ターミナルやらコマンドプロンプトを開いて （C言語を使える環境で）以下のコマンドを順番に打ち込みます。
$ git clone https://github.com/oha-yashi/sudoku $ cd sudoku $ make compile
cloneできなかったら無理やりダウンロードしてsudokuフォルダに入れてください。はい。
make compileで失敗したら大体、makefileのコマンド冒頭のインデントがスペースになってしまっているのでtabにすれば通ります。
追記：makeってwidowsだと無いんですか、知らんかった。頑張ってインストールしてください（投げやり）。まあ、
cc -c source/calc.c cc -c source/fileio.c cc -c source/main.c cc -c source/menu.c cc -c source/setting.c cc -o solveSudoku main.o calc.o fileio.o menu.o setting.o -lncurses
make compileの代わりにこれ↑をディレクトリsudokuで実行してもいけます。
ダウンロード、コンパイル完了したら
$ make do
で実行です。
上下左右キーで移動、0~9キーで入力、その他機能をところどころのキーに割り当てています。
PCゲームでよくあるawsdで左上下右、というのは対応してません。
今時矢印キーない奴は雑魚でしょw知らんけど。
僕が使ってるのmacbookなのでテンキーじゃないから、awsdで操作すると1234あたりのキーと手がぶつかるのでそういう仕様になりました。
$ $(赤色)は現在見ているマス! !(青色)はマスに入る候補が2つのマス。ちょっと前、手動で候補を切り替えないと進まなかった時代に参考にしていた。? ?(緑色)はマスに入る候補が3つのマス。次の盤面をファイル読み込みで解いてみます。それなりの難問です。
別に、矢印キーで移動してマス目を埋めていっても構いません。
それはそれで、1つ入れたり移動するたびに（ただの移動の時にも候補の探索を行なっている）数字が埋まっていくので楽しいですが、一気に解にたどり着くため事前にテキストデータにしておきます。
0 . 準備
読み込むファイルを用意します。コンパイルしたディレクトリにnpというフォルダがあるのでそこにdemo1.datというファイルを作ります。（名前は自由に書き換えて構いませんが、置く場所はnpフォルダ限定です）。
demo1.datの中身は次のようにします。詳しいことは後々。
%1d 000 400 065 080 000 000 700 090 000 000 000 120 065 008 000 004 000 000 000 600 009 100 000 700 000 005 000
1行目は呪文だと思っていただいて、その下に盤面と同様の数字が並んでいるのがわかると思います。
1 . 実行
コンパイルした（実行ファイルsudokuSolveがある）ディレクトリで
$ make do
2 . 開始画面が表示される
なんでもいいのでキーを打ちます。[Enter]
3 . 初期画面
今回は自作ファイルを読み込むので、i
4 . ファイル名入力
今回、読み込みファイルはnp/demo1.datです。npフォルダの中にあるのは指定済み。demo1.dat[Enter]
5 . 読み込み完了
もう一回[Enter]
6 . 数字が入る
この後は[Enter]連打で終わりまで行きます
7 . 完成!!
無事全マスが埋まりました。終わりなのでq
8 . 終了画面
なんでもいいのでキーを押して終了します。
続きを読む