The New Sudoku Players' Forum

[nfady]

I’m writing a short film about a person that tries to solve an impossible sudoku. This will also mean that computer programs can’t solve it either or it would take more than 2 weeks to find the results. If you can construct me one, that would be great. Since this is just a film, it ends with him creating an algorithm the crack it. He finds out that the algorithm also relates to the understanding how the universe started. If you can, state what makes a sudoku impossible, like what are the minimum visible numbers needed for one to complete a 3X3 sudoku by hand or computer. If you think I should add certain facts about sudoku please list them since if it sounds good I might use it in film. Cheers

[The Druid]

Please forgive me if I'm being pedantic here.

But isn't it a part of the definition of a Su Doku puzzle, that it CAN be solved (by the application of logic)?

The Druid

[nfady]

What I seek is a sudoku that is too hard to solve. Surely there must be a sudoku that is impossible to solve.

[Hammerite]

Any "starting grid" for a sudoku has either no solutions, a unique solution, or more than one solution. There are programs readily avalable on the internet which will tell you which is which for a given sudoku, such as the one at http://sudoku.sourceforge.net/

For any sudoku, even ones on larger grids, it is in principle possible with a finite amount of computation to determine how many solutions it has. So no, there isn't a su doku that's "impossible to solve", though there might be ones that are very difficult.

[nfady]

Cheers for that Hammerite. i did find a puzzle that has never been solved which would suit the film well. It’s called The fifteen puzzle.

[Hammerite]

Okay then. I assume that you have read up on the 15-puzzle though? Here are a couple of pages that discuss it.

http://www.geocities.com/jaapsch/puzzles/fifteen.htm

http://en.wikipedia.org/wiki/Fifteen_puzzle

I don't really know much about it, although I have heard the story of the conman who offered the $1000 prize before, in a lecture. :)

[scrose]

I’m writing a short film about a person that tries to solve an impossible sudoku. ... Since this is just a film, it ends with him creating an algorithm the crack it. He finds out that the algorithm also relates to the understanding how the universe started.

I agree with Hammerite; even the most difficult of sudoku puzzles can be solved, even if numbers are just placed at random until the correct answer is found.

Instead of creating an algorithm, perhaps your character could have some sort of innate ability to simply spot the solution of any sudoku. The character doesn't solve a puzzle per se, he/she simply knows the solution. The character would come to realize that this ability gives him/her insights into the universe itself. Just a thought...

[The Druid]

I've come across the "Fifteen" puzzle, but I wouldn't have called it a Su Doku. Out of interest, do other people regard it as such?

The Druid

[RFB]

Remember a Sudoku doesn't have to be 9x9 numeric.

You could use a 36x36 alphanumeric grid for extra complexity.
You could even encode a secrete message into the grid.
It would however still be susceptible to brute force attack.

[Pseudo Cool]

Hmmm... the plot reminds me of the movie Pi.

[dukuso]

>I’m writing a short film about a person that tries to solve an
>impossible sudoku. This will also mean that computer programs
>can’t solve it either or it would take more than 2 weeks to
>find the results. If you can construct me one, that would be
>great. Since this is just a film, it ends with him creating an
>algorithm the crack it. He finds out that the algorithm also
>relates to the understanding how the universe started. If you
>can, state what makes a sudoku impossible, like what are the
>minimum visible numbers needed for one to complete a 3X3
>sudoku by hand or computer. If you think I should add certain
>facts about sudoku please list them since if it sounds good I
>might use it in film. Cheers
>



>Remember a Sudoku doesn't have to be 9x9 numeric.
>
>You could use a 36x36 alphanumeric grid for extra complexity.
>You could even encode a secrete message into the grid.
>It would however still be susceptible to brute force attack.
>
>Pseudo Cool


yes I go with Pseudo Cool here. Just enlarge the gridsize.
We know, the problem is NP-complete so, your hero might find
out that he had finally solved that biggest actual problem of
mathematics and computer science.
I doubt that it relates to the understanding of how the universe
started.
But it's important for encryption e.g., so your hero would be hunted
and sought after by secret services all over the world.
Isn't that good enough for a moviemaker ?
Average movieviewers would be more interested in such "real world"
action anyway, rather than how the universe looked like 13 billion
years ago. Only cosmologists would like to see your movie...

BTW. do you know the Eternity Puzzle ? See
http://www.archduke.demon.co.uk/eternity/
That might match the subject of your film even better than a sudoku.
The inventor thought it were impossible to solve and did put a
million pound prize on it but then it was cracked by two British
programmers in joint work. They didn't need to solve P=NP, though ;-)


Guenter.

[The Druid]

Hello Dukuso ...

Just a note: the quotation you attribute to me (in your posting, immediately previous to this one) is not mine.

It was posted by Nfady.

The Druid

[The Druid]

Thanks for changing it

[Lc3]

The movie origonally suggeested about Sudoku need not be about solving a puzzle. Kinda reminds me of Cube and Cube 2: Hypercube, It might be some weird science-fiction-type movie. i like those.

If oyu want to make it about solving a Sudoku, how about some people are trappled inside a giant 3d alpha-numeric Sudoku and they have to solve it, but they cant see an overview of the whole grid (because they are inside), they have to crawl around the rooms to find the rooms that have a clue filled in, and make a note of it building it a picture of the grid as they go along, and the twist at the end it that it's a sudoku with 0 solutions, and they all die.

[richardginn]

A person trying to solve the biggest sudoku puzzle ever.

It can have like a 512 by 512 grid.