※ 引述《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) ※ 编辑: etrexetrex 来自: 140.118.9.202 (02/02 11:22)