数独日誌110213
世界文化社「難問ナンプレに挑戦11」☆６つが10題、☆７つが35題終了しました。今回もう一度この本で使われている手筋のことを、話題にしたいと思います。
ミシチャンさんは稲葉さんの前著「難問ナンプレに挑戦２」を解いた感想を書いたブログで、ナンプレの解法をグループ分けすると、
1. 定員確定・n国同盟・Xｰwingといったnヶ所n個系
2. ChainやXY-wingといったALS/ALC系
3. Unique RectangleやBUGといった唯一解系
4. Template MethodやTry and Errorといった虱潰し&根性系
に分けられそう、と書いています。
http://mishichan.cocolog-nifty.com/blog/2007/01/2_185f.html
そして、稲葉さんは上記の1.だけで解けるように「難問ナンプレに挑戦２」の問題を作った、としています。ここでよくわからないのですが、X-wing（四角の対角線）はnヶ所n個系に入るのでしょうか。X-wingはそれ以外の上級手筋（上記の2.に分類されるもの）と何か本質的に違う部分があるのか、よくわかりません。
ニコリ社や稲葉さんがn国同盟とX-wing（四角の対角線）にこだわっていることに関係があるのかも、と思いました。このことについて何かご意見のある方はいらっしゃいますか？
以下私の使った手筋です。
４国同盟（隠れ２国） 66,67
４国同盟 70
四角の対角線 67,70,72,73
四角の対角線×２ 66
四角の対角線×３ 74
四角の角線（３行） 69,73,75
| 固定リンク
「趣味」カテゴリの記事
- 数独日誌241201(2024.12.01)
- 数独日誌241124(2024.11.24)
- 数独日誌241117(2024.11.17)
- 数独日誌241110(2024.11.10)
- 数独日誌241103(2024.11.03)
コメント
ナンプレ解法の体系化は私も興味があり、トライしてますが、考え方により分類が分かれぴったりとはいきません。
その中でX-Wingは、SudopediaやHoDoKuサイトのSingle Digit Patterns の仲間と考えると良いのではと思っています。
Single Digit Patterns は、１つの数字に着目した２択の連鎖と考える事ができ、元々Skyscraper、2-String Kite、Empty rectangle 等の手筋が含まれています。
そして、このSingle Digit Patterns の上位手筋の説明としては、ミシチャンさんのサイトのX-cycle が適切と思います。
X-cycle (連続ループ)でX-Wing 、 X-cycle （不連続ループ）でSkyscraper、2-String Kite、Empty rectangle が説明できます。
但し、Empty rectangle は単純な２択の連鎖だけではないので微妙なところですが、グループ化すれば同等です。
このため、X-cycle の考え方が理解できていれば、下位の手筋は忘れても良いという事になります。
X-cycle は、１つの数字に着目するため理解し易いのと、２択の３連鎖、４連鎖にも拡張できますので、活用範囲の広い手筋と思います。
「難問ナンプレに挑戦２」は私もやりましたが、n国同盟は確かにすごかったです。
投稿: nangoqoo | 2011年2月14日 (月) 18時21分
nangoqooさんへ
早速ていねいなコメントありがとうございます。
私も四角の対角線（X-wing）を探すとき、通常はSashimi Fish（Skyscraper）とFinned Fishも一緒に探すので、これらの手筋が同じ系統だろうというのは納得です。
Empty Rectangleについては私は使ったことはないのですが、このブログでは前にTachyonさんとパズル好きさんが今井洋輔さんの世界文化社「難問ナンプレ 解き方のコツ」の本についてのコメントで触れています。（数独日誌100527参照）
とにかく稲葉さんが四角の対角線だけ特別扱いする根拠がどうもよくわかりません。稲葉さんが巻頭に書いてある「候補を消す」手筋の中の３．マトリックス系にSashimi Fish、Finned Fishが入っているのか、というのは興味のあるところです。
投稿: ikachan | 2011年2月14日 (月) 23時17分
稲葉さんの問題でSashimi Fish、Finned Fish、Turbot Fishを使うのは理詰めではないと思います。
ミシチャンさんも井桁理論と予約の共通した考え方について説明しています。
http://www.geocities.jp/master_mishichan/same.html
投稿: 北風 | 2011年2月15日 (火) 22時45分
北風さんへ
コメントありがとうございます。
ミシチャンさんのHPは、見つけた時（2009年１月）に全頁をプリントアウトしたと思っていたのですが、ご指摘のページは印刷し損なっていました。予約（n国同盟）と井桁理論（X-wing）が同じアルゴリズムで処理できるというのはなんとも不思議な、面白い考え方ですね。ミシチャンさんがX-wingをnヶ所n個系に分類している理由がわかりました。
ただ実際に解くときに、この考え方を使って解いている人はまずいないと思うので、人の感覚としてはこの２つが同じ解法に分類できる、というのはなかなか実感しずらいです。
投稿: ikachan | 2011年2月16日 (水) 21時10分
今晩は！このブログに、101011でカミングアウトしたnko_matsu です。数独を解くのは初心者ですが、解法アルゴリズムに興味をもっています。PCで解く際の解法の体系というか構造の特徴は、number-placeという名前にあります。つまり、それぞれ1から９までの値を持つnumber,block,row,columnの4つの変数（座標）を使った４次元の構造体系です。これを視覚的にわかりやすいように２次元matrix であらわすと解法を探す上で基本的な次の４つの np-matrix (ナンプレマトリクスと勝手に名づけました）になります。
①（block,number)、②（row,number)、③ (column,number)、④(row,column)
最後のmatrix は通常の問題紙面に使われている行列です。なお、matrix の値は、④はnumber ですが、あとはplace です。候補の数字または場所を考えるとき、この四つのmatrixで一つの候補(single digit)
見つけるのが、稲葉氏の「数字を入れる」手筋に相当します。①②③で現れるsingle place の候補数字は④では他の候補とまぎれてあらわされるので、hidden single digit と呼ばれています。でもそれはnaked single place でもあるわけです。
次の手順の稲葉氏の「候補を消す」手筋もこの四つのmatrix を使ってプログラミングすれば、アルゴリズムは簡単です。final answer の段階でこの四つのmatrix は すべてdiagonal matrix になりdeterminantは値を持ちます。解法の手順は四つのmatrixを使って部分行列になりえるものを探し、対角化を進めることです。稲葉氏の「コンビネーション系」と「マトリックス系」は同じアルゴリズムで解法が書けます。
n国同盟は、room=2,3,4,5 とするだけで一気に扱えるし、連続して部分行列化もできます。①②③の転置行列は陰の定員確保と（表の）定員確保の関係にあります。④matrixのroom=2,3,4,5は俗にいうX-wing,swordfish,jellyfish,squirmbagになります。転置行列は、行と列の関係になります。
以上コンピュータアルゴリズムの観点から、また稲葉氏の手順の記載の補足のつもりで投稿しました。
投稿: nko_matsu | 2011年2月16日 (水) 22時44分
nko_matsuさんへ
いろいろな方からコメントをいただくと、それだけで嬉しくなってしまいます。ありがとうございます。
大学で勉強した線形代数の用語がたくさん登場して、老化した頭に刺激になりました。数独ナンプレを解くプログラムはどういう考え方に基づいているのかな、と思っていましたが、ここまで数学的なアルゴリズムなんですね。
もしかすると数学の雑誌（日本評論社の「数学セミナー」とか）にナンプレ解法のアルゴリズムということで、記事が掲載されているかもしれません。大昔「数学セミナー」でルービックキューブの解き方の記事を読んだことがあります。
「難問ナンプレに挑戦11」については、n国同盟と四角の対角線だけでどこまで解き進められるか、ということに興味が絞られてきたようです。
投稿: ikachan | 2011年2月17日 (木) 19時39分