Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve

Time：2020-09-07 12:13:31
Class：Weblog
Read：29

Use digit 1 to 8 only once and fill the below grid:

digit-grid

The arithmetic should proceed exactly from left to right and top to the bottom.

Bruteforce Algorithm to Solve the Numbers Grid Puzzle

The bruteforce algorithm should be a very trivial solution. There are 8 numbers to put in the 8 cell. Thus, the total solutions to check is 8! We can use 8 ugly nested loops and skip duplicates. The code nesting isn’t looking good, and is not flexible when the puzzle is later extended e.g. to a much bigger dimension 10×10 etc.

for (let a = 1; a <= 8; ++ a) {
    let b = 13 - a;
    if (b >= 9) continue;
    if (b == a) continue;
    for (let c = 1; c <= 8; ++ c) {
        if ((c == a) || (c == b)) continue;
        for (let d = 1; d <= 8; ++ d) {
            if ((d == a) || (d == b) || (d == c)) continue;
            for (let e = 1; e <= 8; ++ e) {
                if ((e == a) || (e == b) || (e == c) || (e == d)) continue;
                if ((c - d) * e == 4) {
                    for (let f = 1; f <= 8; ++ f) {
                        if ((f == a) || (f == b) || (f == c) || (f == d) || (f == e)) continue;
                        for (let g = 1; g <= 8; ++ g) {
                            if ((g == a) || (g == b) || (g == c) || (g == d) || (g == e) || (g == f)) continue;
                            for (let h = 1; h <= 8; ++ h) {
                                if ((h == a) || (h == b) || (h == c) || (h == d) || (h == e) || (h == f) || (h == g)) continue;
                                if ((a + c == 4 * f) && ((b - d) * g == 4) && (9 - e - h == 4)) {
                                    console.log(a, "+", b, "-", 9, "=4");
                                    console.log(c, "-", d, "*", e, "=4");
                                    console.log(f, "+", g, "-", h, "=4");
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

for (let a = 1; a <= 8; ++ a) {
    let b = 13 - a;
    if (b >= 9) continue;
    if (b == a) continue;
    for (let c = 1; c <= 8; ++ c) {
        if ((c == a) || (c == b)) continue;
        for (let d = 1; d <= 8; ++ d) {
            if ((d == a) || (d == b) || (d == c)) continue;
            for (let e = 1; e <= 8; ++ e) {
                if ((e == a) || (e == b) || (e == c) || (e == d)) continue;
                if ((c - d) * e == 4) {
                    for (let f = 1; f <= 8; ++ f) {
                        if ((f == a) || (f == b) || (f == c) || (f == d) || (f == e)) continue;
                        for (let g = 1; g <= 8; ++ g) {
                            if ((g == a) || (g == b) || (g == c) || (g == d) || (g == e) || (g == f)) continue;
                            for (let h = 1; h <= 8; ++ h) {
                                if ((h == a) || (h == b) || (h == c) || (h == d) || (h == e) || (h == f) || (h == g)) continue;
                                if ((a + c == 4 * f) && ((b - d) * g == 4) && (9 - e - h == 4)) {
                                    console.log(a, "+", b, "-", 9, "=4");
                                    console.log(c, "-", d, "*", e, "=4");
                                    console.log(f, "+", g, "-", h, "=4");
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

The only solution found by the above Javascript bruteforce code is:

5 + 8 - 9 =4
+   -   -
7 - 6 * 4 =4
/   *   -
3 + 2 - 1 =4
=   =   =
4   4   4

Another bruteforce algorithm would be to obtain the 8! permutation and then check the validity of each solution.

DFS with BackTracking Algorithm to Solve the Number Puzzle

A better approach would be to use Depth First Search Algorithm to backtracking the search tree – this allows us to abandon the search branches which can’t be solutions:

(function dfs(sol) {
    if (sol.length == 9) {
        console.log(sol);
        return true;
    }
    if (sol.length == 2) {
        if (sol[0] + sol[1] - 9 != 4) return false;
        sol.push(9); // 9 is given
        //return dfs(sol);
    }
    for (let i = 1; i <= 8; ++ i) {
        if (!sol.includes(i)) { // can only use once
            if (sol.length == 5) {
                // second row
                if ((sol[3] - sol[4]) * i != 4) continue;
            }
            if (sol.length == 6) {
                // first column
                if ((sol[0] + sol[3]) / i != 4) continue;
            }
            if (sol.length == 7) {
                // second column
                if ((sol[1] - sol[4]) * i != 4) continue;
            }
            if (sol.length == 8) {
                // third row
                if (sol[6] + sol[7] - i != 4) continue;
                // third column
                if (sol[2] - sol[5] - i != 4) continue;
            }
            sol.push(i);       
            if (dfs(sol)) {
                return true;
            }
            sol.pop();
        }
    }
    return false;
})([]);

(function dfs(sol) {
    if (sol.length == 9) {
        console.log(sol);
        return true;
    }
    if (sol.length == 2) {
        if (sol[0] + sol[1] - 9 != 4) return false;
        sol.push(9); // 9 is given
        //return dfs(sol);
    }
    for (let i = 1; i <= 8; ++ i) {
        if (!sol.includes(i)) { // can only use once
            if (sol.length == 5) {
                // second row
                if ((sol[3] - sol[4]) * i != 4) continue;
            }
            if (sol.length == 6) {
                // first column
                if ((sol[0] + sol[3]) / i != 4) continue;
            }
            if (sol.length == 7) {
                // second column
                if ((sol[1] - sol[4]) * i != 4) continue;
            }
            if (sol.length == 8) {
                // third row
                if (sol[6] + sol[7] - i != 4) continue;
                // third column
                if (sol[2] - sol[5] - i != 4) continue;
            }
            sol.push(i);       
            if (dfs(sol)) {
                return true;
            }
            sol.pop();
        }
    }
    return false;
})([]);

Running the above Javascript DFS code prints the 8 numbers that is the correct solution:

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

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

The solution is superior to the above bruteforce approach. This can also be solved via Breadth First Search Algorithm.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
How to Earn Bitcoin Through Blogging
5 PayPal Alternatives for Bloggers and Solopreneurs
Can WordPress Make Other E-commerce Platforms Obsolete?
How to Start a Food Blog (A Step-By-Step 2019 Guide)
3 Possible Solutions to the Most Common Corporate Blogging Probl
Why Social Media is Crucial to Your Marketing Efforts
The Difference Between Gillette & Nike Ads
Result-Driven Trends in 2019 to Get Backlinks from Quality Websi
The Contiguous Binary Array with Equal Numbers of Ones and Zeros
Microbit Programming: Showing a Running Pixel on the LED

Comment list

Comment add: Name：　Check：