Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve

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

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

推荐阅读：
Essential Traits That Will Help Bloggers Work From Home Successf　 Examining the Physical and Mental Health of Writers and Bloggers　 How will Blogging Change after the Pandemic?　 Digital Relationships: 5 Tips For Building A Better Veterinary B　 The 2020 Pandemic Further Boosts Earnings and Influence of Blogg　 What to Do When Your Blog Gets Too Big for You Alone　 Minimum Numbers of Function Calls to Make Target Array　 Harddrives will fail – it is just a matter of when　 Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve 　 DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff　
评论列表
添加评论