すごいです！
フラグテーブルにそんな力があったとは。
もうパソコンの前で体が止まってしまいました。
プログラムってすごいですね。
自分で調べて見たところ、
フラグを立てる場合と立てない場合で、
Leftset関数の実行回数が２２万回ほど違いました。
自分でもいつかこんなプログラムが作れるのでしょうか。
気長にがんばります。

ここでまた質問させてください。
hairi１D関数ではLeftset関数、Upset関数を使った縦横１ラインの背理法をやっているわけですか？
Leftset関数、Upset関数が１を返す時は矛盾があったときで、
それを利用して背理法を行ってると理解したんですけどどうですか。
backtrackのところも背理法のような気がするんですが、
最後に仮定した数字を０に戻してしまうのはなぜなんでしょう？
１に仮定したら２に、２に仮定してたら１にするのとは違うのでしょうか？
PSという変数は仮定中の確定マスを戻すときに使ってるんですね。
ということはhairi１D関数は背理法のなかでの背理法ということになるんですかね。
処理の軽い背理法ということでしょうか。
今回の質問は自分の理解の確認みたいな感じですね。
まだまだわからないことだらけです。
前回はお忙しい中質問に答えていただいてありがとうございました。
また時間がありましたらよろしくお願いします。

[以前の投稿記事]をクリックすると「投稿者が記入されていません。」となります。
ちなみにブラウザはネスケ4.7です。

掲示板を新しくしましたが見た目は全く変わってないですね。あの有名な
Web裏技からのコピーですが独自に改造した部分が３箇所あります。

【1】書込みモードの自動判定
    自動改行モードと図表モードが自動判定されます。
    改行をしない(本当はやめて)で書込みされても自動改行されます。
    また、図表やソースコードが記入された通りに表示されます。

【2】古い投稿記事の自動HTML化
    古い投稿記事が自動でHTMLファイル化され消滅することはありません。
    １０件毎の目次ページも自動作成されます。(右側のコメントは手動)

【3】記入もれの事前チェック
    JavaScriptを使って記入漏れがCGI実行前にチェックされます。
    (これはどってことないか。)

動作チェックが不十分なので「書込み出来ない」ような時は直接メール
で教えて頂ければ幸いです。尚、力不足のためタグは一切使えません。

お絵かきロジックはずっと昔に卒業したと思っているので確かな記憶がうすれて
いるのですが．．．．．．

サトシさん wrote:
> 高橋さんのプログラムに出てくるフラグテーブルっていうのは、
> どういう仕組みで入っているんですか？

ご指摘のとおり処理を効率よくするためのものでフラグテーブルは処理を高速化
する方法として常套手段のようなものなので、特にたいしたことをやっている訳
ではありません。やっても無駄な探索をしないようにする為に探索過程を管理
しています。

1. x軸ラインとy軸ラインにそれぞれフラグを設ける。(初期値は総て0)
2. フラグが0ならそのラインに重なり探索を実行してフラグを1にする。
3. フラグが1ならそのラインに1D背理探索を実行してフラグを2にする。

これだけだと何の意味もありませんが次が重要なポイントになります。

4. x軸を走査中に新たに確定したマス[x,y]があればそのy軸のフラグを0にする。
5. y軸を走査中に新たに確定したマス[x,y]があればそのx軸のフラグを0にする。

もちろんx軸走査の次はy軸走査、y軸走査の次はx軸走査とループしています。
「新たに確定するマスが有り得ないと分かっている探索」は決して実行されない
し、フラグを0にされたラインはいずれ再び探索が実行されることになります。

また、フラグ0をフラグ1にする処理を最優先します。つまり総てのフラグが1に
なって初めて1D背理探索に制御が移ります。1D背理探索中に新たに確定したマス
があればフラグ0が出現するので1D背理探索を中断して直ぐに重なり探索に制御
が移ります。処理の軽い重なり探索があくまでも最優先です。

総てのフラグが2になっても解に達していない場合は再帰探索が実行されます。
この時、仮定の対象にしたマス[x,y]に対応するx軸y軸の2つのフラグのみを0に
して前述した確定探索を試みます。徹底して無駄な探索をしない仕組みです。

こんにちは、高橋さん。
この間やっと重なり検索のおおざっぱな理解が終わりました。
あれだけのプログラムでかなりの仕事をさせてしまってますね。
ぼくが最初に作ってたのは細かい仕事をいろんな関数にわけてしまってたので
もう自分でもわけがわからなくなってしまっていました。

ここで質問とかしてもよろしいですか？
高橋さんのプログラムに出てくるフラグテーブルっていうのは、
どういう仕組みで入っているんですか？
処理を効率よくするために入っているのはわかったんですが、
仕組みがよくわかりませんでした。
もしよろしければ教えていただきたいと思います。

これから背理法について勉強してみます。
かなり難しそうですががんばってみようと思います。
それでは。

サトシさん、はじめまして。

「お絵かきロジック」の自動解答プログラムは正直言って奥が深かった記憶があります。
私のプログラムは「スモールモデル(←死語)」しか使えない環境でウジウジと開発した
ものなので、現在のＣ言語コンパイラなら「スタック処理」なんて考える必要はありま
せん。混乱させてすみません。是非、私のよりいいプログラムを書いてください。

また、遊びにきて下さい。

はじめまして。サトシといいます。
Ｃ言語初心者でイラストロジックの解析プログラムに挑戦しています。
高橋さんのプログラム拝見させていただきました。
もうすごいの一言でした。
アルゴリズムの勉強って大切なんですね。
とても勉強になります。
そしてプログラムへの興味もまた倍増です。
スタック処理とか二次元背理法とかさっぱりですが、
がんばって勉強してみたいと思います。
それではまた来ます。
よろしくお願いします。

あけましておめでとうございます。

広井さん、コメントありがとうございます。

今年もスローなまテンポでＨＰを更新していくことに
なりそうですが、ときどき遊びに来てください。

皆さん、今年もよろしくお願い申し上げます。

高橋さん、こんにちは。広井です。

１１パズル最長手数解の探索、素晴らしいですね。
解説もわかりやすくて、とても良かったです。

パズルの偶奇性を使った最小完全ハッシュ関数の作成は、
お見事というしかありません。脱帽です。
この方法は、ほかのパズルにも応用できるかもしれませんね。
それにしても、６×２の最長手数が８０手もあるとは驚きました。

過去の書き込みを拝見しましたが、貴重な情報が多いですね。
公開ありがとうございます。いろいろ参考にさせていただきます。

では、よいお年を。

このコーナーに書込みして下さった方々、どうもありがとうございます。

その中には大変に貴重な情報が含まれているものもありますので【過去の書込み】
を参照しやすい形で公開することにしました。何か参考になるものがあれば幸いです。