6
$\begingroup$

Has there been any attempt to systematically categorize programming puzzles?

I notice that some problems are similar to one another, or have analogous methods of solution. I would think there must be some way to categorize them, so that you could in a sense look up methods of solution if you knew what category it was in. For example, some problems reduce to finding one string in another.

The closest thing I have seen to this is in Garey and Johnson (1975) in which book there is a list of known NP-complete problems. So, if you can reduce a problem to one of the 200 or so examples they give, you know the problem is NP-complete. I have not seen a general attempt to classify all problems however, except maybe Skiena's book, The Algorithm Design Manual.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Unlikely. Categorizing basic components of puzzles can be easier (think of a list of all functions in Mathematica). $\endgroup$ – user23013 Apr 14 '15 at 17:31
  • $\begingroup$ @MartinBüttner It's borderline. Classification of algorithms exists but there's no nontrivial exhaustive classification and even recognizing known classes is undecidable. Defining which problems qualify as “programming puzzles” is more sociology than computer science. But give it a go anyway and we'll see. $\endgroup$ – Gilles 'SO- stop being evil' Apr 14 '15 at 22:44
  • $\begingroup$ seems to me any programming puzzle is part of CS, other distinctions are probably arbitrary/ artificial. and yes CS in general is the classification of programming problems. another basic classification is by algorithmic complexity. etc $\endgroup$ – vzn Apr 15 '15 at 1:45
  • $\begingroup$ Puzzles, like Sudoku (when formulated as computational problems) can be studied and categorized (some are easy, some are hard, for various definitions of "hard"). But I guess this is not what you are asking? $\endgroup$ – Juho Apr 15 '15 at 8:55
  • $\begingroup$ finding another sudoku solution has been shown to be NP-Complete (PhD thesis), i guess similar resuklts unifying various (popular) puzzles exist. One way is to find methods to transform solutions of one puzlze to soluitions of another puzzle. Eg ther rubik cube puzzle can generate solutions to the so-called einstein puzzle (i think this can be made rigorous by 1-1 correspondence between cube sides and relations) $\endgroup$ – Nikos M. Apr 15 '15 at 19:42

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.