Fork me on GitHub
#exercism
<
2020-04-18
>
jaihindhreddy17:04:05

BTW has anyone solved Dominoes?

jaihindhreddy17:04:25

On first look, it seems to be hamiltonian-cycle detection, which is NP-complete.

jaihindhreddy17:04:42

I'm baffled why it's medium and not hard.

jaihindhreddy17:04:16

Assuming it is what I think it is, Diamond and Dominoes do not belong in the same difficulty class.

hindol.adhya18:04:46

NP complete means it will take more than polynomial time to run. Maybe the algorithm is still simple.

hindol.adhya18:04:13

By the way #mathematics exists now.

jaihindhreddy20:04:57

Agreed. naive backtracking is definitely a "medium". But an efficient solution is beyond "hard" 🙂 I was thinking of somehow mapping it to exact-cover and use Knuth's DLX. Is that a decent approach?

hindol.adhya20:04:25

DLX = dancing links?