4 ms·
So, what does it mean exactly when they say that these kinds of problems are in the same class as Sudoku?
by tunesmith 10y ago
So, what does it mean exactly when they say that these kinds of problems are in the same class as Sudoku?
- machinelearning 10y agoboth problems have constraints and you solve the puzzle by finding the right configuration of data that meets the constraints.
- ChronosKey 10y agoSimulated 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 https://en.wikipedia.org/wiki/Combinatorial_explosion) and can be expressed as a state and an associated cost/fitness function.
- yummyfajitas 10y agoThis 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.
- waynecochran 10y agoI've assigned this before... https://ezekiel.encs.vancouver.wsu.edu/~cs330/archive/archive/projects/sudoku/sa-sudoku.pdf https://ezekiel.encs.vancouver.wsu.edu/~cs330/archive/archiv...
- kej 10y agoThey're both examples of an exact cover problem: https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Exact_cover