|
|
|
|
コメント(162)
xtermのカラー・エスケープ・シーケンス機能を備えたWindows用の端末ソフトをご存知ありませんか？
NumberPlace.lisp 3.0.9版に実装したAdvanced Coloringの解説盤面ではxterm 256 colorというカラー表示をサポートしているのですが、Windows標準のcmd.exeは該当する機能をサポートしていないのでモノクロ表示しか対応できません（Linux上で実行する場合はカラー表示可能です）。
xterm 256 colorというエスケース・シーケンスに対応した端末ソフト上でNumberPlace.lispを実行すればカラー表示が可能なのですが、私は残念ながら対応しているWindows用端末ソフトを知りません。
cmd.exeの他にWindows Power Shell, WinBashは試してみましたが対応していませんでした。CygWinという選択肢もありますが、ちょっと大規模すぎるかなと思います。
どなたかxterm 256 colorに対応しているWindows用端末ソフトをご存知でしたら教えていただけないでしょうか。_o_
NumberPlace.lisp 3.0.9版に実装したAdvanced Coloringの解説盤面ではxterm 256 colorというカラー表示をサポートしているのですが、Windows標準のcmd.exeは該当する機能をサポートしていないのでモノクロ表示しか対応できません（Linux上で実行する場合はカラー表示可能です）。
xterm 256 colorというエスケース・シーケンスに対応した端末ソフト上でNumberPlace.lispを実行すればカラー表示が可能なのですが、私は残念ながら対応しているWindows用端末ソフトを知りません。
cmd.exeの他にWindows Power Shell, WinBashは試してみましたが対応していませんでした。CygWinという選択肢もありますが、ちょっと大規模すぎるかなと思います。
どなたかxterm 256 colorに対応しているWindows用端末ソフトをご存知でしたら教えていただけないでしょうか。_o_
○daigoさん＞
「xterm」は全く知らないので、
ご免なさい。(^_^;
「3D Medusa(Advanced Coloring)」を
ベクターで調べたけどまだ登録していなかったので、
もう少し待ちます。
あと、質問しても良いですか？
・質問
「121」の「(1)〜(5)」はとても難しくて、
時間が掛かりますのでまだ解読出来ませんが、
「R3C4とR3C6」は共に「７」にある「Strong link」の２値セル同士ですが、
「R9C7」の「７」を見て上下、左右、ブロックを探して、
「Strong link」の「７」を見ましたが見当たりませんでした。
私の推測なんですが、「Strong link」だけじゃなくて、
「Weak link」の２値セル同士でも可能なのでしょうか？
例えば、「R9C7」と「R7C9（または「R6C7」？）」にある
「Weak link」の「７」ではないのですか？
どうぞ、宜しくお願い致します。
・一応、他の方への参考です。
※「link」とは、上下、左右、ブロックに繋がっているセル同士の事。
※「Strong link」とは、セル同士に入っている候補数字で同じ候補数字を持ち、
それ以外のセルには同じ候補数字は入っていない事。
※「Weakg link」とは、２つの候補数字しかないセル同士で、
同じ候補数字が入っている事。
「xterm」は全く知らないので、
ご免なさい。(^_^;
「3D Medusa(Advanced Coloring)」を
ベクターで調べたけどまだ登録していなかったので、
もう少し待ちます。
あと、質問しても良いですか？
・質問
「121」の「(1)〜(5)」はとても難しくて、
時間が掛かりますのでまだ解読出来ませんが、
「R3C4とR3C6」は共に「７」にある「Strong link」の２値セル同士ですが、
「R9C7」の「７」を見て上下、左右、ブロックを探して、
「Strong link」の「７」を見ましたが見当たりませんでした。
私の推測なんですが、「Strong link」だけじゃなくて、
「Weak link」の２値セル同士でも可能なのでしょうか？
例えば、「R9C7」と「R7C9（または「R6C7」？）」にある
「Weak link」の「７」ではないのですか？
どうぞ、宜しくお願い致します。
・一応、他の方への参考です。
※「link」とは、上下、左右、ブロックに繋がっているセル同士の事。
※「Strong link」とは、セル同士に入っている候補数字で同じ候補数字を持ち、
それ以外のセルには同じ候補数字は入っていない事。
※「Weakg link」とは、２つの候補数字しかないセル同士で、
同じ候補数字が入っている事。
> びーにぃさん
> 「R9C7」の「７」を見て上下、左右、ブロックを探して、
> 「Strong link」の「７」を見ましたが見当たりませんでした。
R9C7の「７」は同じセル内の「３」とのstrong linkなので彩色されています。2値セルの場合はセル内でのstrong linkが成立しているということです。Advanced Coloringでは（Nice Loopと違って）strong linkだけを利用しています。
ベクターへの登録はちょっとミスがあって修正版を再登録申請しています。早ければ今日、公開してもらえるかもしれません。探すときは「NumberPlace309.zip」で探してみてください。^^
> 「R9C7」の「７」を見て上下、左右、ブロックを探して、
> 「Strong link」の「７」を見ましたが見当たりませんでした。
R9C7の「７」は同じセル内の「３」とのstrong linkなので彩色されています。2値セルの場合はセル内でのstrong linkが成立しているということです。Advanced Coloringでは（Nice Loopと違って）strong linkだけを利用しています。
ベクターへの登録はちょっとミスがあって修正版を再登録申請しています。早ければ今日、公開してもらえるかもしれません。探すときは「NumberPlace309.zip」で探してみてください。^^
> 「121」の「(1)〜(5)」はとても難しくて、 時間が掛かります
#125の画像は実際の出力例なのですが、盤面のすぐ下をよく見ていただくと「(r#5)」という部分が見えると思います。これはルールの5番が適用された、という意味です。盤面ごとに「r#1〜r#6」が付記されます。
公開依頼中のプログラムにはAdvanced Coloringの例題として
adv-coloring-01 〜 adv-coloring-04
というサンプルが含まれています。
(teach adv-coloring-01)
などとして実行してみてください。各ルールは文章で書くと難しく感じるかも知れませんが、実際の盤面と見比べてみるとすぐに分かると思います。ヘルプ関数「help」にもルールの文面を入れてありますので画面上でも参照できます。
(help 'advanced-coloring)
で表示できます。
#125の画像は実際の出力例なのですが、盤面のすぐ下をよく見ていただくと「(r#5)」という部分が見えると思います。これはルールの5番が適用された、という意味です。盤面ごとに「r#1〜r#6」が付記されます。
公開依頼中のプログラムにはAdvanced Coloringの例題として
adv-coloring-01 〜 adv-coloring-04
というサンプルが含まれています。
(teach adv-coloring-01)
などとして実行してみてください。各ルールは文章で書くと難しく感じるかも知れませんが、実際の盤面と見比べてみるとすぐに分かると思います。ヘルプ関数「help」にもルールの文面を入れてありますので画面上でも参照できます。
(help 'advanced-coloring)
で表示できます。
ベクターに登録させてもらったNumberPlace.lisp 3.0.9ですが２つほど実験的な機能を実装してみました。
ひとつめは理詰めだけで解に到達できる手筋のリストを返す関数「find-logical-path」です。
cl-user> (find-logical-path sample-board-9)
とすると解に到達するために使用した手筋のリストと手筋の合計適用回数を返します。
(do-primary do-fix-unmoved do-localization do-primary do-localization
do-n-tuples do-localization do-n-grid do-n-tuples do-n-grid do-n-tuples
do-n-grid do-n-tuples do-localization do-n-tuples)
75
用意されているどの手筋でも手を進められなかった場合は手筋のリストとして「nil」を返します。手を進められなかった盤面は
cl-user> (evil-boards)
と実行することで該当する盤面を呼び出せます。返された手筋のリストは返される手筋のリストを適当な変数に保存しておき
cl-user> (setf log-list (find-logical-path sample-board-9))
cl-user> (do-logical-path log-list)
とすることで再実行可能です。
この「find-logical-path」が手筋のリストとして「nil」を返す場合はNumberPlace.lispが実装している手筋をどのような順序で組み合わせても試行錯誤なしで解に到達することは不可能であることを示しています。
何故ならば「find-logical-path」関数は与えられた n 個の手筋を深さ優先で全数探索し、n個のどの手筋でも解決できない盤面が現われると１段階前の盤面に戻り、前回までに適用していない手筋を使って手を進めようとします。適用できる手筋がなかった場合は更に１段階前の盤面に戻ります。以上を繰り返し、最初の盤面に対して適用できる n個の手筋が尽きたときに「nil」を返します（解に到達したときは前述のように解に至る手筋のリストを返します）。
したがって「find-logical-path」関数に対して以下が成立します。
・手筋のリストとして「nil」が返される場合はNumberPlace.lispが実装している手筋をどのような順序で組み合わせても与えられた問題に対して試行錯誤なしで解に到達することは不可能。
・「find-logical-path」が返す手筋のリストが唯一の解法手順とは限らない。
・「teach」関数が試行錯誤関数を使用した場合でも「find-logical-path」関数で試行錯誤なしで解に到達する手筋のリストが得られる可能性がある。
「find-logical-path」関数が「nil」を返した場合、「evil-board」関数で手を進められなかった盤面を呼び出せますが、この盤面を検討することで解決に必要な手筋を検討することが出来ます。
ひとつめは理詰めだけで解に到達できる手筋のリストを返す関数「find-logical-path」です。
cl-user> (find-logical-path sample-board-9)
とすると解に到達するために使用した手筋のリストと手筋の合計適用回数を返します。
(do-primary do-fix-unmoved do-localization do-primary do-localization
do-n-tuples do-localization do-n-grid do-n-tuples do-n-grid do-n-tuples
do-n-grid do-n-tuples do-localization do-n-tuples)
75
用意されているどの手筋でも手を進められなかった場合は手筋のリストとして「nil」を返します。手を進められなかった盤面は
cl-user> (evil-boards)
と実行することで該当する盤面を呼び出せます。返された手筋のリストは返される手筋のリストを適当な変数に保存しておき
cl-user> (setf log-list (find-logical-path sample-board-9))
cl-user> (do-logical-path log-list)
とすることで再実行可能です。
この「find-logical-path」が手筋のリストとして「nil」を返す場合はNumberPlace.lispが実装している手筋をどのような順序で組み合わせても試行錯誤なしで解に到達することは不可能であることを示しています。
何故ならば「find-logical-path」関数は与えられた n 個の手筋を深さ優先で全数探索し、n個のどの手筋でも解決できない盤面が現われると１段階前の盤面に戻り、前回までに適用していない手筋を使って手を進めようとします。適用できる手筋がなかった場合は更に１段階前の盤面に戻ります。以上を繰り返し、最初の盤面に対して適用できる n個の手筋が尽きたときに「nil」を返します（解に到達したときは前述のように解に至る手筋のリストを返します）。
したがって「find-logical-path」関数に対して以下が成立します。
・手筋のリストとして「nil」が返される場合はNumberPlace.lispが実装している手筋をどのような順序で組み合わせても与えられた問題に対して試行錯誤なしで解に到達することは不可能。
・「find-logical-path」が返す手筋のリストが唯一の解法手順とは限らない。
・「teach」関数が試行錯誤関数を使用した場合でも「find-logical-path」関数で試行錯誤なしで解に到達する手筋のリストが得られる可能性がある。
「find-logical-path」関数が「nil」を返した場合、「evil-board」関数で手を進められなかった盤面を呼び出せますが、この盤面を検討することで解決に必要な手筋を検討することが出来ます。
ふたつめは試行錯誤回数を最小化するための設定です。
cl-user> (permit-cheat t)
とすると試行錯誤が必要となった場合に、あるセル内の複数の候補数字から仮候補を選択する際に、あらかじめ高速で解を求められる方法（Bruteforce法）で求めておいた正解候補を選択するようになります。
試行錯誤が必要となった場合に常に正解となる仮候補を選択するので一切の無駄な試行錯誤を行ないません。
cl-user> (permit-cheat nil)
とすることで、この機能をオフにできます。実際には「novice-level」や「machine-level」などのレベルをプリセットする関数内で個別に設定しています。
cl-user> (permit-cheat t)
とすると試行錯誤が必要となった場合に、あるセル内の複数の候補数字から仮候補を選択する際に、あらかじめ高速で解を求められる方法（Bruteforce法）で求めておいた正解候補を選択するようになります。
試行錯誤が必要となった場合に常に正解となる仮候補を選択するので一切の無駄な試行錯誤を行ないません。
cl-user> (permit-cheat nil)
とすることで、この機能をオフにできます。実際には「novice-level」や「machine-level」などのレベルをプリセットする関数内で個別に設定しています。
○daigoさん＞
・「adv-coloring-01」の問題
#=======================================================================#
0:0> (r#5) [R7C9]のX=7は[R9C7]のB=7と[R7C6]のG=7を同時に見ることができる位置です。
==> R7C9<>7
#=======================================================================#
一回目の処理なんですが、
左上の画像のように、「R8C8」の「B(3)」から始まって、
「R9C7」の「G(3)」→「R9C7」の「B(7)」→
「R7C9」の「(X(Gの7)」。
右上の画像のように、「R7C6」の「G(7)」から始まって、
「R7C6」の「B(3)」→「R7C1」の「G(3)→「R9C3」の「B(3）」→
「R9C7」の「G(3)」→「R9C7」の「B(7)」→
「R7C9」の「(X(Gの7)」。
そうすると、１つのStrongの２値セルを「B」から始まって最後のセルまで終わり、
もう１つのStrongの２値セルを「G」から始まって同じ最後のセルまで終わると
同じ値になるので、「R7C9」の候補数字「７」を削除出来るという
「Advance-Coloring」解法はあっていますか？
どうぞ宜しくお願いします。
・「adv-coloring-01」の問題
#=======================================================================#
0:0> (r#5) [R7C9]のX=7は[R9C7]のB=7と[R7C6]のG=7を同時に見ることができる位置です。
==> R7C9<>7
#=======================================================================#
一回目の処理なんですが、
左上の画像のように、「R8C8」の「B(3)」から始まって、
「R9C7」の「G(3)」→「R9C7」の「B(7)」→
「R7C9」の「(X(Gの7)」。
右上の画像のように、「R7C6」の「G(7)」から始まって、
「R7C6」の「B(3)」→「R7C1」の「G(3)→「R9C3」の「B(3）」→
「R9C7」の「G(3)」→「R9C7」の「B(7)」→
「R7C9」の「(X(Gの7)」。
そうすると、１つのStrongの２値セルを「B」から始まって最後のセルまで終わり、
もう１つのStrongの２値セルを「G」から始まって同じ最後のセルまで終わると
同じ値になるので、「R7C9」の候補数字「７」を削除出来るという
「Advance-Coloring」解法はあっていますか？
どうぞ宜しくお願いします。
> #134 びーにぃさん
早速、NumberPlace.lisp 3.0.9をダウンロードして下さり、ありがとうございます。
ご質問の件ですが、左図、右図ともR9C7のB=7からR7C9のX=7へのstrong linkは（同じブロック内のR8C7に７が存在しているので）成立していません。したがって、残念ながら、この時点で#134の論理は成立していません。
ノードAとノードBの間にstrong linkが成立するとは
・AとBが同じハウス（行・列・ブロックのいずれか）に属す。
・AとBがstrong inferenceを満たす。
ことです。strong inferenceを満たすとは
・if A is false, then B is true.
・if B is false, then A is true.
を満たすことです。
つまりセル単位では２値セル、ハウス単位では２所セルだけがstrong linkです。完全に２択ですからstrong linkが成立しているグラフについて、任意のノードAとBからリンクをたどって同じノードCに達したときにパリティ（今の場合はBかG）が異なると言うことはあり得ません。
早速、NumberPlace.lisp 3.0.9をダウンロードして下さり、ありがとうございます。
ご質問の件ですが、左図、右図ともR9C7のB=7からR7C9のX=7へのstrong linkは（同じブロック内のR8C7に７が存在しているので）成立していません。したがって、残念ながら、この時点で#134の論理は成立していません。
ノードAとノードBの間にstrong linkが成立するとは
・AとBが同じハウス（行・列・ブロックのいずれか）に属す。
・AとBがstrong inferenceを満たす。
ことです。strong inferenceを満たすとは
・if A is false, then B is true.
・if B is false, then A is true.
を満たすことです。
つまりセル単位では２値セル、ハウス単位では２所セルだけがstrong linkです。完全に２択ですからstrong linkが成立しているグラフについて、任意のノードAとBからリンクをたどって同じノードCに達したときにパリティ（今の場合はBかG）が異なると言うことはあり得ません。
> #136 daigoさん
何となく理解しました。
先ず、「Advanced-Coloring」を使用して、
「R7C6」の strong link を注目すると、
※ #134 の問題です。
＜左図：B＞
・最初に、
「R7C6」の「B(3)」を入れると、
「R7C1」の「G(3)」には入れないので、
「R9C3」の「B(3)」を入れて、
「R9C7」の「G(3)」には入れないので、
「R9C7」の「B(7)」を入れると、
「R7C9」の候補数字「7」には入れないので、
仮に「8」を入れます。
＜右図：B＞
・逆に、
「R7C6」の「G(7)」を入れると、
「R7C6」の「B(3)」には入れないので、
「R7C1」の「G(3)」を入れて、
「R9C3」の「B(3)」には入れないので、
「R9C7」の「G(3)」を入れると、
「R9C7」の「B(7)」には入れません。
すると、既に「R7C6」の「G(7)」が入っているので、
「R7C9」の候補数字「7」も入れないので、
やはり「8」が入ります。
・つまり、
「R7C6」の「B(3)」に入れても
「R7C6」の「G(7)」に入れても、
「R7C9」の候補数字「7」には入れないので
「8」が確定するという解法はあっていますか？
どうぞ、宜しくお願いします。
何となく理解しました。
先ず、「Advanced-Coloring」を使用して、
「R7C6」の strong link を注目すると、
※ #134 の問題です。
＜左図：B＞
・最初に、
「R7C6」の「B(3)」を入れると、
「R7C1」の「G(3)」には入れないので、
「R9C3」の「B(3)」を入れて、
「R9C7」の「G(3)」には入れないので、
「R9C7」の「B(7)」を入れると、
「R7C9」の候補数字「7」には入れないので、
仮に「8」を入れます。
＜右図：B＞
・逆に、
「R7C6」の「G(7)」を入れると、
「R7C6」の「B(3)」には入れないので、
「R7C1」の「G(3)」を入れて、
「R9C3」の「B(3)」には入れないので、
「R9C7」の「G(3)」を入れると、
「R9C7」の「B(7)」には入れません。
すると、既に「R7C6」の「G(7)」が入っているので、
「R7C9」の候補数字「7」も入れないので、
やはり「8」が入ります。
・つまり、
「R7C6」の「B(3)」に入れても
「R7C6」の「G(7)」に入れても、
「R7C9」の候補数字「7」には入れないので
「8」が確定するという解法はあっていますか？
どうぞ、宜しくお願いします。
> #139 daigoさん
よく分かりませんが、
てっきり「 #138 」のように、
「R7C9」の「X=7」を削除できると思いましたが、
違うみたいですみません。(^_^;
#=======================================================================#
0:0> (r#5) [R7C9]のX=7は[R9C7]のB=7と[R7C6]のG=7を同時に見ることができる位置です。
==> R7C9<>7
＿＿＿↑ ここ。
「==> R7C9<>7」は、「7を削除する」では無く、
「7を削除出来る場所をチェックする」ということですよね？
そうしたら、他の場所も探して、
見つかったら削除出来る場所をチェックしておいて、
見つからなくなかったら「Advanced Coloring」を処理する
ということであっていますか？
※「同時に見ることができる位置」をイメージに、
※図を作りました。
よく分かりませんが、
てっきり「 #138 」のように、
「R7C9」の「X=7」を削除できると思いましたが、
違うみたいですみません。(^_^;
#=======================================================================#
0:0> (r#5) [R7C9]のX=7は[R9C7]のB=7と[R7C6]のG=7を同時に見ることができる位置です。
==> R7C9<>7
＿＿＿↑ ここ。
「==> R7C9<>7」は、「7を削除する」では無く、
「7を削除出来る場所をチェックする」ということですよね？
そうしたら、他の場所も探して、
見つかったら削除出来る場所をチェックしておいて、
見つからなくなかったら「Advanced Coloring」を処理する
ということであっていますか？
※「同時に見ることができる位置」をイメージに、
※図を作りました。
> 「==> R7C9<>7」は、「7を削除する」では無く、
> 「7を削除出来る場所をチェックする」ということですよね？
えっと、「R7C9には７は存在し得ない ==> 7を削除できる」で合ってます。R7C9から７を削除できる理由を誤解されているのではないかという意味で書きました。> #139
#140の例でもそうですが、R7C9の７はstrong linkの構成要素ではありません。何故なら最後のブロック内にはR7C9, R8C7, R9C7の３カ所に７が存在しますから、このブロック内で７はstrong linkを構成できません。つまりR7C9の７とR9C7の７はstrong linkの関係にありません。
同様に７行目についても７はR7C1, R7C4, R7C6, R7C9の４カ所に存在しますから、やはりR7C9の７とR7C6の７もstrong linkの関係にありません。
Gと表記された候補数字群とBと表記された候補数字群はAdvanced Coloringによる塗り分けによって互いに排他的な関係にあることが判明した候補数字群です。つまり盤面上でGと表記された候補数字群のいずれかひとつでも真であるならば他のすべてのGも真であり、他のすべてのBは偽です。
Gと表記された候補数字群とBと表記された候補数字群のどちらが真であるかは確定できませんが、少なくともどちらか一方が真であることは確定しています（もし両方が偽であれば２値セル内、あるいは２所セル内の候補数字が共に空となり矛盾）。
したがって、R7C9の７は、R7C6あるいはR9C7のいずれが７であるにせよ、同一の行内または同一のブロック内に２つ以上の７が存在できないのでR7C9<>7。つまりR7C9から７を削除できるということになります。link関係の矛盾により削除できるという訳ではありません。
うまく説明できていると良いのですが。^^;
> 「7を削除出来る場所をチェックする」ということですよね？
えっと、「R7C9には７は存在し得ない ==> 7を削除できる」で合ってます。R7C9から７を削除できる理由を誤解されているのではないかという意味で書きました。> #139
#140の例でもそうですが、R7C9の７はstrong linkの構成要素ではありません。何故なら最後のブロック内にはR7C9, R8C7, R9C7の３カ所に７が存在しますから、このブロック内で７はstrong linkを構成できません。つまりR7C9の７とR9C7の７はstrong linkの関係にありません。
同様に７行目についても７はR7C1, R7C4, R7C6, R7C9の４カ所に存在しますから、やはりR7C9の７とR7C6の７もstrong linkの関係にありません。
Gと表記された候補数字群とBと表記された候補数字群はAdvanced Coloringによる塗り分けによって互いに排他的な関係にあることが判明した候補数字群です。つまり盤面上でGと表記された候補数字群のいずれかひとつでも真であるならば他のすべてのGも真であり、他のすべてのBは偽です。
Gと表記された候補数字群とBと表記された候補数字群のどちらが真であるかは確定できませんが、少なくともどちらか一方が真であることは確定しています（もし両方が偽であれば２値セル内、あるいは２所セル内の候補数字が共に空となり矛盾）。
したがって、R7C9の７は、R7C6あるいはR9C7のいずれが７であるにせよ、同一の行内または同一のブロック内に２つ以上の７が存在できないのでR7C9<>7。つまりR7C9から７を削除できるということになります。link関係の矛盾により削除できるという訳ではありません。
うまく説明できていると良いのですが。^^;
> #141 daigoさん
かなり時間が掛かりましたが、
この処理なんですが、
#=======================================================================#
0:0> (r#6) [R2C3]のX=7は[R9C3]のG=7と同じグループで、セル内の[R2C3]のB=9
が反対の色で彩色されています。
==> R2C3<>7
#=======================================================================#
図左のように、「R9C3」の「G=7」が「真」だったら、
「R2C3」の候補数字「７」を入れることは出来ないし、
図右のように、「R9C3」の「G=7」が「偽」だったら、
「R7C1」の「B=7」が「真」だから、
「R7C1」の「G=3」は「偽」になって、→
「R3C1」の「B=3」が「真」だから、
「R3C1」の「G=9」は「偽」になり、→
最終的には「R2C3」の「B=9」が「真」となるので、
やはり「R2C3」の候補数字「７」を入ることは出来ない。
という数独のルールなので合っていますか？
※一応、他の方々のために参考までに。
※「真」とは、仮にマスに一つだけ数字を入れると、
※そのマスの候補数字は全て入れない、ということです。m(_ _)m
かなり時間が掛かりましたが、
この処理なんですが、
#=======================================================================#
0:0> (r#6) [R2C3]のX=7は[R9C3]のG=7と同じグループで、セル内の[R2C3]のB=9
が反対の色で彩色されています。
==> R2C3<>7
#=======================================================================#
図左のように、「R9C3」の「G=7」が「真」だったら、
「R2C3」の候補数字「７」を入れることは出来ないし、
図右のように、「R9C3」の「G=7」が「偽」だったら、
「R7C1」の「B=7」が「真」だから、
「R7C1」の「G=3」は「偽」になって、→
「R3C1」の「B=3」が「真」だから、
「R3C1」の「G=9」は「偽」になり、→
最終的には「R2C3」の「B=9」が「真」となるので、
やはり「R2C3」の候補数字「７」を入ることは出来ない。
という数独のルールなので合っていますか？
※一応、他の方々のために参考までに。
※「真」とは、仮にマスに一つだけ数字を入れると、
※そのマスの候補数字は全て入れない、ということです。m(_ _)m
で、今度はAlmost Locked Setという手筋を実装してみました。ご存じの方もいらっしゃると思いますが、これはXY-Wing, XYZ-Wing, Sue De CoqなどのWing系手筋を一般化した手筋で、Wing系手筋すべてを含む手筋です。
私が知る限り http://www.stolaf.edu/people/hansonr/sudoku/explain.htm で紹介されている解説が最も詳しいと思います。
現在は問題の解説盤面で表示する手筋の難易度をどうするかを検討しています。既存の手筋の相対難易度を次のように設定しているのですが、皆さんはAlmost Locked Setは数値として、どの程度の難易度とお考えでしょうか？
naked型2国同盟。組が増えるごとに[+2] tuples-naked=2
ローカライゼーション localization=4
hidden型2国同盟。組が増えるごとに[x2] tuples-hidden=4
試行錯誤(仮置き)法 trial-and-error=5
単独候補(行・列・ブロック内で唯一の候補) only-one=5
セル・ユニーク(グループ内で唯一可能な確定値) cell-unique=6
n-grid(X-wing, swordfishなどの一般系)。グリッド数が増えるごとに[x2] n-grid=7
配置確定法(Pattern Overlay Method) POM=8
Nice Loop。連鎖が増えるごとに[+2] nice-loop=8
Advanced Coloring advanced-coloring=8
自分の手で解くと言うことをほとんどしないので、実際に数独を楽しんでいる方からの感想としての難易度評価を聞かせてもらえると助かります。_o_
私が知る限り http://www.stolaf.edu/people/hansonr/sudoku/explain.htm で紹介されている解説が最も詳しいと思います。
現在は問題の解説盤面で表示する手筋の難易度をどうするかを検討しています。既存の手筋の相対難易度を次のように設定しているのですが、皆さんはAlmost Locked Setは数値として、どの程度の難易度とお考えでしょうか？
naked型2国同盟。組が増えるごとに[+2] tuples-naked=2
ローカライゼーション localization=4
hidden型2国同盟。組が増えるごとに[x2] tuples-hidden=4
試行錯誤(仮置き)法 trial-and-error=5
単独候補(行・列・ブロック内で唯一の候補) only-one=5
セル・ユニーク(グループ内で唯一可能な確定値) cell-unique=6
n-grid(X-wing, swordfishなどの一般系)。グリッド数が増えるごとに[x2] n-grid=7
配置確定法(Pattern Overlay Method) POM=8
Nice Loop。連鎖が増えるごとに[+2] nice-loop=8
Advanced Coloring advanced-coloring=8
自分の手で解くと言うことをほとんどしないので、実際に数独を楽しんでいる方からの感想としての難易度評価を聞かせてもらえると助かります。_o_
> #142 びーにぃさん
ご質問の件。r3c2の7が削除できる理由ですがAdvanced Coloringの説明文5ページ欄外に書いてある
(6) 彩色されていない候補数字と同じグループ内に同じ値の彩色された候補数字(a)が存在し、彩色されていない候補数字と同じセルに(a)と反対の色に彩色された候補数字が存在するならば、該当する候補数字を削除できる。
という定理が成立しているためです。彩色を進めた結果#142の左図のようにr9c3の7はGreenとなった状態です。同じ3列目に存在するr2c3の7はGreenではあり得ないので、可能性があるのはBlueのみです。ところがr2c3の9がすでにBlueに確定しているのでBlueもあり得ません。したがって、r2c3に7が存在することは矛盾です。
以上がr2c3<>7の根拠です。正しく彩色した結果としてr2c3に7が存在し得ないという矛盾が発見できたということです。
ご質問の件。r3c2の7が削除できる理由ですがAdvanced Coloringの説明文5ページ欄外に書いてある
(6) 彩色されていない候補数字と同じグループ内に同じ値の彩色された候補数字(a)が存在し、彩色されていない候補数字と同じセルに(a)と反対の色に彩色された候補数字が存在するならば、該当する候補数字を削除できる。
という定理が成立しているためです。彩色を進めた結果#142の左図のようにr9c3の7はGreenとなった状態です。同じ3列目に存在するr2c3の7はGreenではあり得ないので、可能性があるのはBlueのみです。ところがr2c3の9がすでにBlueに確定しているのでBlueもあり得ません。したがって、r2c3に7が存在することは矛盾です。
以上がr2c3<>7の根拠です。正しく彩色した結果としてr2c3に7が存在し得ないという矛盾が発見できたということです。
Almost Locked Set（XY-Wing,XYZ-WingなどのWing系手筋の一般系）に加えて、Grid-Based Almost Locked Set（Sashimi Fish,Finned Fishの一般系）を追加実装した版の数独解法プログラム（＝NumberPlace.lisp）がほぼ完成しました。現在実装している手筋は
・基本手筋(置く手筋)
・単独候補(行・列・ブロック内で唯一の候補なら確定値）
・セル・ユニーク(グループ内で唯一可能な確定値)
・ローカライゼーション
・tuples(n国同盟=無制限）
・n-grid(x-wing, swordfish, jellyfish,...の一般形)
・配置確定法(Pattern Overlay Method)
・Nice Loop(連鎖セル数=無制限)
・Advanced Coloring(Simple Colors, Multi-Colorsを統合した手筋)
・Almost Locked Set(XY-Wing, XYZ-Wing, Sue De CoqなどWing系手筋の一般形)
・Grid-Based Almost Locked Set(=Sashimi Fish, Finned Fishの一般形)
・試行錯誤(仮置き)法
となっています。ベクターで公開させていただくつもりですが、その前に数名の方にベータテストをお願いできればと思っています。ご希望いただける場合は私まで送信先メール・アドレスをmixiメールで送っていただければ、折り返しご連絡いただいたメール・アドレスにプログラムを送らせていただきます。先着3名程度を考えています。２〜３週間を目処にフィードバックをいただいた上で公開させていただきたいと思っています。
以上、興味を持っていただける方がいれば宜しくお願いいたします。_o_
・基本手筋(置く手筋)
・単独候補(行・列・ブロック内で唯一の候補なら確定値）
・セル・ユニーク(グループ内で唯一可能な確定値)
・ローカライゼーション
・tuples(n国同盟=無制限）
・n-grid(x-wing, swordfish, jellyfish,...の一般形)
・配置確定法(Pattern Overlay Method)
・Nice Loop(連鎖セル数=無制限)
・Advanced Coloring(Simple Colors, Multi-Colorsを統合した手筋)
・Almost Locked Set(XY-Wing, XYZ-Wing, Sue De CoqなどWing系手筋の一般形)
・Grid-Based Almost Locked Set(=Sashimi Fish, Finned Fishの一般形)
・試行錯誤(仮置き)法
となっています。ベクターで公開させていただくつもりですが、その前に数名の方にベータテストをお願いできればと思っています。ご希望いただける場合は私まで送信先メール・アドレスをmixiメールで送っていただければ、折り返しご連絡いただいたメール・アドレスにプログラムを送らせていただきます。先着3名程度を考えています。２〜３週間を目処にフィードバックをいただいた上で公開させていただきたいと思っています。
以上、興味を持っていただける方がいれば宜しくお願いいたします。_o_
top95（http://magictour.free.fr/top95）という問題を使ってAlmost Locked Set（ALS）とGrid Based Almost Locked Set（GB-ALS）の効果を測定してみました。
ALSとGB-ALSなしで全95問を解いた場合に必要となった試行錯誤ルーチンの合計実行回数は122回でしたが、使用手筋にALSとGB-ALSを加えた場合の試行錯誤ルーチンの合計実行回数は54回でした。
Wing系とSashimi系手筋が加わわることによる効果は大きいようです。引き続き、のんびりと試行錯誤ルーチン使用ゼロを目指して手筋を追加していこうと思っていますが、あまり超絶過ぎる手筋だと人間による実行がほとんど不可能になってしまうのが悩みです。出来るだけ人間にも容易に実行できる手筋を選んで実装していこうと思ってます。
βテスターは引き続き募集しています。翻訳ですが日本語でのALSとGB-ALSの解説も用意しましたので試してみても良いという方、宜しくお願いします。_o_
ALSとGB-ALSなしで全95問を解いた場合に必要となった試行錯誤ルーチンの合計実行回数は122回でしたが、使用手筋にALSとGB-ALSを加えた場合の試行錯誤ルーチンの合計実行回数は54回でした。
Wing系とSashimi系手筋が加わわることによる効果は大きいようです。引き続き、のんびりと試行錯誤ルーチン使用ゼロを目指して手筋を追加していこうと思っていますが、あまり超絶過ぎる手筋だと人間による実行がほとんど不可能になってしまうのが悩みです。出来るだけ人間にも容易に実行できる手筋を選んで実装していこうと思ってます。
βテスターは引き続き募集しています。翻訳ですが日本語でのALSとGB-ALSの解説も用意しましたので試してみても良いという方、宜しくお願いします。_o_
○＃１４４：daigoさん＞
数独による難易度の点数は分かりませんが、
私的に高低はこんな感じです（参考まで）。
―――――――――――――――――――
高
―――――――――――――――――――
配置確定法（Pattern Overlay Method）
↑
試行錯誤（仮置き）法
↑
Advanced Coloring
↑
Nice Loop
↑
n-grid（X-wing, swordfishなどの一般系）
↑
ローカライゼーション
↑
hidden型２国同盟
↑
naked型２国同盟
↑
セル・ユニーク（グループ内で唯一可能な確定値）
↑
単独候補（行・列・ブロック内で唯一の候補）
―――――――――――――――――――
低
―――――――――――――――――――
数独による難易度の点数は分かりませんが、
私的に高低はこんな感じです（参考まで）。
―――――――――――――――――――
高
―――――――――――――――――――
配置確定法（Pattern Overlay Method）
↑
試行錯誤（仮置き）法
↑
Advanced Coloring
↑
Nice Loop
↑
n-grid（X-wing, swordfishなどの一般系）
↑
ローカライゼーション
↑
hidden型２国同盟
↑
naked型２国同盟
↑
セル・ユニーク（グループ内で唯一可能な確定値）
↑
単独候補（行・列・ブロック内で唯一の候補）
―――――――――――――――――――
低
―――――――――――――――――――
びーにぃさん、難易度についての参考意見ありがとうございます。
私の感覚と似ていますね。少し安心しました。現在はPOMとAdvanced ColoringそれにNice Loopの難易度が同じ設定になっているので参考にさせていただきます。
ちなみに私の脳内では、この３つは Nice Loop > Advanced Coloring > POM という順序でした。Nice LoopとAdvanced Coloringのどちらが難しいかは感覚の相違かなと思いますが、POMは難しいと言うよりは作業が大変というイメージです。
POMを他の数独解法プログラムがどのように実現しているのかは知りませんが、NumberPlace.lispでは、候補が存在する可能性がある位置から、数独のルール下であり得るすべての存在パターンを特定して候補位置を絞り込むという作業を行っています。手作業で同じことを行おうとすると数十枚から数百枚の配置パターンを書きまくって、すべてに共通する位置、あるいはすべてに現れない位置を探すことになります。要するに手作業で行うことはお勧めできない手筋です（もっと効率的な方法があるかも知れませんが）。^^;
私の感覚と似ていますね。少し安心しました。現在はPOMとAdvanced ColoringそれにNice Loopの難易度が同じ設定になっているので参考にさせていただきます。
ちなみに私の脳内では、この３つは Nice Loop > Advanced Coloring > POM という順序でした。Nice LoopとAdvanced Coloringのどちらが難しいかは感覚の相違かなと思いますが、POMは難しいと言うよりは作業が大変というイメージです。
POMを他の数独解法プログラムがどのように実現しているのかは知りませんが、NumberPlace.lispでは、候補が存在する可能性がある位置から、数独のルール下であり得るすべての存在パターンを特定して候補位置を絞り込むという作業を行っています。手作業で同じことを行おうとすると数十枚から数百枚の配置パターンを書きまくって、すべてに共通する位置、あるいはすべてに現れない位置を探すことになります。要するに手作業で行うことはお勧めできない手筋です（もっと効率的な方法があるかも知れませんが）。^^;
先ほどベクター（http://www.vector.co.jp/）にAlmost Locked SetとGrid-Base Almost Locked Setを追加実装した版のNumberPlace.lispの登録依頼を行いました。「NumberPlace.lisp.503.zip」というファイル名で登録されると思います。
手筋に詳しくない方のために「Almost Locked Set入門.pdf」と「GB-ALS入門.pdf」という解説も添付しています。参考になれば幸いです。
今日は週末なので、ベクターには来週の登録になると思います。宜しければダウンロードして試してみて下さい。^^
手筋に詳しくない方のために「Almost Locked Set入門.pdf」と「GB-ALS入門.pdf」という解説も添付しています。参考になれば幸いです。
今日は週末なので、ベクターには来週の登録になると思います。宜しければダウンロードして試してみて下さい。^^
数独解法ソフトのNumberPlace.lispの新版を公開したという連絡をもらいました。
---
NumberPlace.lisp 5.0.3
NumberPlace.lisp.503.zip (NumberPlace.lisp.503.zip)
11/07/08 1523511
概要: ナンプレ(数独)の解法過程を表示するCommon Lispプログラム
説明ページ: http://www.vector.co.jp/soft/data/game/se472172.html
---
すでにダウンロードできる状態になっているようです。宜しければ使ってみていただけると幸いです。^^
---
NumberPlace.lisp 5.0.3
NumberPlace.lisp.503.zip (NumberPlace.lisp.503.zip)
11/07/08 1523511
概要: ナンプレ(数独)の解法過程を表示するCommon Lispプログラム
説明ページ: http://www.vector.co.jp/soft/data/game/se472172.html
---
すでにダウンロードできる状態になっているようです。宜しければ使ってみていただけると幸いです。^^
NumberPlace.lispのMac OS X Lion上での動作を確認しました。
動作を確認した処理系はCLISPとClosure CLです。OS XにCLISPを導入するには事前にXcodeなどをインストールしなければならず煩雑なのでClosure CLを簡単に設定できる「LispBox」をお奨めします。
http://common-lisp.net/project/lispbox/
LispBox はEmacs23とSLIME 、そしてClosure CLをセットにした環境で、ダウンロードさえすればインストールなしでEmacs上でのCommon Lisp開発環境が出来上がるというパッケージです。
ただし、Emacs内でのCommon Lisp実行環境だとxterm 256カラーのカラー表示環境が使えないのでNumberPlace.lispの実行にはClosure CL単独での使用をお奨めします。
「dx86cl64」がClosure CLの本体です。このファイル名のアイコンをダブルクリックするとClosure CLがターミナル環境で起動します。あとはCLISP上での実行と同じで
> (load "/Users/daigo/Lisp/NumberPlace.lisp")
などとNumberPlace.lispが存在するパス名を付けて実行するだけです。
動作を確認した処理系はCLISPとClosure CLです。OS XにCLISPを導入するには事前にXcodeなどをインストールしなければならず煩雑なのでClosure CLを簡単に設定できる「LispBox」をお奨めします。
http://common-lisp.net/project/lispbox/
LispBox はEmacs23とSLIME 、そしてClosure CLをセットにした環境で、ダウンロードさえすればインストールなしでEmacs上でのCommon Lisp開発環境が出来上がるというパッケージです。
ただし、Emacs内でのCommon Lisp実行環境だとxterm 256カラーのカラー表示環境が使えないのでNumberPlace.lispの実行にはClosure CL単独での使用をお奨めします。
「dx86cl64」がClosure CLの本体です。このファイル名のアイコンをダブルクリックするとClosure CLがターミナル環境で起動します。あとはCLISP上での実行と同じで
> (load "/Users/daigo/Lisp/NumberPlace.lisp")
などとNumberPlace.lispが存在するパス名を付けて実行するだけです。
マイクロソフトACCESSで数独を解くソフトを作りました。
手法は、手書きで条件に合わないものを候補数字から外し処理を流し、絞り込んでいくものと一緒です。
ちなみに、全組み合わせ（362,880件）から抽出していく方法は
わたくしのPCスペックでは無理がありました( ;∀;)
候補が複数あり手詰まりとなってしまいます。この場合には処理が止まってしまいます。
その場合は確定分までを記憶させて、複数候補のうちひとつを仮の確定分として処理を流します。
これが違っていた場合には、別の候補を確定分として同じ処理を繰り返します。
※この場合は手動になってしまいます。
どなたかわたくしに問題を出してみていただけませんか？
手法は、手書きで条件に合わないものを候補数字から外し処理を流し、絞り込んでいくものと一緒です。
ちなみに、全組み合わせ（362,880件）から抽出していく方法は
わたくしのPCスペックでは無理がありました( ;∀;)
候補が複数あり手詰まりとなってしまいます。この場合には処理が止まってしまいます。
その場合は確定分までを記憶させて、複数候補のうちひとつを仮の確定分として処理を流します。
これが違っていた場合には、別の候補を確定分として同じ処理を繰り返します。
※この場合は手動になってしまいます。
どなたかわたくしに問題を出してみていただけませんか？
- mixiユーザー
- ログインしてコメントしよう！
|
|
|
|
Sudoku 数独 更新情報
-
最新のイベント
-
まだ何もありません
-
-
最新のアンケート
-
まだ何もありません
-
Sudoku 数独のメンバーはこんなコミュニティにも参加しています
人気コミュニティランキング
- 1位
- 暮らしを楽しむ
- 75492人
- 2位
- 写真を撮るのが好き
- 208297人
- 3位
- 音楽が無いと生きていけない
- 196028人