Flow Free is a popular mobile phone game where the problem is to connect the pieces . Wikipedia suggests this is equivalent to Number Link puzzles and as such is NP-complete.

Supppse we wanted to write a solver for this kind of puzzle. This could be considered a type of integer programming problem, where each square is indexed by a variable. So if the puzzle is $N \times N$ there are $N^2$ variables and a number of restrictions.

Somehow we could encode the restriction there's a single path connecting the dots on each vertex. And that every vertex must be covered.

Is this equivalent to one of the more standard CS problems such as set-cover or SAT?

enter image description here

Related: Are "Flow Free" puzzles NP-hard?

  • $\begingroup$ What do you mean by "equivalent"? Are you asking for a reduction from e.g. SAT or a (natural) reduction to e.g. SAT? Or do you really want both? $\endgroup$ – Peter Taylor Jun 27 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.