Re: [問題] 騎士踩地雷（knightsweeper）002

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者etrexetrex (moonet)時間16年前 (2010/02/02 11:03)推噓0(0推 0噓 3→)

留言3則, 2人參與討論串3/4 (看更多)

※ 引述《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)