作者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