Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve

  • 时间：2020-09-07 12:13:31
  • 分类：网络文摘
  • 阅读：126 次

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

digit-grid Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve the Numbers Grid Puzzle algorithms brute force DFS javascript

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

(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:

1
2
3
4

[
  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) —

推荐阅读：
Top Tech Trends To Watch For In 2016　 7 ABC’s for Turning Words into Money with Your Blog　 Here’s What You Don’t Know About The Oxford Comma　 Euro 2016: Underway And Plenty Has Changed　 A Look Behind the Curtain of the Fashion Blogging World　 How To Bring Your Old Blog Posts Back From The Dead　 Five Essential Photography Tips for Bloggers　 Desired Domain Name Taken? Here’s What To Do Next　 Sex Bloggers Shocked By Tumblr’s Smut Smackdown　 Can You Recover From A Facebook Rant Gone Viral?　
评论列表
添加评论