Re:Using Simulated Annealing to Solve Logic Puzzles
by tunesmith on Sunday July 17, 2016 @11:48PM
(#12113136)
So, what does it mean exactly when they say that these kinds of problems are in the same class as Sudoku?
[ Parent
| on HN ]
Re:Using Simulated Annealing to Solve Logic Puzzles
by ChronosKey on Monday July 18, 2016 @12:18AM
(#12113203)
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.
Re:Using Simulated Annealing to Solve Logic Puzzles
by yummyfajitas on Monday July 18, 2016 @03:49AM
(#12113715)
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.
Re:Using Simulated Annealing to Solve Logic Puzzles
by waynecochran on Monday July 18, 2016 @12:39AM
(#12113243)
I've assigned this before...
https://ezekiel.encs.vancouver.wsu.edu/~cs330/archive/archiv...
Re:Using Simulated Annealing to Solve Logic Puzzles
by machinelearning on Sunday July 17, 2016 @11:59PM
(#12113161)
both problems have constraints and you solve the puzzle by finding the right configuration of data that meets the constraints.
Re:Using Simulated Annealing to Solve Logic Puzzles
by kej on Monday July 18, 2016 @11:40AM
(#12115705)
They're both examples of an exact cover problem: https://en.wikipedia.org/wiki/Exact_cover