数独solverの最小コードに挑戦
数独solverは昔作ったことがあるのでsolver作成という点では再挑戦ということになる。しかし今回少し趣を変えてコード量を減らすことに重点を置いた。なので速度と可読性はとりあえず度外視した。とはいえ、有用な時間に解けなければ意味がないのである程度速度も考慮に入れる。あとあんまり暗号化が酷いのも何なのである程度可読性も考慮しました。まあ中途半端です。
そして出来上がったコードが以下の通り。
bool Sudoku3x3(int* t, int i = 0){ const static int b_[] = { 0, 1, 2, 9, 10, 11, 18, 19, 20 }; for (; i < 81; ++i) { if (t[i] == 0) { bool c[10] = {}; int h((i / 9) * 9), v(i % 9), b((i % 9 / 3) * 3 + (i / 27) * 27); for (int j = 0; j < 9; ++j, ++h, v += 9) { c[t[v]] = c[t[h]] = c[t[b + b_[j]]] = true; } for (int n = 1; n <= 9; ++n) { if (!c[n]) { t[i] = n; if (Sudoku3x3(t, i + 1)) return true; } } t[i] = 0; return false; } } return true; }
実際に動かす場合は以下の通り
int table[] = { 8,0,0, 0,0,0, 0,0,0, 0,0,3, 6,0,0, 0,0,0, 0,7,0, 0,9,0, 2,0,0, 0,5,0, 0,0,7, 0,0,0, 0,0,0, 0,4,5, 7,0,0, 0,0,0, 1,0,0, 0,3,0, 0,0,1, 0,0,0, 0,6,8, 0,0,8, 5,0,0, 0,1,0, 0,9,0, 0,0,0, 4,0,0, }; Sudoku3x3(table);//上書きされる
20行程で完成。まあ改行はいくらでも減らせるので行数での比較は意味ないですけど。
本当に総当たりなので結構重いと思いきや、意外と速かった、ていうか以前作った物より速いんだけど・・・。ただし、試しに4x4や5x5を作ったらやっぱり重かった。しかし3x3なら十分実用的(?)な速度だと思います。
ついでに練習のためにswift3.0でも書いてみました。少し可読性を上げています。
func Sudoku3x3(table t:inout [[Int]], _ index:Int = 0)->Bool{ //サイズ取り出し。9x9のはず let sy = t.count let sx = t[0].count //総当たり for i in index..<sy * sx{ //現在の座標 let y = i / sx let x = i % sx //0以外は既に埋まっているので飛ばす if t[y][x] == 0 { //縦と横とブロック内で存在する数値を調べる var c = [Bool](repeating: true, count:10) let bx = x / 3 * 3//ブロックの左上 let by = y / 3 * 3 for j in 0..<9{ c[t[y][j]] = false//横チェック c[t[j][x]] = false//縦チェック c[t[by+j/3][bx+j%3]] = false//ブロック内チェック } //存在しなかった数値を順番に入れてみる。 for (n, test) in c.enumerated(){ if test { t[y][x] = n //次に進む if Sudoku3x3( table:&t, i+1 ){ //最後まで埋まった return true } } } //どの数値もダメだった。前に戻る。 t[y][x] = 0 return false } } //最後まで埋まったので成功 return true }
なにげに初めてのswiftプログラミングです(^^;たったこれだけだけどえらい苦労しました。でもおかげさまでswift開発力が格段に上がりました。
ところでシンタックスハイライト、swiftはないんだな・・・。