GENERAL SODOKU SOLUTION

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

GENERAL SODOKU SOLUTION

Postby Bigtone53 » Sun Mar 22, 2009 12:09 am

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

Postby gsf » Sun Mar 22, 2009 2:14 am

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

Postby Red Ed » Sun Mar 22, 2009 3:21 am

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

Postby udosuk » Sun Mar 22, 2009 6:57 am

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

Postby Luke » Sun Mar 22, 2009 10:28 am

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 .
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby StrmCkr » Sun Mar 22, 2009 11:22 am

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.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby 999_Springs » Thu Mar 26, 2009 11:12 pm

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.

Postby StrmCkr » Fri Mar 27, 2009 7:12 am

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.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby Red Ed » Fri Mar 27, 2009 2:08 pm

I had the same download problems with Firefox, but no problem with Opera.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Allan Barker » Sat Mar 28, 2009 7:49 am

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

Postby 999_Springs » Sat Mar 28, 2009 11:55 pm

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.

Postby Pat » Sun Mar 29, 2009 2:59 pm

999_Springs wrote:I had never heard of people who, while manually solving, put pencilmarks at the bottom of cells instead of the top.
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby 999_Springs » Sun Mar 29, 2009 5:53 pm

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

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.


Your point being...?
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.

Postby Pat » Tue Mar 31, 2009 3:18 pm

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.


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
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby Pat » Tue Mar 31, 2009 3:55 pm

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
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005


Return to General