背理法必須のナンバープレース問題について

質問

背理法でのみ解くことができないナンバープレース（数独）の
問題が「難問」と言われる問題として提示されている本があります。
このたぐいの問題は問題としては意地悪でありパズルとしての質が
よくないと思いますが皆さんはどう思われますか？
私は大嫌いで、背理法を使うのがわかった段階で解くのをやめます。
出版社？（ダイソー、ニコリetc）によっては背理法でしか解けない
問題は出題しない方針ではないかと思われる信念をもった出題者がいるように感じます。
そもそも、背理法を使えばこれだけで最後まで解けてしまうのでパズルでも何でもないものになります。手間は膨大にかかりますが頭をほとんど使わず解けるのでコンピュータ向きですね。
どんな問題か例として解答と共に添付します。

回答No.7

asciiz · ベストアンサー

＞予約消去法(2,5)<=1がどのような解法テクニックなのか理解できません。
＞そのソフトに説明はありませんか？

いやあこれが、無いんですよね……(汗)(図左)
でも、そこまで進めた場面で、こういうことか、と解釈はできています。
1ステップごとに結構考えてしまいます^^;

＞恐らく2列５行のセルの候補数字の１が消せるということだと思いますが

「2列5行に1が入る」方です。それでは図右の手書き画面で。

上3ブロックの「1」が入る場所を確認すると、左ブロックは確定、中ブロックは2行4・6列のいずれか、右ブロックは3行7・8列のいずれか、になっています。(赤丸)
下3ブロックの「1」が入る場所を確認すると、左ブロックは9行の1・2列のいずれか、中ブロックは確定、右ブロックは7行7・8列のいずれか、になっています。(赤丸)
と、言うことは、中央右ブロックで1が入る場所は、第9列のいずれか(青丸)と言うことになり、その他の「1候補」を消すことが出来ます。(赤バツ)

そうした上で5行目全体を見ると、1が入るのは5行2列(水色マス)しかありません。1で確定です。

納得できたら、また進めてみてください。

＞手書き回答での説明での３行７列が８に確定する根拠の説明が理解できません。

こちらの件も、前回答の図は(3,3)が4に確定する直前場面なので、確かに8が入る理由はいきなりわからないと思います。
「8候補」が消えたり、確定数字で上書きされた結果、入る流れになっています。
(すでに今回の場面でも、右上ブロックでの「8候補」は2か所にまで絞られているわけですが。)

お礼

ソフトの説明で最後まで自分の頭で検証できました。
この問題は背理法を使わずに解ける問題でした。
自動解法ソフトや解法補助ソフトによりそのプログラムを組む上で始めに設計するアルゴリズムの差によりその時点で使う解法テクニックの種類や使う優先順位に差が出た結果、解法手順が変わったり、背理法が登場してしまうのでしょう。プログラム上背理法に逃げるのは極めて簡単ですから。アルゴリズムでできるだけ背理法を避けるような設計をしてもらえると使う立場からはありがたいです。
これらのソフトを１００％信用せずに他にも解法手順があるのを模索すべきですね。同様な問題がいくつか保存してあるのでもう一度解き直してみます。

回答No.8

asciiz

んん、「予約消去法」の解釈は少し違ったかもしれません

よく見てみれば、9列の「1」は、上下の「1候補」消去により、すでに4行目と6行目のどちらか、にまで絞り込めていました(前図の青丸)。
それで、中央右ブロックの他の「1候補」を消せます(前図の赤バツ)。
5行3列は、上に1があるので1は入らない、5行5列も、下に1があるので入らない。

それで、1が入る可能性は5行2列だけになるので、1が確定。

…と言うのが、解析アプリの色つき表示だったようです。

まあ、どちらの考えでも5行2列を確定できます。

回答No.6

asciiz

＞この問題の３行目３列のセルを８ではなく４だと特定する根拠（解法テクニック）は何と説明されているのでしょうか

ではアプリによる解析を転記してみます。
初めて出てくる方法にはコメント(※)入れました。
「<= (数字)」となっているのは、「その数字で確定」なのですが、
「<= ^(数字)」となっているのは、「その数字が入らないことが確定」という意味です。
アプリではステップごとに注目している行・列・ブロックが表示され、排除数字もメモされていくので、文字だけだと分かりづらいのですが…。
あとマス位置の表示で、(1,2)は「第1列2行目マス」であるので、それも注意です。

場所消去法: (8,9) <=6 ※(8列9行に6が入る)
場所消去法: (7,4) <=6
場所消去法: (6,8) <=7
予約排他: (7,2),(9,2) <=^1 ※(7列2行、9列2行には、1が入らない)
予約排他: (9,9) <=^8
予約排他: (8,1),(9,1),(9,2),(8,3) <=^8
数字専有: (3,3),(3,6) <= (4|8) ※3列3行と、3列6行には、お互いに4か8のどちらかしか入らず、他の数字は入らない
場所消去法: (2,3) <=5
予約排他: (2,7),(2,9) <=^3
縦横専有: (8,4),(8,6),(3,8),(8,8) <= ^5 ※5行目と7行目のX-ウイング(5)、その上下に5は入らない
縦横専有: (5,1),(8,1),(5,6),(8,6),(5,7) <= ^9 ※3行目と5行目のX-ウイング(9)、その上下に9は入らない
場所消去法: (4,8) <=9 ※ひとつ前のX-ウイングで中央下ブロックの9候補がここだけになった
場所消去法: (2,7) <=9
予約排他: (9,9) <=^1
予約消去法: (2,5) <= 1
場所消去法: (1,9) <= 1
場所消去法: (2,9) <= 4
数字消去法: (7,5) <= 7
場所消去法: (8,1) <= 7
予約排他: (9,8),(9,9) <= ^2
予約排他: (9,9) <= ^5
数字消去法: (9,9) <= 3
場所消去法: (7,2) <= 3
場所消去法: (5,7) <= 3
場所消去法: (4,1) <= 3
場所消去法: (3,8) <= 3
場所消去法: (7,3) <= 8 ※ここで先ほどの(3,3)マスが4か8のどちらかだったのに、同行に8が入った。
数字専有確定: (3,3) <=4 ※このマスに入る数字候補が4しかなくなったため、確定。【3行3列マス】
数字専有確定: (3,6) <=8
補完: (7,7) <=1 ※1列のうち、もう1か所しか空いてないのでこの数字しか入らない。
場所消去法: (8,3) <= 1
補完: (5,3) <=9 ※1行のうち、もう1か所しか空いてないのでこの数字しか入らない。【3行5列マス】

と、なっています。

いやー、やっぱ文字だとわかんないですよね^^;
転記した私自身も、ステップ図が無ければさっぱりわかりません。
なので、手書き回答側でも解説してみます。

まずは最初に、単純に縦横の数字から、各マスに入る可能性がある候補を全て書き出しています。(図左、拡大してください)
(3,3)マスで重要なのは、「数字専有: (3,3),(3,6) <= (4|8)」ってやつですが、手書きの回答(図左)で言えば、3列目において「4・8ペアの隠れた2国同盟」を見つけたことに相当し、他の数字候補を斜線で消しています。
アプリ手順にある「予約排他」っていうのも、この「候補数字を斜線で消す」という作業に相当します。
そうしてもう少し進めると、3行7列に数字「8」が確定します。(図右)
そこに「8」が入るのをもう少し前から解説すると、回答No.2の右図で7列目全体と数字の8に注目してもらうと、問題にはじめからある「8」により、「8」が入る可能性があるのは7列目の2行目・3行目のどちらかだけであるので、右上ブロックの8列目・9列目の「8」候補を消去できていることによります。

という訳で、(3,3)マスの4・8候補のうち、8が消えたので4確定です。
ついでに、3行5列マスは候補として4・8・9 が入っていましたが、4・8が消えたので9確定になります。

(ちなみにこの手書き再現アプリ自体にも、回答検索プログラムが入っているのですが、そちらではすぐ「仮定(背理法)」を使ってしまって、きちんと解いてくれませんでした。)

背理法の無いナンプレ問題ではこのように、「候補数字を書き入れる」そして「入る可能性の無くなった数字を(斜線で)消していく」ことにより、『消しゴムを使わずに解けます』。
雑誌や本に掲載されるナンプレは、そうであるべきで、ニコリの発表するナンプレは背理法無しに解けるようになっている、というのも、確実に意識してそうなっているのだろうと思います。

補足

まず、いくつかの解法手順の検証のためこの問題をいくつかプリントアウトしました。（元々、難問についてはExcelで保存してありすぐ印刷できる体制です。）それにエンピツで各セルに入り得る候補数字を書き込みます。そしてそのセルに一義的に決まる数値を残し他の数を消します。その後、＊国同盟、Xウイング等の常とう手段の解法テクニックを使い各セルの候補数字を消して行き、その時点での候補数字を別に何枚か印刷した問題に書き写します。同じ条件まで解いた数枚の問題を使い各解法手順で解き進めてみます。
それで、そちらのアプリによる解析を上から順番に当てはめて行きました。途中までは解法テクニックは理解でき納得しながら進められましたが１５step目の初めて出てきた
予約消去法(2,5)<=1がどのような解法テクニックなのか理解できません。恐らく2列５行のセルの候補数字の１が消せるということだと思いますがその根拠は何なのでしょうか？そのソフトに説明はありませんか？
あと、手書き回答での説明での３行７列が８に確定する根拠の説明が理解できません。回答（解答）の情報は使ってはダメです。

回答No.5

asciiz

＞行き詰まった結果、しょうがない、背理法を使ってみるかということになるわけです。
＞行きつ戻りつで結果、最後まで解けますがこの半分ギャンブルみたいにやってみないと
＞分からないところがパズルではないように思えて嫌いです。

いやもう、そこは完全に同意します。「行きつ『戻りつ』」が出来るのはパソコンソフトやアプリで操作するからであって、紙のパズルを手で解くことを考えたらやってられません。
私もそんなナンプレは投げてしまいますね。

----

で、ただいま食い違っているのは、ご質問にある問題がそういう物かどうか、と言う点ですね。

私の使ってるのはこちらなんですが、

＞数独解析 for Android
＞https://play.google.com/store/apps/details?id=jp.gr.java_conf.jyokun.sudokudroid

こちらでは、ステップごとに「このマスの数字○はこの理由で確定」というのはもちろんあるんですが、「このマスの数字×がこの理由により排除(絶対に入らない)」というデータ(予約排他)も積み重ねていき、結果「このマスは数字△で確定」みたいに解析が進んでいきます。

もちろん論理で解けない問題では、「総当たり(仮定)」→経過→「破綻」を確認後に「このマスの数字▽は排除」ってなる問題もありましたが。
この問題は、そうではないようです。

ステップごとの表示が難しくて、どういう意味なのか毎ステップ考えてしまうんですけど^^;
自分でハイライトされた列の候補数字を検討すると、きちんと理解できたりします。

補足

残念ながらAndroidは使っていないのでそのソフトをインストールできません。ちなみにそのソフトでこの問題の３行目３列のセルを８ではなく４だと特定する根拠（解法テクニック）は何と説明されているのでしょうか？それは仮定した結果の先の矛盾からの決定（背理法）ではありませんか？同様に３行目５列のセルに８が入らないとする根拠はどのように説明されていますか？

回答No.4

asciiz

＞必要ならお知らせします。

あ、すいません、私の使ってるやつはStep数表示がないので何手目かはちょっと(^^;
(途中経過画像を作ったのとはまた別のアプリ)

＞そのセルは３行３列と３行５列の数字を決めるときに発生します。

3行3列、は左上からのカウントでいいですか?
そこは早いうちに(4,8)のどちらかが入ることがわかっていて、解き進めていると右の方で8が入って、数字4に決定してますね。
で、3行5列は、(4,8,9)のどれかですが、第3行で他に4と8が入ったので最後の9で決定です。(解法アプリはちょっと他のとこ埋めてますが)

そこまで、仮置きして戻るような解法にはなっていませんでした。
解き方が違うようなので、回答Step数も食い違ってる可能性がありますね。

補足

下記サイトです。
http://algorithm.main.jp/Puzzle/Sudoku/3-Input.php
使ってみて下さい。
行、列の番号は左上からで行は横方向で列は縦方向です。
このサイトでも背理法以外では進めない場合のみ背理法を使っています。背理法以外での一般的解法を使って解き進むと、この解説とstepに多少の前後に違いは出ますがほぼ同じ手順を踏むことになると思います。当然、背理法の適用時に不正解の数字を選択した場合は矛盾が生じるまでの無駄なstepが増えます。結構深い行き止まりの迷路に入り込む場合があります。あなたの解法手順とこのプログラムによる解法手順を比較してみて下さい。
いずれにせよ、２か所の”背理法でのみ解き進める”セルの
存在は変わらないと思います。
ーーーーーーーーーーーーーーーーーーーーーーーーーー
このたぐいの問題では、どこのセルが背理法を使わなければならないかがわかりません。まだ通常の解法でも解き進める手段があるのではないかと考えてしまいます。それで
行き詰まった結果、しょうがない、背理法を使ってみるかということになるわけです。行きつ戻りつで結果、最後まで解けますがこの半分ギャンブルみたいにやってみないと
分からないところがパズルではないように思えて嫌いです。

回答No.3

asciiz

回答No.2の画像で、右から2列目・6段目の「5」候補も消せますね^^;

訂正ついでに、「9」のX-ウイング消去後の途中経過はこんな風になります。

お礼

すみません。補足に間違いがあり、「お礼」の枠で訂正します。背理法を使わざるstepは７～２０stepではなく１７～２０stepです。

話題にお付き合い頂きありがとうございます。

補足

あなたも私と同じくナンバープレースにはまっていますね。お仲間がいてうれしいナア！
背理法はあなたの言われている（１）（２）（３）そのものです。で、この問題で背理法を使って解くことに対して文句を言っているのではなくこの問題が背理法でのみ解ける問題であることが気に入らないのです。解き進められていますがこの問題は全７０stepで解けますが７～２０step
あたりで背理法でのみ解き進めることができるstepが２つ出てきます。そのセルは３行３列と３行５列の数字を決めるときに発生します。
ご存知かも知れませんが自動解法プログラムというのが結構ネットでいくつかつくられていてstep毎の解説付きもあります。本来、頭脳で人間が１つづ解いていくのがパズル
ですが、この問題、本当に解けるの？行きづまってしまったけどどのように進めればいいの？問題をつくったけど有効な問題として成り立つの？などの目的では便利です。
そんなの見たくないと言う方もいるかも。検索すればすぐに見つかります。必要ならお知らせします。

回答No.2

asciiz

質問者さんの言う背理法っていうのは

(1)未確定数字のどれかを置く。
(2)それで解き進めて完成すれば正解。
(3)矛盾が出たら全部戻して、最初に置いた数字が間違いということで消去。

みたいな方法のことでしょうか。
それは手書きではちょっと解けないし、確かにやりたくありません。

でも、質問画像の問題は、それを使わずとも解けます。

画像左は、6が2か所と、7が一つ、そして左から3列目の[4,8]ペア確定により、1・2段目の5と合わせて5が一つ確定したところです。

ここで、5段目と7段目に置いて、「5」の入る可能性がある場所に注目します。
すると、それぞれの段に置いて、「5」入る場所が、同じ列の2か所にしか存在しません。
ということは、5段目の左側に「5」が入れば、7段目で「5」が入るのは右側に確定します。
逆に、5段目の右側に「5」が入れば、7段目で「5」が入るのは左側に確定します。
ということは、5・7段目以外の上下にある「5」候補を消せるんです！(画像右)

これは「X-ウイング」という定石で、ごく稀に出てきます。

…その稀にしか出ないものが、もう一つあります。

3段目と5段目の「9」に注目すると、やはり2か所ずつにしか入らないので、それ以外の段の上下の「9」候補を消せます。

これ以後は、まあ普通の解法で解けそうな感じでした。

私がこの解法が見えるようになったのは、次のナンプレアプリのおかげですね。

＞ナンプレ館
App Store> https://apps.apple.com/jp/app/id1276087921
Google Play> https://play.google.com/store/apps/details?id=jp.co.puzzle.NPK

こちらのアプリは、問題はすべて人間による手作成、メニューの解法解説にある方法だけで解ける問題のみ収録、とあるうえ、どうしてもわからない場合にヒントを使用すると、「この解法によってここが確定」あるいは「この解法によってこの候補は消去」という手順解説をしてくれるので、「あっ、そうだったか!」と、納得して解いていけます。

あとヒントコインが余ってれば、最初に候補数字を全部埋める機能を使ったり、確定数字を入れると矛盾する候補は自動的に消去してくれたりと、かなり快適に解き進めることができます。

回答No.1

neKo_quatre

例えば、

INTERNET PUZZLER - パズルの解き方 > ナンバープレース
http://www.puzzler.ne.jp/solve/nanpure.html

| ルール
| (1) タテ9列、ヨコ9列のどの列にも1～9の数字が1つずつ入る。
| (2) 太線で囲まれた3×3の9マスのどのブロック内にも1～9の数字が1つずつ入る。

で、

| （２）
| 例えば3に注目。左上のブロックで3が入るマスを考えてみると、上のヨコ2列には、3がすでにあるから入らないことがわかる

の手順は、

上のヨコ２列(２行？)に3が入ると仮定する。
そうすると、ルール(1)に矛盾する。
従って、上のヨコ２列(２行？)に３は入らない。

って立派な背理法なのでは？

--
「No!背理法」って言ってるのを見ると、上のロジックも否定するんだったらどうするんだ？って思います。

多分、
△△のマスに△の数字が入ると仮定する。
そうすると、コッチのマスに入る数字は△。
従って、アッチのマスに入る数字は△。
そうなると、コレコレのマスに入る数字は△。
これは、(1)か(2)かのルールに矛盾。
従って、
△△のマスに△の数字は入らない。

とかって、長い？ややこしい？背理法、コンピュータを使うと楽そうな方法がＮＧって話だと思うけど、何段の推論になるとダメとか、線引きのしようも無いと思うので、「背理法だから」って言い方はチョット居心地が悪いと思います。

補足

あなたの言われているところは背理法でなくとも解けます。この問題で背理法が必要になるのは、はるか先です。
しかも２か所あります。
実際に紙の上で解く場合、背理法を使う直前まで戻る（記録）しておく必要があります。（パソコンですればいいなんて言わないで）先の見えない迷路でやみくもに先に進んでみるのは偶然性を期待するだけでパズル的思考は皆無です。そもそも背理法を使わなくてもいくらでも難問はできます。この方法で難問を安易をつくるのはある意味、怠慢だと思います。例え１段の推論であっても背理法無しで解ける問題の方が正当だと思います。