## GENERAL SODOKU SOLUTION

Everything about Sudoku that doesn't fit in one of the other sections

### GENERAL SODOKU SOLUTION

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?
Bigtone53

Posts: 413
Joined: 19 September 2005

### Re: GENERAL SODOKU SOLUTION

Bigtone53 wrote: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
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

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.
Red Ed

Posts: 633
Joined: 06 June 2005

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

Posts: 2698
Joined: 17 July 2005

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 AlgorithmThe 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 .

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

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...
Some do, some teach, the rest look it up.

StrmCkr

Posts: 647
Joined: 05 September 2006

gsf wrote:
Bigtone53 wrote: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?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs

Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

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...
Some do, some teach, the rest look it up.

StrmCkr

Posts: 647
Joined: 05 September 2006

Red Ed

Posts: 633
Joined: 06 June 2005

999_Springs wrote: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.

udosuk wrote: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.....

DonM wrote: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.

Luke451 wrote: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.
Allan Barker

Posts: 266
Joined: 20 February 2008

Allan Barker wrote:
999_Springs wrote: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.
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs

Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

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

Pat

Posts: 3438
Joined: 18 July 2005

The article wrote: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.84.7|6..|...---+---+---...|..5|...52.|...|.47...|7..|...---+---+---...|..3|5.43.6|5..|..1.9.|.7.|.6.`

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

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

Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs

Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

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

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

Posts: 3438
Joined: 18 July 2005

999_Springs wrote:
The article wrote: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)and has exactly one answer

Pat

Posts: 3438
Joined: 18 July 2005