作者etrexetrex (moonet)
看板puzzle
標題Re: [問題] 騎士踩地雷（knightsweeper）002
時間Tue Feb 2 11:03:48 2010
※ 引述《puzzlez (帕索)》之銘言：
: 星期一的沉悶，用一道謎題來打破吧！ ‧ ‧
: ‧ ‧
: 請將20個騎士，放入沒有數字的空格裡。 騎
: 盤中的數字，代表有幾個騎士正在攻擊那個格子。 ‧ ‧
: ‧ ‧
: 你能夠像踩地雷那樣，把全部的騎士都找出來嗎？ ▲圓點為騎士攻擊之格
: ‧‧‧１‧‧１‧‧‧
: ‧１１１‧‧１‧‧１
: １‧‧‧‧‧２３‧‧
: ‧１‧２‧１‧２‧‧
: ‧‧‧１２‧１‧‧‧
: ‧２‧‧‧‧‧５‧１
: ‧‧１１２‧‧‧‧‧ 這次一個「０」也沒有哦～咯咯咯……
: ‧‧１‧‧‧‧１‧‧
: ‧‧‧２‧‧１‧‧‧
: ‧‧‧‧‧１２‧‧‧
有些格子是無效的格子 不管放不放騎士都不影響
因為他們沒有攻擊到任何一個數字
‧‧騎１‧‧１‧‧騎
‧１１１‧‧１‧‧１
１‧‧‧‧‧２３‧‧
‧１‧２‧１‧２‧‧
騎‧‧１２‧１‧‧‧
‧２‧‧‧‧‧５‧１
‧騎１１２‧騎‧騎‧
‧‧１騎‧‧‧１‧騎
‧‧‧２‧‧１‧‧‧
騎‧騎‧‧１２騎‧騎
所以說當我們使用少於20個騎士去滿足所有數字的時候
可以用這些X的位置來補滿20個
找出這些格子是因為這樣才能避免解矩陣的時候遇到無窮多解的問題
定義變數 M(i,j)
Ｍ ｊ
０１２３４５６７８９
０ ‧‧騎１‧‧１‧‧騎
１ ‧１１１‧‧１‧‧１
２ １‧‧‧‧‧２３‧‧
３ ‧１‧２‧１‧２‧‧
ｉ ４ 騎‧‧１２‧１‧‧‧
５ ‧２‧‧‧‧‧５‧１
６ ‧騎１１２‧騎‧騎‧
７ ‧‧１騎‧‧‧１‧騎
８ ‧‧‧２‧‧１‧‧‧
９ 騎‧騎‧‧１２騎‧騎
M(i,j) = 0 or 1 ,if M(i,j) 原本是 ‧
M(i,j) = M(i,j) ,if M(i,j) 原本是 １ ２ ３ ５
M(i,j) 不存在 ,if M(i,j) 原本是 騎
定義限制式 每個數字會產生一條限制式，舉例來說
M(0,3)的限制式：
M(2,2) + M(2,4) + M(1,5) = 1
M(5,7)的限制式：
M(3,6) + M(3,8) + M(4,5) + M(4,9) + M(6,5) + M(6,9) + M(7,6) + M(7,8) = 5
用這29個限制式可以排出一個 29 * 59 的矩陣Ａ 跟 29 * 1 的矩陣Ｂ
解ＡＸ＝Ｂ
如果Ｘ的每一項剛好等於 0 or 1 就是答案
如果不能剛好等於 0 or 1，就要加上限制式
M(i,j) >= 0
M(i,j) <= 1
變成在解線性規劃問題
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.9.202
※ 編輯: etrexetrex 來自: 140.118.9.202 (02/02 11:04)
※ 編輯: etrexetrex 來自: 140.118.9.202 (02/02 11:04)
1F：→ EIORU:題目如果可以使用少於20個騎士去滿足所有數字..就不是題目 02/02 11:15
※ 編輯: etrexetrex 來自: 140.118.9.202 (02/02 11:22)
2F：→ etrexetrex:不一定吧 要看題目怎麼出 有機會找到少於20個騎士的解 02/02 11:24
3F：→ etrexetrex:直接解AX = B 是失敗的 因為限制式數量小於變數 02/02 18:44