3 ms·

What makes a difficult sudoku problem difficult? Is it possible that a brilliant, experienced solver would find the right "tricks" to solve the puzzle? Or is t

What makes a difficult sudoku problem difficult? Is it possible that a brilliant, experienced solver would find the right "tricks" to solve the puzzle? Or is the sudoku such that it can be only solved by some flavor of exhaustive search on the space of potential solutions?

jbri 13y ago
The difference between an "easy" and a "hard" sudoku (and other problems of that ilk) is essentially how many steps ahead you need to think in order to derive useful information. An "easy" sudoku is one solvable by mechanical application of the rules of the game - if there's only number that can be placed in a cell, fill it in, and similarly if there's only one cell in a given row, column, or box that a given number fits in, fill it in there. As things get harder, other logical steps are required. For example, if there are two cells in a line, and both of them can only accept the numbers 5 and 9, you can conclusively say that no other cell in that line can be a 5 or a 9. That's looking one step ahead, and (depending on how often it's necessary) makes for a medium-difficulty puzzle. As you move up difficulties things get more complex, and thinking several steps ahead becomes necessary if you want to make meaningful headway. -- I would expect the "hardest" sudoku would not be one that's only solvable by brute force - that's a rather uninteresting puzzle, for a start. Instead, the hardest (in my opinion) would be one that requires making the trickiest insights in order to make headway without resorting to guess-and-check style exhaustive search.
pliny 13y ago
The more backtracking you have to do, the harder it is for a human to solve / more likely that your weak flesh brain will encounter a stack overflow.
- GhotiFish 13y ago
  I got the sense alot of people consider a sudoku puzzle unfair if there isn't a discrete set of logical steps you can take to solve it, sans guessing. After all, if you're looking for a hard Sudoku to solve in that vein, just look at the minimally unique Sudokus. Those required a metric ton of back tracking.
Someone 13y ago
According to http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html http://www.nature.com/srep/2012/121011/srep00725/full/srep00..., there is a nice correlation between perceived difficulty and a nice, objectively computable number. So, a sudoku seems to be extremely hard iff η > 3. And no, you don't need to do an exhaustive search.
GhotiFish 13y ago
Difficulty rating systems I've seen essentially take a sudoku and then solve it starting with easy human steps, and working their way down to more complicated logical deductions. Chokepoints that can only be found in a large set, or having to solve the puzzle with a complicated deduction like an X-wing or Y-wing, raise the number. With guessing as a fully last resort.

jbri 13y ago

The difference between an "easy" and a "hard" sudoku (and other problems of that ilk) is essentially how many steps ahead you need to think in order to derive useful information. An "easy" sudoku is one solvable by mechanical application of the rules of the game - if there's only number that can be placed in a cell, fill it in, and similarly if there's only one cell in a given row, column, or box that a given number fits in, fill it in there. As things get harder, other logical steps are required. For example, if there are two cells in a line, and both of them can only accept the numbers 5 and 9, you can conclusively say that no other cell in that line can be a 5 or a 9. That's looking one step ahead, and (depending on how often it's necessary) makes for a medium-difficulty puzzle. As you move up difficulties things get more complex, and thinking several steps ahead becomes necessary if you want to make meaningful headway. -- I would expect the "hardest" sudoku would not be one that's only solvable by brute force - that's a rather uninteresting puzzle, for a start. Instead, the hardest (in my opinion) would be one that requires making the trickiest insights in order to make headway without resorting to guess-and-check style exhaustive search.

pliny 13y ago

The more backtracking you have to do, the harder it is for a human to solve / more likely that your weak flesh brain will encounter a stack overflow.

GhotiFish 13y ago
I got the sense alot of people consider a sudoku puzzle unfair if there isn't a discrete set of logical steps you can take to solve it, sans guessing. After all, if you're looking for a hard Sudoku to solve in that vein, just look at the minimally unique Sudokus. Those required a metric ton of back tracking.

Someone 13y ago

According to http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html http://www.nature.com/srep/2012/121011/srep00725/full/srep00..., there is a nice correlation between perceived difficulty and a nice, objectively computable number. So, a sudoku seems to be extremely hard iff η > 3. And no, you don't need to do an exhaustive search.

GhotiFish 13y ago

Difficulty rating systems I've seen essentially take a sudoku and then solve it starting with easy human steps, and working their way down to more complicated logical deductions. Chokepoints that can only be found in a large set, or having to solve the puzzle with a complicated deduction like an X-wing or Y-wing, raise the number. With guessing as a fully last resort.