A computer program designed to determine a series of numbers needed to complete a square grid

Question

A computer program designed to determine a series of numbers needed to complete a square grid

Given the numbers 1, 2, 3, 4, 5, 6, 7, 8, I am seeking to replace the x's in such a way that each side adds up to the number in the center.

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

Initially, I have iterated over the numbers to identify all potential 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, the numbers have been concatenated 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]);
        }

      }
    }
  }
}

Currently, there is no check in place to ensure each set of numbers is only used once, which is my proposed solution.

I am open to suggestions on a more efficient approach to solving this problem.

javascript algorithm

Answer 1

Answer №1

There's no need to list out all 40,320 permutations of the numbers because 4 of the 8 positions are automatically filled by subtracting the two neighboring values from the target. Therefore, there are only 4 variables and a maximum of 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. Therefore, A, B, D, and E are the variables.

You can approach this iteratively with 4 nested loops, as shown below, or recursively, which will make it 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 the simplest iterative form, and following Daniel Wagner's suggestion to generate unique solutions that can be rotated and mirrored, the code example below showcases this. The code in the inner loop only runs 56 times, with 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("× 4 rotations and 2 mirrorings (8 solutions per result)");

Answer 2

There's no need to list out all 40,320 permutations of the numbers because 4 of the 8 positions are automatically filled by subtracting the two neighboring values from the target. Therefore, there are only 4 variables and a maximum of 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. Therefore, A, B, D, and E are the variables.

You can approach this iteratively with 4 nested loops, as shown below, or recursively, which will make it 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 the simplest iterative form, and following Daniel Wagner's suggestion to generate unique solutions that can be rotated and mirrored, the code example below showcases this. The code in the inner loop only runs 56 times, with 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("× 4 rotations and 2 mirrorings (8 solutions per result)");

Answer 3

Answer №2

After taking some time to reconsider the problem, I came up with a new approach. I thought it would be beneficial to use an indexed object to streamline the process. By organizing the combinations based on the central number, I could easily determine the next number to consider. For instance, if you start with the combination [1, 3, 8], you know that the next set should begin with 8:

[1, 3, 8]

Resulting in:

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

This method significantly narrows down the options to explore.

Though I believe there is room for improvement in my code, I will have to revisit it later as it is quite 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 4

After taking some time to reconsider the problem, I came up with a new approach. I thought it would be beneficial to use an indexed object to streamline the process. By organizing the combinations based on the central number, I could easily determine the next number to consider. For instance, if you start with the combination [1, 3, 8], you know that the next set should begin with 8:

[1, 3, 8]

Resulting in:

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

This method significantly narrows down the options to explore.

Though I believe there is room for improvement in my code, I will have to revisit it later as it is quite 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 5

Answer №3

This implementation may be considered quite simple. While a dynamic programming approach could potentially yield a more efficient solution, my current time constraints limit me to presenting a straightforward method. Despite this limitation, the method is reasonably fast, utilizing what I believe to be one of the most efficient permutation algorithms available in JS. The process is summarized as follows:

Generate all possible permutations of the given numbers array.
Evaluate each permutation to determine if it is valid.

The valid permutations obtained are then interpreted as values to be placed starting from the upper left corner and progressing clockwise.

function solve4(n,a){
  
  function perm(a){
    // Implementation of permutation function
  }
  
  function validChoices(chs,n){
    // Function to filter out valid choices based on specific conditions
  }
  
  return validChoices(perm(a),n);
}

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

For the input values 12 and [1,2,3,4,5,6,7,8], this method yields 8 distinct solutions, such 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 ] ]

Answer 6

This implementation may be considered quite simple. While a dynamic programming approach could potentially yield a more efficient solution, my current time constraints limit me to presenting a straightforward method. Despite this limitation, the method is reasonably fast, utilizing what I believe to be one of the most efficient permutation algorithms available in JS. The process is summarized as follows:

Generate all possible permutations of the given numbers array.
Evaluate each permutation to determine if it is valid.

The valid permutations obtained are then interpreted as values to be placed starting from the upper left corner and progressing clockwise.

function solve4(n,a){
  
  function perm(a){
    // Implementation of permutation function
  }
  
  function validChoices(chs,n){
    // Function to filter out valid choices based on specific conditions
  }
  
  return validChoices(perm(a),n);
}

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

For the input values 12 and [1,2,3,4,5,6,7,8], this method yields 8 distinct solutions, such 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 ] ]

A computer program designed to determine a series of numbers needed to complete a square grid

Answer №1

Answer №2

Answer №3

Similar questions

Is it possible to create an online game using JavaScript?

Organizing a set of div elements based on their ID attributes

Creating a minigame using JQuery (Javascript)

I'm having trouble getting my home.js to render in the outlet component

Utilizing HTML5 Canvas for Shadow Effects with Gradients

Error [ERR_MODULE_NOT_FOUND]: Module could not be located in vscode

Executing a C# method from within a .js file using a Javascript function in a .cs file

Once the window width exceeds $(window).width(), the mouseenter function is triggered exponentially

Filtering rows of an HTML table that contain links in the `<href>` column data in real time

Is there a way for me to manage the rendering of a three.js scene?

The universal CSS variables of Material UI

Learn how to incorporate latitude and longitude coding into PHP to display a map icon that correctly redirects to the desired URL when clicked

What could be causing the API link to not update properly when using Angular binding within the ngOnInit method?

Optimizing JavaScript performance by packaging files with Browserify

Discover the most frequent value in an array by utilizing JavaScript

It appears that the flex-grow property is not functioning as expected

Generating and Importing Graphics through Iterations in Javascript

"Enhance the visual appeal of your Vue.js application by incorporating a stylish background image

Adjusting the size of the iframe to match the dimensions of the window

What methods can a controller use to verify the legitimacy of the scope?