作者funkie (乾!!草泥馬)
看板puzzle
標題Re: [問題] 數獨卡關求解
時間Sat Jul 2 19:22:23 2016
※ 引述《waterap (呱呱)》之銘言:
http://i.imgur.com/9vFWhvh.jpg 推 funkie: row3:{8,9} {8,9}; row9:{1,8,9} {8,9} => {1,8,9}->{1} 07/02 17:28
推 funkie: unique rectangle of type 1 07/02 17:35
→ waterap: 抱歉,我不懂這解法,可以麻煩解釋一下嗎?為何{1、8、9 07/02 18:13
→ waterap: }有獨解1? 07/02 18:13
推 LPH66: 這個是唯一解理由, 若那裡不是 1 則這個長方形就是 89 互換 07/02 18:35
→ LPH66: 理論上應該要有別的線索才對 07/02 18:36
一個合法的數獨有解則必定是唯一解
因此不能含有deadly pattern
4 cells deadly patteern example:
12 . . | 21 . . | . . .
21 . . | 12 . . | . . .
. . . | . . . | . . .
1,2位置可以互換
所以解的時候可以排除這些可能
{1,8,9}那格如果是8 or 9 就是上面的情況
所以可以刪去候選數8,9
刪去後只剩1 所以那一格是1
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.230.100
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1467458547.A.424.html
推 waterap: 所以,當確定其他地方都無線索才用這方式?還是這也是一 07/02 19:53
→ waterap: 個常用法? 07/02 19:53
→ funkie: 這算最簡單的進階技巧,3格一樣的候選數刪第4格候選數 07/02 21:09
→ funkie: 算是一眼就看的出來 有看到就用囉 07/02 21:13
推 waterap: 謝謝f大講解 07/02 21:22
推 LPH66: 個人是不太喜歡用這種方法, 一個題目要唯一解該有其他線索 07/02 21:49
→ LPH66: 不過如果要把這回事當前提那也不是不能用就是了 07/02 21:50
→ LPH66: 再說這個方法在賢獨是不能用的 07/02 21:51
推 walkwall: 原來如此 07/02 22:54
推 arthurduh1: 唯一解的條件並不是普遍被出題者採用的 07/02 23:11
→ arthurduh1: 但漂亮的題目一般都會這樣自我要求就是 07/02 23:13
可以參考以下網頁的解釋:
http://sudoku.ironmonger.com/howto/deadlyPattern/docs.tpl 第二段有說
There is some debate on the issue of uniqueness in Sudoku puzzles. On one
hand there is nothing in the basic Sudoku rule that specifies uniqueness. On
the other,
there is no logic that can solve a puzzle with multiple solutions so at some point, to get to any one of the solutions you have to guess. ※ 編輯: funkie (106.1.230.100), 07/03/2016 00:28:45
推 LPH66: 其實這個 some point 比大家想像中的還要更早 07/03 01:05
→ LPH66: 因為進階技法的「當某些條件滿足時某些格子因矛盾可刪除」 07/03 01:05
→ LPH66: 這其實就是 guess 了: 某格猜這個數的話經推理得到矛盾 07/03 01:06
→ LPH66: 所以我並不排斥長 backtrack 推理, 但我不喜歡唯一解理由 07/03 01:07
→ LPH66: 嘛, 這也就是為什麼我雖然不喜歡它, 但若把唯一解當前提 07/03 01:09
→ LPH66: 也不是不能用的原因了; 當前提的話上面那句話的矛盾就可以 07/03 01:10
→ LPH66: 包含「和唯一解這前提矛盾」 07/03 01:10
→ wxtab019: 之前有些看過沒唯一解的 後來就沒用這招解了 07/04 00:13
→ funkie: 樓上誤會了 沒唯一解的本來就要猜 猜錯就錯了 並不會用了 07/04 19:54
→ funkie: 這方法就有唯一解 用不用這方法是信仰問題 07/04 19:54
推 LPH66: 推這是信仰問題 07/05 09:30
推 arthurduh1: 遇到沒唯一解的話,用這個方法會遇到的問題是 07/05 09:37
→ arthurduh1: 可能會解到很後面才發現矛盾 07/05 09:38
推 arthurduh1: 所以基本上就要跟試誤法一樣,對後來的推導另外標記 07/05 09:40
→ funkie: 遇到沒唯一解的問題是這題目根本不能靠邏輯解 07/05 14:10
推 arthurduh1: 有的,有些沒有唯一解的題目還是可以手算出全部的解 07/05 15:24
→ arthurduh1: 你要說不能靠邏輯解,有些有唯一解的題目也不行 07/05 15:24
→ arthurduh1: 所以這是兩回事 07/05 15:25
→ arthurduh1: 會建議開始用唯一解條件時就要當作試誤法就是因為 07/05 15:26
→ arthurduh1: 被陰過 07/05 15:27
→ arthurduh1: 但一般來說 可以怪出題者出得不好 這我是沒意見 07/05 15:28
→ funkie: ... 若A B兩種解都和原題目符合請問哪種邏輯可以分得出來? 07/05 17:05
推 arthurduh1: 非唯一解的意思不就是有兩組答案?! A,B都是解阿 07/05 17:25
推 arthurduh1: 我不是都推可以解出 "全部的解" 了 07/05 17:34
→ arthurduh1: 我也說過你可以怪題目不佳不要解 07/05 17:36
→ arthurduh1: 但若至少想解出來,且採用本篇方法,就必須當成試誤 07/05 17:38
→ funkie: 所以你在某一步做了"猜"這件事 發現答案A正確 又"猜"一次 07/05 19:21
→ funkie: 再發現B答案正確 這個遊戲的目標就是要不能猜答案阿 -,- 07/05 19:23
推 arthurduh1: 反過來思考,當題目可能有多解時,本篇方法才是猜答案 07/05 19:26
→ arthurduh1: 所謂猜到底是什麼其實很模糊,我自己是以「記憶體」 07/05 19:27
→ arthurduh1: 用量當判別標準。我也同意盡量不要猜答案,但同時 07/05 19:27
→ arthurduh1: 這也是我盡量不使用本篇方法的原因 07/05 19:28
→ arthurduh1: 要用的時候我一定當試誤法 (所謂試誤法就是猜) 07/05 19:28
→ arthurduh1: 這一切都奠基在到底允不允許多解上 07/05 19:30
→ arthurduh1: 你的引用裡也說到這是有爭議的,所以除非強調唯一解 07/05 19:30
→ arthurduh1: 否則我都會把 本篇方法&試誤法 當最後手段 07/05 19:31
推 arthurduh1: 其實你可以問問自己,當遇到多解題目的時候你怎麼辦? 07/05 19:39
這遊戲的目的是完全不用猜的得到最後答案
當一個題目有多重解要你一定要猜的時候 就是不同的遊戲了
沒有繼續做下去的必要
一個沒有邏輯的問題當然不能用邏輯解
用邏輯去解沒有邏輯的問題得到錯誤的答案
這不是再正常不過了嗎
前面說的爭議你就誤會了
不用這個方法的是因為
只有唯一解是經過推論的結果
有多重解 => 一定要猜
=> 可以不用猜的 => 只有唯一解
這個方法是刪除會得到多重解的分支
這樣才能保證這個遊戲可以不用猜的得到最後答案
所以一個合法的數獨題目不需要猜只能有唯一解
so 這是信仰問題
※ 編輯: funkie (106.1.230.100), 07/05/2016 20:32:24
推 arthurduh1: 我沒有要為了前面的爭議(?)背書阿 我提的是自己所想 07/05 20:38
→ arthurduh1: 的確是信仰問題也沒錯。 依你說會變不同遊戲,我想 07/05 20:38
→ arthurduh1: 應該代表遇到多重解你就不會繼續解下去了? 07/05 20:39
→ arthurduh1: 那就是我說的你覺得題目不佳阿XD 這也OK沒問題呀 07/05 20:39
→ arthurduh1: 我的話是會想釐清這個題目到底出了什麼問題,所以會 07/05 20:40
→ arthurduh1: 試看看能不能完全解出。畢竟解不出來還分「有矛盾」 07/05 20:40
→ arthurduh1: 和「多重解」 但如果不把本篇方法當試誤法,就會 07/05 20:41
→ arthurduh1: 變成無法分辨其中差異。 07/05 20:41
→ arthurduh1: 另外關於「邏輯」這個字眼: 多重解並不違反邏輯 07/05 20:42
→ arthurduh1: 否則我們解 多次方程式 不就都是不合邏輯的行為? 07/05 20:43
→ arthurduh1: 我傾向於邏輯代表的是在很少的步數內能看出結果 07/05 20:44
→ arthurduh1: (在本篇所提到的邏輯) 07/05 20:44
推 arthurduh1: 而有些多重解是真的能夠用很少的步數整理出來的 07/05 20:48
推 arthurduh1: 那個推論的過程其實我也有疑義。只有唯一解應該是規定 07/05 21:04
→ arthurduh1: (某個不一定被接受的規定) 07/05 21:04
→ arthurduh1: 而不是由「可以不用猜」這個模糊的概念推得 07/05 21:05
→ arthurduh1: 除非你的「猜」專指多重解,那就很明確。但這樣就不須 07/05 21:06
→ arthurduh1: 繞這麼多步的推論了 07/05 21:06
推 LPH66: 我很前面就推過了: 開始「猜」的點比各位想像中的還要早 07/06 20:36
→ LPH66: 邏輯推理裡所謂的歸謬法或反證法就是猜一個前提再推出矛盾 07/06 20:37
→ LPH66: 有很多進階數獨技巧的理由歸根究底還是反證法 07/06 20:38
→ LPH66: 當某些格子滿足條件時若哪一格是什麼數字則可以推出矛盾 07/06 20:38
→ LPH66: 所以我才會說長串倒推跟這種技巧邏輯上沒什麼兩樣 07/06 20:39
→ LPH66: 唯一差別只有 arthur 講的「記憶體用量」而已 07/06 20:40
→ wxtab019: 所以意思是 這方法也只是"猜"的其他一種 不一定是正解? 07/06 20:47
推 arthurduh1: 猜跟邏輯技巧的分界仔細想想會發現有模糊地帶 07/06 21:50
→ arthurduh1: 其實我也沒說原PO說錯什麼,只是想把非唯一解的題目 07/06 21:50
→ arthurduh1: 拉近考慮範圍而已 07/06 21:51
推 arthurduh1: *進 07/06 21:54
→ arthurduh1: 唯一覺得不妥的就是要嘛就把唯一解當規則 07/06 21:54
→ arthurduh1: 要嘛就是接受非唯一解。 而不是因為「不能猜」這個 07/06 21:55
→ arthurduh1: 理由而說不允許非唯一解 07/06 21:55
→ arthurduh1: 若把唯一解當條件 => 本篇方法是個強大的技巧 07/06 21:57
→ arthurduh1: 若接受非唯一解 => 本篇方法是「猜」 07/06 21:58
推 arthurduh1: to wxtab: 能解出來的(i.e. 沒有與規則衝突)都是正解 07/06 22:05
→ arthurduh1: 正解與否跟你用什麼方法無關 07/06 22:05