An algorithm that finds a sequence of numbers to fill a square grid

Question

Given numbers 1,2,3,4,5,6,7,8 I need them to replace the x's so that each side adds up to the number in the centre.

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

As a start I have looped over the numbers to find all of the possible combinations.

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]]);
            }
        }           
    }   
}

Next I have joined the numbers together end to end

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]);
        }

      }
    }
  }
}

I have not currently put a check in to make sure each combination of numbers is only used once, which is how I would solve this.

I really would like to know an overall better approach to solving this problem.

Answer 1

There's really no need to enumerate all 40,320 permutations of the numbers, since 4 of the 8 positions are automatically filled by subtracting the two neighbouring values from the target. So there are only 4 variables and at most 1,680 permutations:

A   B   C
D  12   E
F   G   H

Any choice of A and B determines C, then any choice of D determines F, and any choice of E determines H and G, so A, B D and E are the variables.

You could do this iteratively with 4 nested loops, as shown below, or recursively, which will be easier to adapt to other grid sizes.

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
            }
        }
    }
}

---

In its simplest iterative form, and using Daniel Wagner's suggestion of only generating unique solutions which can then be rotated and mirrored, you get something like the code example below. The code in the inner loop is run just 56 times, and there are a total of 142 indexOf() calls.

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

I spent a bit of time rethinking the approach to this. I figured a nice solution would be to have an indexed object so as you loop through the different combinations that make up the central number, you know the next number will need to start with your current selections last number, so if you take

[1, 3, 8]

You know you will need to look at combinations that start with 8

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

This will leave only two options to look through.

I am sure my code could be refactored, but it is late!

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;
}

Answer 3

Well this is a simple implementation. I am sure by a dynamical programming approach i could come with a more efficient solution however as of now due to my limited time i can only present a straightfoeward method. Which turns out to be decently fast since i use one of the most efficient permutation algorithms in JS.

It worls as follows;

• Get all permutations of the provided numbers array.
• Check if we have a valid permutation.

The returned valid permutations shall be interpreted as values to be set starting from the upper left corner and inserted clockwise.

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]));

So as you will see for input 12 and [1,2,3,4,5,6,7,8] we have 8 separate solutions as;

[ [ 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 ] ]