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 !
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.
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 array
Does 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.
>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
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.
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!
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.
:- 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:
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.
> 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.
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
I know it's been a few days, but just for the sake of completeness I have to add them...
After doing a web search for similar puzzles I discovered a similar game named Hopido [1]. There is also a very nice page over at Rosettacode [2] where sample codes are given. It's easy to edit the source code and adjust the matrix size to the desired dimensions. On a personal side note, I might create something similar for Android as my first Unity project :-)
25 comments
[ 5.6 ms ] story [ 63.3 ms ] thread[0]https://jean-marc.salis.fr/en/knights-tour--part-1/
https://en.wikipedia.org/wiki/Depth-first_search
Does 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.
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.
Is this something you can share? I'm curious what it was.
http://rafalbuch.com/cracking-the-mega-maze-using-breadth-fi...
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.
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!
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)
Here is a Prolog formulation of the task:
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: 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:
A few additional definitions let us print solutions in a more readable form: For example, here is the 5×5 solution from the article again: And here is a query that solves the 10×10 instance:The prolog version already posted looks fun, too. Curious if anyone has already done this as an exact cover.
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.)
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.
[1] https://gamesandinnovation.com/2010/02/10/hopido-design-post... [2] https://rosettacode.org/wiki/Solve_a_Hopido_puzzle