So, I enjoy games where I feel like I can recognize patterns that have some depth and complexity, that make me feel like I can develop some skill, that don't seem trivially teachable to a computer.
(EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
I'm curious what you mean by this? Sudoku is mechanically solvable, but not all sudoku puzzles feel that way, to me.
Uh, I haven't actually done sudoku in a long time, so let me talk about kakuro (https://en.wikipedia.org/wiki/Kakuro) instead. I think the feelings I have about them are similar.
So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column.
And getting a computer to implement that sort of algorithm would be challenging. (http://www.sudokuhints.com/ seems to do something like it for sudoku, to let it give you a number and tell you how you could have found that number yourself. But trying a fiendish puzzle, it's not explaining itself very well.)
(Obviously, if you don't enjoy sudoku, that's fine. I'm not trying to convince you that you should. It just feels to me like the skills I use for sudoku, aren't ones that I could trivially teach to a computer.)
This could be relevant to you: http://norvig.com/sudoku.html
> So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column.
For Sudoku puzzles generated for humans, the simplest algorithm doesn't require any backtracking or brute force at all: note for every square which numbers can still potentially work there, and at each step, select one of the squares that has only one number, fill in that number, and update all other squares accordingly. Any puzzle that that algorithm can't solve qualifies as "hard".
One of the rules I use (in that and similar puzzles) for harder puzzles: if you've determined that a pair of squares can each only have X and Y, or a trio of squares can each only have X, Y, and Z, then you know those squares contain those numbers, just not which square contains which number. So you can (for instance) eliminate X and Y from the possibilities for other squares accordingly, which may then provide more steps. Puzzles where I can recognize and apply higher-level, complex rules like that have more staying power with me.
However, it may or may not make sense to teach a computer that special-case rule. A solver may find it easier, rather than recognizing that pattern, to instead just do a search, with transposition tables and similar to avoid duplication. Providing special-case reasoning rules for specific patterns may speed up or slow down such a search, depending on how often the pattern occurs, how much brute-force it eliminates, and how much computation recognizing it requires.
I agree that there's a significant difficulty jump, when that algorithm fails to suffice, and I think it's fair to say that's the "hard" jump. But I think a lot of puzzles intended for humans are "hard", by this definition.
Teaching a computer that special-case rule might not make sense for speedy computer solving, but I think it would make sense for telling a human "here's how you could have found this number".
Figure out the possibility sets of all empty squares (that is, a set of all possible values given the current state of the table, i.e., for each square, initialize them with 1-9, then remove every value that is already contained in the same row, column, and 3x3, thus figuring out for each "this square could be 1 or 5, and nothing else"). Grab the square with the fewest possibilities; does it have only one? If so, go with it, update all related squares (by removing that value from their possibility set), recurse. Is it of possibilities > 1? Take one of the values out of the possibility set. Push a copy of the table as it stands (without that removed value) onto a stack; put in the taken value for the value of that square, update all related squares, and recurse. If you ever find a possibility space of zero (that is, a square has neither a value, nor any possible values), throw out your current table and pop off the stack, recursing upon that. If you find a possibility space of zero, and the stack is empty, the sudoku is unsolvable. Otherwise, once every square has a value, you're finished.
I feel like I had done a little pondering on ways, while coding it up, to find better heuristics for picking what number to start with, in the event the square with the minimal number of possibilities had more than one (i.e., "this square could be 1 or 5", rather than just picking one arbitrarily, would choose one based on some criteria), but I never really got around to playing with it, as nothing took more than a few tenths of a second, and that was enough to say "there, I need never care about Sudoku"
Quite a number of engineers I knew had written solvers of various sorts and rarely solved the puzzle by hand, the company accountant wrote little tally numbers in the box corners and worked by a process of elimination, and a lawyer whom I travelled with for many plane flights spent hours on them using some ad-hoc hunt and seek approach.
The paper shows that Super Mario Bros. is NP-complete, whereas Zelda games are PSPACE-complete. So Zelda is more complex than Mario (unless P=PSPACE). Is there some subjective way in which Zelda is harder than Mario, that would correspond to the difference? I guess Zelda can feel more cerebral, maybe.
More crucially the proofs in this paper rely just on the availability of certain items and level configurations that allow them to build circuits to solve 3SAT or whatever. All the other items and possible configurations in a game are irrelevant. For example they show Zelda OoT is PSPACE-complete because it has puzzles where you push around ice blocks---it is possible to construct such as puzzle where solving the puzzle is PSPACE-complete. All the other puzzles in the game, and also the configuration of real ice block puzzles in the game, do not factor into the proof, all that matters is that ice blocks exist somewhere in the game.
So these proofs might point to a potential hard core of cerebral difficulty in games but they ignore many other factors which contribute to enjoyable challengingness. I remember the ice block puzzles in Zelda OoT being pretty tricky, but they certainly don't stand out as the most memorable part of the game.
I may not actually understand what you're asking, but the obvious answers are objectives, and time limits.
In the classic Mario games there was a clear goal for every level, and you had a time limit to make it there. So you could hypothetically try every possible combination of buttons within the time limit to see which ones succeed.
Zelda has no time limit, and the goals must be discovered.
This is all putting aside the other ways in which video games can be difficult for humans but trivial for computers. Games which emphasize reflexes, timing, accuracy, communication, etc. are all orthogonal to the question of computational complexity.
A similar example, is that we know that 2-color match-Ns (and some further generalizations therefrom) such as Tic Tac Toe, Connect 4, and even wilder variants like Lumines have solved, polynomial solutions and machines can play them better than humans ever will. Humans will probably play some of these games forever, and its still a continual surprise to me how many people don't know the generalized Tic Tac Toe solution, much less that the only way to win is not to play.
Lumines will probably remain interesting to humans for a long time for those orthogonal reasons such as timing and accuracy (and music). But the interesting comparison here is to Tetris which we also generally know to be NP-hard as a direct relative to the generalized packing problem. I would think that to a human both games "feel" equally complex and yet in terms of computational complex you have easy solved algorithm in Lumines and computationally hard problem in Tetris. Lumines certainly feels at first glance to a human like an equal to the packing problem, even though it is not.
--Limited resources. Bombs, arrows, etc. ++Mario can always jump/squish, and fireballs are infinite.
--Game changes as items are acquired. A block may be liftable in phase3 of the game, but not in phase1/2. An area may drown you in phase1-4, but may be swimmable in phase5. ++Mario death is always death.
My number one reminder why Zelda would be harder is that temple where most of the walls/floors are bombable and drop you back to the bottom (except one). A computer learning without manual training of some sort would be very interesting to watch.
Zelda's main quest tends to have a lesser degree of this in practice; often it falls back on "use the item you just got in this dungeon to progress in this dungeon". And some games take it too far in the other direction, leading to the adventure game trope of "poke everything with everything else until something happens". But a good balance rewards players who remember huge parts of the world and reason about what could help them progress.