騎士踩地雷（knightsweeper）002 - 拼圖

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

變成在解線性規劃問題

--