"This app should really be called "20 different brain benders packed into one tight, little package," but developers pick the whole brevity thing for App Store names. PuzzleManiak is chock full of puzzles that will make you wrinkle your brow in frustration and keep you coming back for more. It's ideal for long lines at the DMV, the waiting room at the dentist, or pretty much whenever you need to kill some time.
The puzzles range from games you might be familiar with, like Sudoku, to ones that make particularly good use of the touchscreen, like Untangle. The latter features several points connected by lines; you have to untangle the lines by rearranging them so they don't cross. It starts out fairly easy, but turns into a frustratingly difficult--albeit fun--crisscrossing cat's cradle with each new level."