作者kissuo (Evolution ...)
看板Prob_Solve
標題[問題] 關於窮舉卻又無法證明他是無解的題目
時間Tue Oct 21 16:28:55 2008
最近遇到一個老師給的問題～可是又不知到怎麼解
想問一下版上的高手們
先舉一個例子
資工系的人一定聽過 西洋棋 8 Queen Puzzle這個問題
就是在一個8*8的棋盤上要怎麼放8個皇后才不會讓彼此互咬
(皇后可以走直的，橫的，跟斜的)
既然如此，如果我們放9個皇后在同一個棋盤上的話，整個題目肯定變成無解的
即使我們不知道他是無解，也可以利用窮舉來證明他是無解的
現在需要一種題目
他是利用窮舉法把所有可能的狀況都舉出來了
卻還是不能夠顯示出他是無解的
有這種題目嗎?
--
-----------------------------------------------------------------
" Kids are great. Unfortunately,they grow up and become jerks ."
From Sir Charles
-----------------------------------------------------------------
http://www.wretch.cc/album/cktmilk
原子小叮噹，機器貓小金剛 = ="a .....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.177.198.215
1F：推 ledia:halting problem ? XD 10/21 16:34
2F：→ Pash77:樓上... 10/21 17:18
3F：→ sunneo:halting problem確實符合他的需求 XDrz 10/21 20:33
4F：推 Hseuler:羅素悖論 10/22 00:00
5F：推 DJWS:中央氣象局的天氣預報? "明天到底會不會下雨?" 10/22 13:43
6F：推 xcycl:halting problem 怎麼會呢 ...= =a 10/24 00:24
7F：推 march20:但是在那之前要定義 "窮舉"? 無限但可數算不算? 10/26 18:03
8F：推 bobju:窮舉應該是對可數有限集列出所有子集. 11/11 11:38