選擇最佳矩陣

Question

我給定尺寸Ni*Mi其中1<=N<=4 and 1<=M<=4, for all 1 <= i <= X

遊戲包括選擇從所述給定X矩陣中的一個的任何矩形（子矩陣），並刪除該子矩陣的的X矩陣。

例如：我們有一個大小爲4x4的矩陣。玩家1可以選擇尺寸爲4x4（本例中爲整個矩陣）的子矩陣並將其移除。或者他們可以選擇2x2或1x1或2x3的子矩陣或任何有效的子矩陣，並將其從4x4矩陣中移除，並且剩下的矩陣留在遊戲中。

不能移動的玩家輸了。

哪位球員獲勝？

兩個播放器都播放最佳。

Answer 1

（之前馬拉卡發表了他對斯普拉格格蘭迪定理的答案，我試圖找出遊戲的最佳策略，下面我將介紹它，也許它也可以用於編碼解決方案。）

遊戲的結果是每個矩形在奇數還是偶數移動中被移除的結果。如果總的移動次數是奇數，玩家1獲勝;如果是偶數，玩家2獲勝。

讓我們來看看可能的矩形：

對於所有「正常」的矩形（除了2×2和1×1）玩家誰首先除去它的一部分可以決定是否在完全去除奇數次移動（例如通過一次完全移除它）或以偶數次移動;用黃色表示的細胞顯示出第一步移動，使玩家處於控制之下。

對於只有1個單元寬度的「細」矩形，立即執行奇數/偶數判定（通過刪除整個矩形或者留下1個單元）。對於其他「正常」矩形，根據其他玩家的動作，決定從1次延遲到3次。

1x1矩形只能在一次移動中移除（即奇數次移動）。 2×2矩形可以一次移除，但玩家不能通過移除部分移動來強制進行偶數移動;其他玩家總是可以決定單數還是偶數。

正如您從圖像中用黃色表示的動作所看到的那樣，創建對稱情境（例如，將4x4方塊分成兩個4x1矩形）的動作會使創建此情境的人員控制此結果長方形。他可以例如強制偶數的移動這個矩形是這樣的：

這也適用於整個遊戲：如果一個球員的舉動導致對稱的情況下（例如，兩個相同的L形和四個3X1的矩形）他可以通過鏡像來響應其他玩家的動作，然後當只剩下一個大於1x1的矩形時，他可以選擇將其完全移除或留下一個單元格（取決於剩餘單個單元格的數量是否爲奇數甚至）並贏得比賽。

所以這個策略歸結爲創造一個對稱的情況，而不是讓另一個玩家有機會創造一個對稱的情況。

注意：通過移除3x3,4x3或4x4矩形的中心並創建一個循環，可以創建更復雜的對稱性。而不是鏡像其他玩家的動作，然後將它們旋轉180度（即點鏡像）。

基於這些想法的一些比賽的結果：

• 一個矩形：玩家1勝。
• 兩個相同的矩形：玩家2獲勝。
• 1x1和一個薄矩形：玩家1獲勝。
• 1x1和2x2矩形：玩家2獲勝。
• 1x1和更大的矩形：玩家1獲勝。
• 一個2x2和一個薄矩形：玩家1獲勝。
• 2x2和更大的矩形：玩家1獲勝。
• 三個相同的矩形：玩家1獲勝。
• 1x1，2x2和其他任何矩形：玩家1獲勝。
• 偶數個相同的矩形：玩家2獲勝。
• 偶數和任何其他矩形：玩家1獲勝。
• 奇數個相同的矩形：玩家1獲勝。

---

下面是斯普萊格 - 格隆第定理的實現，在馬拉卡的答案解釋。它使用預先計算的nimbers列表，最多爲4x4的矩形。

function outcome(rectangles) { 
 
    var n = 0, nimbers = [[1,2,3,4],[2,1,5,8],[3,5,4,7],[4,8,7,3]]; 
 
    for (var i = 0; i < rectangles.length; i++) { 
 
     n ^= nimbers[rectangles[i][0] - 1][rectangles[i][1] - 1]; 
 
    } 
 
    return n > 0 ? 1 : 2; 
 
} 
 
document.write("Player " + outcome([[3,3],[3,4],[4,4]]) + " wins.<br>"); 
 
document.write("Player " + outcome([[1,1],[2,2],[3,3],[4,4]]) + " wins.");

任何4x4矩陣的nimber可以與下面的算法來計算。 4×4矩陣由16比特模式表示，例如， 65535是一個填充了矩陣的矩陣。預先計算所有矩形（可能的移動）的列表，以位模式表示。

function nimber(matrix) { 
 
    var rect = [ 1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 
 
        16, 17, 32, 34, 48, 51, 64, 68, 96, 102, 
 
       112, 119, 128, 136, 192, 204, 224, 238, 240, 255, 
 
       256, 272, 273, 512, 544, 546, 768, 816, 819, 1024, 
 
       1088, 1092, 1536, 1632, 1638, 1792, 1904, 1911, 2048, 2176, 
 
       2184, 3072, 3264, 3276, 3584, 3808, 3822, 3840, 4080, 4095, 
 
       4096, 4352, 4368, 4369, 8192, 8704, 8736, 8738,12288,13056, 
 
       13104,13107,16384,17408,17472,17476,24576,26112,26208,26214, 
 
       28672,30464,30576,30583,32768,34816,34944,34952,49152,52224, 
 
       52416,52428,57344,60928,61152,61166,61440,65280,65520,65535]; 
 
    var memo = [0];         // nimber of empty matrix is 0 
 
    return nim(matrix); 
 

 
    function nim(current) { 
 
     if (memo.hasOwnProperty(current)) return memo[current]; // use memoized value 
 
     var exclude = [];      // set of nimbers of reachable states 
 
     for (var i = 0; i < rect.length; i++) { 
 
      if ((current & rect[i]) == rect[i]) { // this rectangle is a valid move 
 
       var next = current & ~rect[i];     // remove rectangle 
 
       exclude[nim(next)] = true;   // recurse and add nimber to set 
 
      } 
 
     } 
 
     return (memo[current] = mex(exclude));     // memoize this nimber 
 
    } 
 
    function mex(n) {        // minimum excludant of nimber set 
 
     var m = 0; 
 
     while (n[m]) ++m; 
 
     return m; 
 
    } 
 
} 
 

 
document.write(nimber(65535)); // 0b1111111111111111 represents a filled 4x4 matrix

可以這樣產生的表示在4×4矩陣中的所有的尺寸，位置和取向的矩形的16位模式的列表：

function rectangles(width, height) { 
 
    var rect = [], line = (1 << width) - 1; 
 
    for (var y = 0; y < height; y++) { 
 
     for (var x = 0; x < width; x++) { 
 
      for (var h = 1; h <= height - y; h++) { 
 
       for (var w = 1; w <= width - x; w++) { 
 
        var bits = ((line >> (width - w)) << (width - x - w)) << (y * width) 
 
        for (var row = 1; row < h; row++) { 
 
         bits |= (bits << width); 
 
        } 
 
        rect.push(bits); 
 
       } 
 
      } 
 
     } 
 
    } 
 
    return rect; 
 
} 
 
document.write(rectangles(4,4));

Answer 2

此問題已解決Sprague Grundy theorem ，其中說，當你對單個矩陣的nimbers進行異或時，只有當結果爲0時，纔會移動的玩家輸掉（因爲任何移動都會使失去的位置變成勝利的位置，而另一個玩家則可以將勝出的位置變成再次失去位置等等，這就是nim式比賽的本質）。

nimbers是遞歸計算的，矩陣的nimber是所有可到達狀態的nimbers的mex（最小的獨佔性=集合中不存在的最小非負整數）。

全0是0，你沒有一個有效的舉動，因此它是一個損失（0）。

整整1是1，因爲唯一可到達的位置爲0和MEX（0）= 1。

對於兩個1就要決定它們是否相鄰或不相鄰= MEX（0，1） = 2，不相鄰= mex（1）= 0 ...依此類推。

實施例：

1 0 0 0  1 1 0  1 1 
0 0 1 1  0 0 0  1 1 
0 0 1 0  0 0 1 
0 0 0 0 
    =   =  = 
    2 xor 3 xor 1 = 0 => player to move loses. 

甲快速實現可能看起來像這樣：

1. 計算nimbers爲16（10具有對稱性）不同的情況預先，並將它們存儲在數組中。

2. 分配結果= 0

3. 結果=結果XOR nimbers [readRowCount（）] [readColCount（）]

4. 重複3，直到所有的矩陣尺寸是讀

5. 如果結果！= 0那麼第一個玩家贏得其他第二個玩家

例2：微小的計算

matrix: 
1 1 
1 1 

valid moves: 
0 1* 1 0* 1 1* 1 1* 0 0 1 1+ 0 0+ 1 0+ 0 1+ 
1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 
         = 
         0 by definition 

The other matrices can be grouped into 2 groups * and + because of symmetries. 

Reachable positions from *: 
0 1 0 1 0 0 
0 1 1 0 0 1 
=  =  = 
      1 = mex(0), because the only reachable position has a nimber of 0 
     0 = mex(1), because the only reachable position has a nimber of 1 
2 = mex(0,1), because the reachable positions have nimbers of 0 and 1 

==> the nimber for * is mex(0, 1, 2) = 3. 

==> we already know now that the nimber of + is 2. 

==> the nimber of the given matrix is mex(0, 2, 3) = 1.