Indeed anything with constraints is usually a great use case for Prolog. I particularly like this version in ECLiPSe which is specialized on constraint programming with Prolog:
https://gist.github.com/JuanitoFatas/2227711
I haven't benchmarked it but it is pretty intuitive to read which is very important for these types of problems.
This is the best prolog solution I've seen for this kind of puzzle. Other solutions all had to define a bunch of primitives for neighborhood constraints.
The article mentions the problem of "local minimums". The author suggests occasionally accepting worse solutions, in order to escape from such. "The hope here is that by following this worse solution, we can eventually get to the global minimum." This is good but one may wish to take it further.
I once messed with something called "metropolis coupling", where you run multiple threads in parallel, with different thresholds for how often they accept worse solutions, i.e. one thread is "cold", one is slightly "hotter", and so on. If a hot thread's current solution is better than the solution of the neighbouring colder thread, the solutions are swapped. In this way the coldest thread (which is the one we're paying attention to) gets pulled out of the local minimum.
As I say, I messed with this once and it did seem to help. It seems to have been developed for inference in evolutionary phylogenetics, and is perhaps a bit obscure?
This has the advantage of working as a sampling strategy, not just an optimization strategy. It is useful when the mass of your distribution is concentrated in a region that may be hard to find with a random walk.
That's actually pretty brilliant. I haven't ever heard of metropolis coupling before, but I can see how it would break the algo out of a local minimum.
Also, klaatu barada nikto.
Nice. I've used Simulated Annealing to achieve good results in problems were the solution space was too large for constraint programming, but for this specific sort of problems I've had good experience using constraint programming frameworks like GECODE or choco
A lot of people here mention Prolog as another tool to solve this problem. I wonder if there's a natural way to combine constraint solving with simulated annealing.
If you like this sort of thing, I wrote some code a couple of years ago to generate and solve logical deduction problems, such as the "Cheryl's Birthday" brainteaser:
The code isn't very clean (it was written hastily as part of a hack days project at work) but the notebook walks you through it, so even if you're not familiar with Python, you'll get a sense of the technique.
I've used simulated annealing to make constraint solvers more efficient. The nice thing about constraint solvers and simulated annealing as demonstrated is that it's fairly straight forward to adapt the algorithm to your specific problem and data in order to get the best performance.
Simulated annealing and similar techniques such as Tabu Search are good for problems that have large search spaces due to combinatorial explosion (https://en.wikipedia.org/wiki/Combinatorial_explosion) and can be expressed as a state and an associated cost/fitness function.
This is true provided your cost function is "continuous" w.r.t. distance. Roughly what this means is that if you make a small change - e.g. one edit in this example - then your cost function shouldn't change a lot.
If you don't have some form of continuity condition you are actually just doing random search.
Constraint Satisfaction Problems can be modeled as Hopfield-type neural networks, such as Boltzmann machines (RBMs of deep learning are a variant) which can be tuned using simulated annealing.
There was plenty of research on this around 1985-1995 (the "second coming" of neural networks), but it died out with the hype because it was never an actually practical way to solve CSPs. Given the recent innovations in deep learning, it should eventually pick up again, to enable deep learners to solve constraint satisfaction subproblems within the same integrated architecture.
Really interesting, I wrote a logic puzzle solver in Prolog a long time ago while I was in uni, I just created a repo for anyone who wants to check it out. Unfortunately the documentation and comments are all in Spanish...
Tweaking 't' here seems to be similar to tweaking the learning rate in gradient descent. But in gradient descent you assume the problem is convex.
Is there any way to tell whether this logic problem (or any other) is convex? Is it possible that the correct solution's 5-away neighbours all have very high costs (like 9+)? What prevents you from doing worse that brute force?
What if we change the cost function to something that returns a number which has a direct correlation with the maximum number of attributes that matched? Would solving the problem be any easier or we would still leave the possibility of getting stuck in local optimums just like the one described in the post?
I think in theory it is possible by unary encoding attributes of the five houses then defining the appropriate weights according to the constraints.
In practice it might not be possible to map the resulting graph on the D-Wave's architecture, I can't find any good documentation on the D-Wave though.
