The New Sudoku Players' Forum

[Bigtone53]

I heard on the radio today that a US mathematician is going to publish next week in some US mathematical publication a simple formula which can be used to solve ALL sudokus. Anyone know anything more?

[gsf]

I heard on the radio today that a US mathematician is going to publish next week in some US mathematical publication a simple formula which can be used to solve ALL sudokus. Anyone know anything more?

http://www.ams.org/notices/200904/rtx090400460p.pdf

[Red Ed]

Oh my God, that's moronic. It's a just backtracking algorithm. On hidden tuples / fish or something. I couldn't be bothered to read further.

[udosuk]

Bear in mind April 1st is coming around so we'll be bound to see more "discoveries" like this during the next couple weeks.

[Luke]

From the article:

Code: Select all

In the next section we display and solve a Sudoku puzzle whose solution requires the use of random choice: The Mepham Diabolical Sudoku Puzzle

I was unaware there was a "Mepham Diabolical" that required guessing.

Code: Select all

Since there are no more undiscovered preemptive sets at this point, we choose the cell in box 1, ... as the vertex of the search path that we will generate on the fly. We then randomly choose one of the two numbers [4, 7] ... by flipping a coin. The choice was 4. ...The red path in Figure 13 plays out quickly and does not, through crossouts, generate any new preemptive subsets, so we begin a green path by choosing randomly from the set [4, 8] in c (7, 8). The choice was 8. ... The green path ....leads to the solution of Mepham’s D displayed in Figure 13.

So, you guessed 4, and it didn't play out. You guessed 8, and it did. I'm not a mathematician, but does algorithm construction normally involve coin flips??

We then move on to the legendary puzzle, "Shortz 301" (remember him?), to finally reach a conclusion:

Code: Select all

Summary: Statement of the Algorithm
The steps in the algorithm for solving Sudoku puzzles are:
(1) Find all forced numbers in the puzzle.
(2) Mark up the puzzle.
(3) Search iteratively for preemptive sets in all rows, columns, and boxes—taking appropriate crossout action as each new preemptive set is discovered—until
(4) either
(a) a solution is found or
(b) a random choice must be made for continuation.
(5) If 4(a), then end; if 4(b), then go to step 3.

I think they're on to something. One CAN solve any puzzle with the proper guesswork. I think udosuk is onto something, too .

[StrmCkr]

plus if you notice that he claims to have built an algroithum as well but doesnt desplay it at all in the section that says it does?? instead it avoids the topic and moves around it with quotes to otehr sources...

[999_Springs]

I heard on the radio today that a US mathematician is going to publish next week in some US mathematical publication a simple formula which can be used to solve ALL sudokus. Anyone know anything more?

http://www.ams.org/notices/200904/rtx090400460p.pdf

I can't view the link. I guess it's not worth reading, however, but could someone provide me with a text file or something so that I can see how stupid these people are?

[StrmCkr]

the first few lines sum the entire thing up.

it states that sudokus are easily solved with a back tracking tree algorithums.

and that every player mearly has to sit down and guess and test and do manual sub set tree searches for a invalid state, to eventually solve a puzzle.

thats is the first paragaph in a nut shell.


.....and i cant get it to load past the first page now..??
odd...

[Red Ed]

I had the same download problems with Firefox, but no problem with Opera.

[Allan Barker]

I can't view the link. I guess it's not worth reading, however, but could someone provide me with a text file or something so that I can see how stupid these people are?

I put a copy of the paper here CJ Crook paper, so you can see it however, its not on my website.

Bear in mind April 1st is coming around so we'll be bound to see more "discoveries" like this during the next couple weeks

After reading the paper, it is difficult to dismiss the April 1 connection however, after reading DonM's comment below and Crook's reference to receiving one of his first Sudoku books on his 70th birthday in 2007.....

Totally digressing for a moment. Has anyone noticed how bizarre the situation is at the moment when it comes to a person trying to learn how to solve Sudoku using basic & advanced methods? I went into Borders (a book store chain for those not in the U.S.) the other day and just for the heckuvit checked out the Sudoku section. There were easily over 100 Sudoku books with all sorts of names. While right next to them were books on Chess, Bridge with indepth descriptions on how to play them, not one of the Sudoku books had anything more than 1-3 pages on very rudimentary instructions on how to solve a sudoku puzzle (eg. pretty much limited to cross-hatching, perhaps basic naked pairs and the like.) and most of them had nothing. If you were lucky you might come across Paul Stephen's Mastering Sudoku which is probably the best book available for basic methods now that Andrew Stuart's 'Logic of Sudoku' is sadly unavailable now. Otherwise there's virtually nothing that would teach someone how to logically solve a puzzle. Which means that any person trying to get to the level of those on this forum have got a lot of hard-core sleuthing to do.

...it seems more likely that the retired Crook spent time wondering around a Border's bookstore in Winthrop, North Carolina where he had been a professor of mathematics. Applying his life long skills, he discovered naked multiples. From this view, DonM's words would seem to ring true. BTW, he published at least one paper with I. J. Good about 1980, "C. Crook, I. Good" ?.

Is it time for a large multi-volume compendium on all the methods to fill Borders' shelves? I'll do the graphics.

So, you guessed 4, and it didn't play out. You guessed 8, and it did. I'm not a mathematician, but does algorithm construction normally involve coin flips??

Yes. A rather substantial area of computaional math and physics is based on what's called the Monte-Carlo approach. People familiar with Monte-Carlo but not Sudoku may have a different opinion about coin-flips.

Having said all that, now imagine any of the experts around here sending such a paper to the AMS.

[999_Springs]

I can't view the link. I guess it's not worth reading, however, but could someone provide me with a text file or something so that I can see how stupid these people are?

I put a copy of the paper here CJ Crook paper, so you can see it however, its not on my website.

It's just a description about subsets and guessing. It certainly isn't a "simple formula" that can solve puzzles. Anyway, I had never heard of people who encourage guessing on a puzzle rated SE 4.4, or people who, while manually solving, put pencilmarks at the bottom of cells instead of the top.

This is just ridiculously dumb.

[Pat]

I had never heard of people who, while manually solving, put pencilmarks at the bottom of cells instead of the top.

[999_Springs]

Thomas Snyder of the USA, who won the 2007 World Sudoku Championship in Prague, Czech Republic, solved a puzzle that has exactly two solutions to win the championship. The puzzle Snyder solved is

Code: Select all

.5.|.2.|.3.
2..|..1|7.8
4.7|6..|...
---+---+---
...|..5|...
52.|...|.47
...|7..|...
---+---+---
...|..3|5.4
3.6|5..|..1
.9.|.7.|.6.

TWO solutions!? TWO!!??!? *Lifts eyes to ceiling* These people must have no idea how to count.

I had never heard of people who, while manually solving, put pencilmarks at the bottom of cells instead of the top.

Your point being...?

[Pat]

I had never heard of people who, while manually solving, put pencilmarks at the bottom of cells instead of the top.

Your point being...?

just what i said
i.e. you left me speechless

okay i might've tried to explain
-- would this be clearer?

yes, the rules of SuDoku do clearly specify that "pencilmarks" may only appear at the top of each cell

[Pat]

Thomas Snyder of the USA, who won the 2007 World Sudoku Championship in Prague, Czech Republic, solved a puzzle that has exactly two solutions to win the championship. The puzzle Snyder solved is

Code: Select all

 . 5 . | . 2 . | . 3 .
 2 . . | . . 1 | 7 . 8
 4 . 7 | 6 . . | . . .
-------+-------+------
 . . . | . . 5 | . . .
 5 2 . | . . . | . 4 7
 . . . | 7 . . | . . .
-------+-------+------
 . . . | . . 3 | 5 . 4
 3 . 6 | 5 . . | . . 1
 . 9 . | . 7 . | . 6 .



TWO solutions!? TWO!!??!? *Lifts eyes to ceiling* These people must have no idea how to count.

yes, they found only 2 (of the 30)
where the puzzle is considered a plain SuDoku

their phrasing also suggests that the championship had a puzzle with more than one answer --
where in fact this is a Jigsaw (not a plain SuDoku)
http://entertainment.timesonline.co.uk/tol/arts_and_entertainment/games_and_puzzles/sudoku/article1599976.ece
http://wpc.puzzles.com/sudoku/jigsawFinals.htm


and has exactly one answer