パズル勉強会

パズルプログラミング勉強会

第3課題:カックロ

by パソコン初心者


どうも数独は予想以上に皆がホイホイ解いてしまったので、 次の課題を用意したほうがよい状況になってしまった。 それで、いろいろ考えて、数独と少しは似ているところもあるカックロを 第3課題とすることに決めました。

■問題データ: kakrovol1.data  (遊びたい人は、問題集 Vol.1)
これは、私のページで公開しているカックロ問題集のVol.1の全問題データである。 これを読み込みながら、ホイホイ解けることでしょうかね。 パズルプログラムの検証用に使う分にはいくらでも利用してくだされ。

■解答データ: kakrovol1.txt
もしかして正解と思われる解答データです。保証はしませ〜ん。

■C++ ソース: Kakro.h, Kakro.C
開発途中もいいところ(正確には放棄中)なのですが、まあ動くので公開。
問題は、知識がほとんど入っていないこと。もちろん、計算能力ゼロ。
特徴は、ビット(可能な組合せ)を調べているだけ。計算は苦手なので、一切なし。 複数のマスがタテまたは横に繋がったものをグループと呼んでいて、 グループを調べるとき、タテ、ヨコを別個に調べているだけで、 タテとヨコが交差するというカックロの特徴を利用したプログラム部分は1行もない! それでも何とか解けるのは、各マスに可能性の残っている数字をビットで表し 記憶するようにしているから。1ビットだけ立っていたら決定。
そんな横着プログラムでも、仮定をちょっと入れたら、 CPUの腕力で解けるようになってしまったので、続ける気力が無くなった。 つい、デカビロも解いてみたが、9秒程で解けてしまった。 上の例題100問(akrovol1.data)が4.3秒もかかるので、決して高速ではない。 上の問題データを1秒以内が、速度を目指す場合の参考時間であろうか。

■高速なプログラム:
勉強会参加者の高速なプログラムが公開されました。
100問0.1秒以下、デカビロ1問も0.1秒以下のプログラムです。 データは、上の問題データがそのまま使えます。
2001年8月22日
2001年9月17日 解答データを追加
2001年10月5日 中断ソースを追加
2002年1月28日 参加者の高速プログラムを紹介

パズル勉強会