找到一個數字序列來填充一個方格的算法

Question

給定的數字1,2,3,4,5,6,7,8我需要它們來替換x's，以便每個邊加起來的數字中心。

*-*---*-* 
|x| x |x| 
*-*---*-* 
|x| 12|x| 
*-*---*-* 
|x| x |x| 
*-*---*-* 

由於一開始我都環繞在數字中尋找所有可能的組合。

var range = [1,2,3,4,5,6,7,8]; 
var target = 12; 
var matches = []; 

for (x = 0; x < range.length; x ++){ 
    for (y = 0; y < range.length; y ++){ 
     if (y === x){ 
      continue; 
     } 
     for (z = 0; z < range.length; z ++){ 
      if (z === y || z === x){ 
       continue; 
      } 

      if (range[x] + range[y] + range[z] === target){ 
       matches.push([range[x], range[y], range[z]]); 
      } 
     }   
    } 
} 

接下來，我也加入了數字加在一起端到端

for (j=0; j < matches.length; j++){ 
    for (k=0; k < matches.length; k++){ 
    if (j==k) continue; 
    //if (matches[j][2] != matches[k][0]) continue; 
    for (l=0; l < matches.length; l++){ 
     if (l==j || l==k) continue; 
     //if (matches[k][2] != matches[l][0]) continue; 
     for (m=0; m < matches.length; m++){ 
     if (m==j || m==k || m==l) continue; 
     if (matches[l][2] != matches[m][0]) continue; 
     if (matches[m][2] != matches[j][0]){ 
      console.log(matches[j], matches[k], matches[l], matches[m]); 
     } 

     } 
    } 
    } 
} 

我還沒有現在把支票以確保數字只能使用一次的每個組合，這是我會怎樣解決這個。

我真的很想知道一個整體更好的方法來解決這個問題。

Answer 1

真的沒有必要列舉數字的所有排列40320，由於8位的4由從目標減去兩個相鄰值自動填充。所以只有4個變量和至多1680名的排列：

A B C 
D 12 E 
F G H 

A和B中的任何選擇決定C，然後d的任何選擇決定女，和E的任何選擇決定H和G，所以A，BD和E是變量。

您可以用4個嵌套循環（如下所示）或遞歸方式迭代執行此操作，這將更容易適應其他網格大小。

for A is 1 to 8 
    for B is any available number < target - A 
     C = target - (A + B) 
     if C is not available, skip to next B 
     for D is any available number < target - A 
      F = target - (A + D) 
      if F is not available, skip to next D 
      for E is any available number < target - C 
       H = target - (C + E) 
       if H is not available, skip to next E 
       G = target - (F + H) 
       if G is available, store this combination 
      } 
     } 
    } 
} 

---

在最簡單的迭代形式，以及使用的僅產生獨特的解決方案，然後可以旋轉和鏡像的丹尼爾·瓦格納的建議，你得到的東西像下面的代碼示例。內循環中的代碼僅運行56次，總共有142個indexOf()調用。

function numberSquare(target) { 
 
    for (var a = 1; a < 9; a++) { 
 
     for (var c = a + 1; c < 9 && c < target - a; c++) { 
 
      var b = target - (a + c); 
 
      if ([a,c].indexOf(b) > -1 || b > 8) continue; 
 
      for (var f = c + 1; f < 9 && f < target - a; f++) { 
 
       var d = target - (a + f); 
 
       if ([a,b,c,f].indexOf(d) > -1 || d > 8) continue; 
 
       for (var h = a + 1; h < 9 && h < target - c && h < target - f; h++) { 
 
        if ([b,c,d,f].indexOf(h) > -1) continue; 
 
        var e = target - (c + h); 
 
        if ([a,b,c,d,f,h].indexOf(e) > -1 || e > 8) continue; 
 
        var g = target - (f + h); 
 
        if ([a,b,c,d,e,f,h].indexOf(g) > -1 || g > 8) continue; 
 
        document.write([a,b,c] + "<br>" + [d,'_',e] + "<br>" + [f,g,h] + "<br><br>"); 
 
       } 
 
      } 
 
     } 
 
    } 
 
} 
 

 
numberSquare(12); 
 
document.write("&times; 4 rotations and 2 mirrorings (8 solutions per result)");

Answer 2

這是一個簡單的實現。我確信，通過動態編程方法，我可以提供更高效的解決方案，但由於時間有限，我只能提供一種簡單的方法。事實證明，由於我使用one of the most efficient permutation algorithms in JS，所以速度非常快。

它包含以下內容;

• 獲取提供的數字數組的所有排列。
• 檢查我們是否有有效的置換。

返回的有效排列應解釋爲從左上角開始順時針插入的值。

function solve4(n,a){ 
 
    
 
    function perm(a){ 
 
    var r = [[a[0]]], 
 
     t = [], 
 
     s = []; 
 
    if (a.length <= 1) return a; 
 
    for (var i = 1, la = a.length; i < la; i++){ 
 
     for (var j = 0, lr = r.length; j < lr; j++){ 
 
     r[j].push(a[i]); 
 
     t.push(r[j]); 
 
     for(var k = 1, lrj = r[j].length; k < lrj; k++){ 
 
      for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj]; 
 
      t[t.length] = s; 
 
      s = []; 
 
     } 
 
     } 
 
     r = t; 
 
     t = []; 
 
    } 
 
    return r; 
 
    } 
 
    
 
    function validChoices(chs,n){//console.log(chs) 
 
    return chs.filter(ch => ch[0]+ch[1]+ch[2] === n && 
 
          ch[2]+ch[3]+ch[4] === n && 
 
          ch[4]+ch[5]+ch[6] === n && 
 
          ch[6]+ch[7]+ch[0] === n); 
 
    } 
 
    
 
    return validChoices(perm(a),n); 
 
} 
 

 
console.log(solve4(12,[1,2,3,4,5,6,7,8]));

所以你會輸入12和[1,2,3,4,5,6,7,8]我們有8個獨立的解決方案看;

[ [ 1, 5, 6, 4, 2, 7, 3, 8 ], 
    [ 6, 4, 2, 7, 3, 8, 1, 5 ], 
    [ 2, 7, 3, 8, 1, 5, 6, 4 ], 
    [ 3, 8, 1, 5, 6, 4, 2, 7 ], 
    [ 3, 7, 2, 4, 6, 5, 1, 8 ], 
    [ 2, 4, 6, 5, 1, 8, 3, 7 ], 
    [ 6, 5, 1, 8, 3, 7, 2, 4 ], 
    [ 1, 8, 3, 7, 2, 4, 6, 5 ] ] 

Answer 3

我花了一點時間重新思考的方法這一點。我認爲一個很好的解決方案是建立一個索引對象，以便循環組成中央號碼的不同組合，您知道下一個號碼需要從當前選擇的最後一個號碼開始，所以如果您採取

[1, 3, 8] 

你知道你需要看，隨着8

{ 
    ..., 
    8: [[8, 1, 3], [8, 3, 1]] 
} 

開始將只留下兩個選項翻閱組合。

我確定我的代碼可以重構，但已經晚了！

var range = [1,2,3,4,5,6,7,8]; 
var target = 13; 
var matches = []; 
var keyedMatches = { 
    "1": [], 
    "2": [], 
    "3": [], 
    "4": [], 
    "5": [], 
    "6": [], 
    "7": [], 
    "8": [] 
}; 

let firstSteps = 0; 

for (x = 0; x < range.length; x ++){firstSteps++ 
    for (y = 0; y < range.length; y ++){ 
     if (y === x){ 
      continue; 
     }firstSteps++ 
     for (z = 0; z < range.length; z ++){ 
      if (z === y || z === x){ 
       continue; 
      }firstSteps++ 

      if (range[x] + range[y] + range[z] === target){ 
       matches.push([range[x], range[y], range[z]]); 
       keyedMatches[range[x]].push([range[x], range[y], range[z]]) 
      } 
     }   
    } 
} 
console.log(keyedMatches); 


let secondSteps = 0; 

var currentSelection = []; 
var usedNums = []; 
for (j = 0; j < matches.length; j ++){secondSteps++; 
    usedNums.push(matches[j][0]); 
    usedNums.push(matches[j][1]); 
    usedNums.push(matches[j][2]); 


    var step2 = keyedMatches[usedNums[usedNums.length-1]]; 

    for (k=0; k < step2.length; k++){ 
    if(checkUsed(usedNums, step2[k])) continue; 

    usedNums.push(step2[k][1]); 
    usedNums.push(step2[k][2]); 

    var step3 = keyedMatches[usedNums[usedNums.length-1]]; 

    for (l=0; l < step3.length; l++){ 
     if(checkUsed(usedNums, step3[l])) continue; 
     usedNums.push(step3[l][1]); 
     usedNums.push(step3[l][2]); 


     var step4 = keyedMatches[usedNums[usedNums.length-1]]; 
     for (m=0; m < step4.length; m++){ 

     if(usedNums.indexOf(step4[m][1]) !== -1) continue; 

     if (step4[m][2] != usedNums[0]) continue; 

     usedNums.push(step4[m][1]); 
     console.log(usedNums); 

     // remove the used numbers 
     usedNums.pop(); 

     } 

     // remove the used numbers 
     usedNums.pop(); 
     usedNums.pop(); 
    } 

    // remove the used numbers 
    usedNums.pop(); 
    usedNums.pop(); 
    } 

    usedNums = []; 

} 

function checkUsed(unum, nnum){ 
    if (unum.indexOf(nnum[1]) === -1 && unum.indexOf(nnum[2]) === -1){ 
    return false; 
    } 
    return true; 
}