Brute-forcing a seemingly simple number puzzle 61 points by ScottWRobinson 10 days ago | hide | past | web | favorite | 24 comments

 That's a very nice challenge!Here is a Prolog formulation of the task:`````` :- use_module(library(clpfd)). n_tour(N, Vs) :- L #= N*N, length(Vs0, L), successors(Vs0, N, 1), append(Vs0, [_], Vs), % last element is for open tours circuit(Vs). successors([], _, _). successors([V|Vs], N, K0) :- findall(Num, n_k_next(N, K0, Num), [Next|Nexts]), foldl(num_to_dom, Nexts, Next, Dom), Dummy #= N*N + 1, % last element is for open tours V in Dom \/ Dummy, K1 #= K0 + 1, successors(Vs, N, K1). num_to_dom(N, D0, D0\/N). n_x_y_k(N, X, Y, K) :- [X,Y] ins 1..N, K #= N*(Y-1) + X. n_k_next(N, K, Next) :- n_x_y_k(N, X0, Y0, K), ( [DX,DY] ins -2 \/ 2 % 2 diagonally ; [DX,DY] ins -3 \/ 0 \/ 3, % 3 vertically or horizontally abs(DX) + abs(DY) #= 3 ), [X,Y] ins 1..N, X #= X0 + DX, Y #= Y0 + DY, n_x_y_k(N, X, Y, Next), label([DX,DY]). `````` The key element of this solution is the CPL(FD) constraint circuit/1, which describes a Hamiltonian circuit. It uses a list of finite domain variables to represent solutions: Each element of the list is an integer, denoting the position of the successor in the list. For example, a list with 3 elements admits precisely 2 Hamiltonian circuits, which we can find via search:`````` ?- Vs = [_,_,_], circuit(Vs), label(Vs). Vs = [2, 3, 1] ; Vs = [3, 1, 2]. `````` The rest of the code sets up the domains of the involved variables to constrain them to admissible moves. A dummy element is used to allow open tours. The predicate n_x_y_k/4 relates X/Y coordinates to list indices. You can easily adapt this to other variants of the puzzle (e.g., knight's tour) by changing n_k_next/3.A major attraction of a declarative solution is that it can be used in all directions: We can use the exact same code to test, generate, and to complete solutions. For example, we can use the Prolog program to show that the 5×5 solution that is shown in the article is uniquely defined if we fix just 4 elements in the first row:`````` ?- n_tour(5, Vs), last(Vs, 1), Vs = [_,_,18,19,26|_], label(Vs). Vs = [4, 5, 18, 19, 26, 21, 22, 20, 24|...] ; false. `````` A few additional definitions let us print solutions in a more readable form:`````` :- set_prolog_flag(double_quotes, chars). print_tour(Vs0) :- reverse(Vs0, [First|Vs1]), reverse(Vs1, Vs), length(Vs, L), L #= N*N, N #> 0, length(Ts, N), tour_enumeration(Vs, N, First, Es), phrase(format_string(Ts, 0, 4), Fs), maplist(format(Fs), Es). format_(Fs, Args, Xs0, Xs) :- format(chars(Xs0,Xs), Fs, Args). format_string([], _, _) --> "\n". format_string([_|Rest], N0, I) --> { N #= N0 + I }, % I is textual width of square "~t~w~", call(format_("~w|", [N])), format_string(Rest, N, I). tour_enumeration(Vs, N, First, Es) :- length(Es, N), maplist(same_length(Es), Es), append(Es, Ls), foldl(vs_enumeration(Vs, Ls), Vs, First-1, _). vs_enumeration(Vs, Ls, _, V0-E0, V-E) :- E #= E0 + 1, nth1(V0, Ls, E0), nth1(V0, Vs, V). `````` For example, here is the 5×5 solution from the article again:`````` ?- n_tour(5, Vs), last(Vs, 1), Vs = [_,_,18,19,26|_], label(Vs), print_tour(Vs). 1 24 14 2 25 16 21 5 8 20 13 10 18 23 11 4 7 15 3 6 17 22 12 9 19 `````` And here is a query that solves the 10×10 instance:`````` ?- n_tour(10, Vs), time(label(Vs)), print_tour(Vs). `````` Yielding:`````` % 21,852,020 inferences, 3.323 CPU in 3.349 seconds (99% CPU, 6575193 Lips) 63 58 53 64 59 54 65 60 55 66 21 16 11 22 17 12 23 18 13 24 52 49 62 57 50 61 56 67 28 85 10 7 20 15 8 19 14 25 82 72 47 44 51 48 45 68 29 86 69 30 5 91 9 6 92 26 83 73 27 84 42 96 46 43 97 87 70 31 81 71 36 39 93 35 38 74 34 78 75 33 4 90 98 3 89 99 2 88 100 1 41 95 37 40 94 79 76 32 80 77 `````` Since the search for solutions is decoupled from the problem description, we can easily try different search strategies. For example, using the strategy "ff" (first fail) measurably reduces the running time in this case:`````` ?- n_tour(10, Vs), time(labeling([ff], Vs)), print_tour(Vs). % 8,317,298 inferences, 1.344 CPU in 1.355 seconds (99% CPU, 6190382 Lips) 89 84 49 90 85 48 23 86 47 22 81 63 13 82 64 61 68 65 60 69 50 91 88 51 92 87 46 43 24 36 14 83 80 62 12 66 59 70 67 21 27 52 93 26 53 44 25 37 45 42 79 57 15 8 58 71 11 40 72 35 94 31 54 95 32 38 19 33 75 20 28 7 98 29 6 9 73 3 10 41 78 56 16 77 55 17 76 39 18 34 97 30 5 96 99 4 1 100 74 2 `````` Using CLP(FD) constraints typically yields much faster solutions than using brute-force search, since constraints propagate information before and also during the search to prune the search tree. Especially for more complex tasks, the computational cost of constraint propagation is typically negligible in comparison to traversing the entire search tree.However, if you want, you can also easily obtain a brute-force variation from this program, by posting the constraints after the search. This turns the whole program into a "generate and test" approach, which is typically much slower than constraint-based search.
 I tried the same with the knight’s tour [0] and add similar problems. You don’t really guess how many iterations it will need when you start coding it, and then realize why they needed such big computers to beat a human at chess !
 There's no mention of the word 'search' within the blog post, but this is classic search algorithm: depth-first search (recursing depth first, with no heuristic).
 > Therefore we could use a two-dimensional byte[][] array. However, due to (most likely premature) optimization, I chose one-dimensional, unrolled arrayDoes the Java compiler optimize this to be equivalent?As an aside, I really hate problems like this that seem like they have a nice solution but then you end up brute forcing them. A family friend had one recently that she tore her hair out over for at least a week before finally accepting that there was no “simple” solution after confirmation from no fewer than five other people that they thought the problem was hard.
 > Does the Java compiler optimize this to be equivalent?No, it can't. `byte[][]` is an array of arrays, and that fact is user-visible because you can access any of the individual arrays, pass it to other functions, etc.
 But you can do this is C, which has flat arrays. To “access” an individual array just grab the base address+array sizeelement sizeindex.
 >A family friend had one recently that she tore her hair out over for at least a week before finally accepting that there was no “simple” solution after confirmation from no fewer than five other people that they thought the problem was hard.Is this something you can share? I'm curious what it was.
 Sure, it was the problem listed on this page: https://www.rain.org/~mkummel/stumpers/22sep00a.html. Basically it requires at least a bit of guess and checking, which made her feel as if she was doing it wrong since it seems like there would be a “formula” to do these that you could find if you did some algebra or something. I ended up writing a C++ program (yay, std::next_permutation) to brute force solutions but it could not find a pattern, especially if you try to increase the number of circles and look for patterns there.
 This is cool! I attempted something similar using JavaScript and brute force wouldn’t work for me very well (at least the way i implemented it). I guess concurrency could be used to explore different paths in parallel but the problem would need to be sent to the server
 > The fact that Board is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead end, we must slowly go back, trying to take all other possible moves. Mutating Board would require cleaning it up. Immutable Board can be simply thrown away once it's no longer needed. Also immutability enables concurrent exploration (soon to come).Someone correct me if I'm wrong, but I believe backtracking actually requires a mutable array and would be faster (since you wouldn't have to build 100x100 arrays all the time: you could just build the 100x100 array one time and mutate it.)
 Backtracking doesn't require a mutable anything, per se. Just the ability to get back to where you were.Now, it can be somewhat easily reasoned that a mutable board can more quickly let you go back to previous settings, since you could potentially lose the GC steps of the immutable version.Of course, the immutable is more easily reasoned for parallelizing, since you can just throw paths to different workers without them stepping on each other.So, tradeoffs.
 My argument is that the version with a single mutable board would be 100x100=10000 times faster, since you won't need to make a new array for every move
 Oh, in that, I agree. I would hope a more friendly datastructure would be used for the immutable version. Data sharing should be possible.
 As one commenter on the post points out, there's a really simple optimization that can be done to make this much faster and avoid local minima: check for dead ends ahead of time.Example: I'm generating 5 new boards based on this one to check. In 3 of them, there is now a spot that cannot ever be reached. But the board is only half completed and from the spot I jumped to, I can still reach other places.By trimming these options from the search at the moment of their conception, one can greatly reduce their search time.
 This, so much.I remember writing a solver for a different game, and already had a dead end check in it, but with increasing board size it took half an hour to find a solution. Then I added another check for a different dead end condition. This actually required quite a lot of additional work, more than doubling the time spent for evaluating each board state. But it brought down the time from 30 minutes to a fraction of a second!
 Spend twice as long to prevent spending exponentially more time- usually worth it.
 Agreed, good call.Another possible optimisation might be to order the generated next-moves, so that the 'better' options are returned earlier in the list. Although I'm not sure what 'better' here means, exactly. But, through experimentation, one may find that visiting boards with more available options first, or vice versa(?), could produce a quicker route to the goal?(Making it an 'informed' search, a kind of greedy/best-first depth-first search)
 I posted it top-level, but I'll post here, as well. Look into Knuth's discussion of Exact Cover problems. He has a very elegant algorithm for this style of problem that, I believe, is quite hard to beat. (Would love for someone to prove me wrong.)
 Sure, agreed. But I guess it depends on whether one wishes to stick with a search algorithm, and improve upon it, or, whether one wants to implement a completely different algorithm instead.
 The other algorithm is still a search one. Just really clever in how it searches.
 Really fun problem. Pretty sure this would be easy to encode as an exact cover problem, and then just use Knuth's dancing links. Just got into the office, so probably not going to have time to try today, but will try and make an attempt at it this evening. (After I do the advent problem for today, of course. :) )The prolog version already posted looks fun, too. Curious if anyone has already done this as an exact cover.
 Good read. A similar scenario that always boggles my mind is password complexity. It always seems so simple until you work out you need till the end of the time to crack it!
 It depends on the level of password complexity. A standard 8 letter password with recommended complexity would generate a search space of a few hundred trillion passwords. That would take a very long time, but certainly, not forever. Now GUIDs will give you a run for your money.
 I remember doing this a lot in elementary school. I definitely never finished it, so it's nice to hear that it's at least possible.

Search: