World’s hardest sudoku puzzle?


This Sudoku puzzle published in The Telegraph claims to be the world’s hardest puzzle, though I am not exactly sure how one measures that.

The Everest of numerical games was published by Arto Inkala, a Finnish mathematician, on his website and is specifically designed to be unsolvable to all but the sharpest minds.

On the difficulty scale by which most sudoku grids are graded, with one star signifying the simplist and five stars the hardest, this puzzle would score an eleven, he explained.

Instead of being able to spot where a number goes based solely on the boxes that have already been filled in, most moves will face you with two or more spaces where a number could fit.

Only one of these is correct, but to find it you must examine all possible options for your next move and perhaps the move after that, continuing in the same vein until all but one potential route results in a dead end.

Mr Inkala said the most difficult parts of the grid require you to think ten moves ahead, exploring a series of permutations at each stage in order to eliminate all routes other than the right one.

All I can say is that it looks really tough and completely defeated me. It is clearly not to be attempted by the faint-hearted.

Comments

  1. gustavstieglitz says

    You don’t have use brute force – computers turn out to be pretty good at handling deductions. Solving a million-variable equation takes my machine a couple of minutes, so working with a Soduku should be about as hard for a PC as filling in a captcha is for us.

  2. Stevarious says

    The problem with this puzzle is that (at least for me) there are two kinds of Sodoku puzzle – the puzzle type and the ‘guessing game’ type.

    The puzzle type is the kind where I can use logic to determine ‘this has to be three, and this has to be four, and this could be five or seven or nine, but since these two have to be either five or seven, than we know this guy over here can’t be either and has to be nine.’ These I enjoy quite a bit (though there is only so many ‘tricks’ that can be done along those lines which is why I don’t really do Sudoku puzzles any more).

    Then there’s the other kind, the guessing game kind, where there’s no way to ‘know’ which square is which so it boils down to a big guessing game. ‘Well, what if this square was a three? Then this would have to be a five, and this a seven, and this a nine, and this another five, wait that doesn’t work, hmmm…’ These puzzles aren’t really puzzles at all (IMHO) because I’m not solving the puzzle, I’m just playing a really complicated game of hangman, where the end of the game comes when I’ve either guessed correctly (could be the 20th try or the 1st) or I run out of patience.

    I ran out of patience with this one the moment I discovered that not a single square could be filled without playing hangman with the numbers.

    (Apologies to anyone who actually enjoys this game. It is not my intention to ruin your fun.)

  3. Randy Shane says

    Marcus Ranum:

    I wonder how long it would take a computer to brute-force it.

    Less than a second on my tablet.

  4. wholething says

    I wrote a JavaScript program that could always solve the puzzles in the local paper but usually needed a little help with the USA Today puzzle. It couldn’t get the first number with this one. It used some of my own simpler strategies but it wasn’t optimized for complex strategies.

  5. Mano Singham says

    I had thought that one of the rules for creating genuine sudoku puzzles was that it had to be of the first type you describe, that it be soluble by purely deductive means. This one, as you say, seems to be of the ‘guess-and-check’ type and thus outside the bounds.

  6. 'Tis Himself says

    Like Stevarious I enjoy the logic kind of puzzles and hate the guessing type. I worked at the “hardest puzzle” for 15 minutes and couldn’t figure out the first number.

    If at first you don’t succeed, give up, why make a fool of yourself? -Anon

  7. says

    A complex strategy is more elegant but far more complicated to write the algorithm for. Since the sudoku grid is the same 9×9 of 3x3s, the number of possible combinations is extremely limited in terms of modern computer hardware. This makes a brute force solver more than feasible (downright trivial, to be honest).

    Of course, if you like the challenge of writing a more human-like deductive approach for your computer to use, by all means.

  8. mcbender says

    As far as I can tell, the “guess and check” and deductive reasoning ones are actually isomorphic – it’s just that the “guess and check” puzzles require you to store more information in your mental RAM than is realistically feasible. As long as the puzzle is written correctly to imply a unique solution, it is technically true that there is a path of deductive logic which will imply a value for at least one of the empty squares (which may imply further values and so on until the grid is filled), even if it is difficult to represent that mentally.

    I’m not particularly interested in traversing search trees in my head (nor on paper), so I’m not terribly interested in attempting this one (although I may yet do so).

    Incidentally, I don’t know how the computerised solvers work – I can imagine an approach similar to Boolean satisfiability solvers using a depth-first search and constraint propagation, which would work but I expect would be horribly inefficient…

  9. says

    I don’t think there is much correspondence between how difficult a Sudoku is for humans, and how difficult it is for computers.

    The easiest Sudoku puzzles (for humans) are designed so that each number can be solved in turn. More difficult puzzles require the solver to consider contingencies, whereby the fact that a given cell can have a limited range of numbers has to be used. Puzzles are made more and more difficult by increasing the range of possible numbers in these contingencies, and the range of cells they involve.

    This is difficult for humans, as juggling a large set of interdependent numbers is mentally challenging. Computers, however, can perfectly recall large sets of numbers, and so a brute force solver won’t have any difficulty.

  10. Mano Singham says

    I think you are right in your statement about isomorphism and that the guess-and-check method is the deductive method that is too difficult to do mentally.

  11. Miroslav Balac says

    Logic won supercomputer

    Using my Method I solved: “The world hardest Sudoku puzzle” in 58 minutes without guesswork. Before, I also solved AI Escargot in the same way and wrote about it to his publisher. The result is they offered that Dr. Inkala construct several most difficult puzzle for my book ( I have emails). I agree that the hardest one is not yet discovered.

    Miroslav Balac, author books: “Sudoku Don’t Do That” published
    “Mystery of Sudoku” not yet published

Trackbacks

Leave a Reply

Your email address will not be published. Required fields are marked *