Announcement: Be excellent to each other.


Caravel Forum : Other Boards : Anything : really hard sudoku
Page 1 of 2
2
New Topic New Poll Post Reply
Poster Message
disoriented
Level: Smitemaster
Avatar
Rank Points: 2517
Registered: 08-07-2007
IP: Logged

File: hardest.gif (5.2 KB)
Downloaded 1444 times.
License: Public Domain
icon really hard sudoku (0)  
Ran across this Sudoku. Without using a computer, can you solve it?


____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

[Last edited by disoriented at 06-13-2009 11:17 AM]
06-13-2009 at 11:17 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Samuel
Level: Delver
Avatar
Rank Points: 69
Registered: 07-08-2007
IP: Logged
icon Re: really hard sudoku (0)  
I can solve any sudoku you throw me. I'll try it and get back to you.

____________________________
I believe in everything until it's
disproved. So I believe in fairies,
the myths, dragons. It all exists,
even if it's in your mind. Who's to
say that dreams and nightmares
aren't as real as the here and now?
John Lennon
06-13-2009 at 12:03 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
Briareos
Level: Smitemaster
Avatar
Rank Points: 3517
Registered: 08-07-2005
IP: Logged
icon Re: really hard sudoku (0)  
I prefer this one:



:D

np: Coldcut - Everything Is Under Control (Qemists Remix) (Sound Mirrors Remixes)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009) :(
06-13-2009 at 12:07 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
Samuel
Level: Delver
Avatar
Rank Points: 69
Registered: 07-08-2007
IP: Logged

File: sudoku_solution.JPG (14.8 KB)
Downloaded 67 times.
License: Public Domain
icon Re: really hard sudoku (0)  
Here it is. I hope I've got it right.

____________________________
I believe in everything until it's
disproved. So I believe in fairies,
the myths, dragons. It all exists,
even if it's in your mind. Who's to
say that dreams and nightmares
aren't as real as the here and now?
John Lennon
06-13-2009 at 12:52 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
Monkey
Level: Master Delver
Avatar
Rank Points: 190
Registered: 03-21-2006
IP: Logged
icon Re: really hard sudoku (0)  
Nope. Two threes in the fifth row.

____________________________
lurking
06-13-2009 at 04:17 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged
icon Re: really hard sudoku (0)  
All sudoku can be solved by simple process of elimination. The only real challenge is in not making careless errors. So if that puzzle's solvable, I daresay anyone here should be able to solve it.

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator
06-13-2009 at 04:25 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged
icon Re: really hard sudoku (0)  
VIPCOOL wrote:
I can't find any possible numbers by elimination (and other logical methods) without guessing. I think you have to use a guessing method (guess a number, see if it works, if it doesn't, eliminate it) to solve it.
If that's necessary, it isn't sudoku. Sorry.

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator
06-13-2009 at 05:05 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
disoriented
Level: Smitemaster
Avatar
Rank Points: 2517
Registered: 08-07-2007
IP: Logged
icon Re: really hard sudoku (0)  
Jatopian wrote:
VIPCOOL wrote:
I can't find any possible numbers by elimination (and other logical methods) without guessing. I think you have to use a guessing method (guess a number, see if it works, if it doesn't, eliminate it) to solve it.
If that's necessary, it isn't sudoku. Sorry.


Sudoku has only one rule: In each row, column, and 3x3 box, fill in a number from 1-9 once and only once.

There is a second general guideline that must be followed by all 'good' sudoku puzzles: The solution should be unique.

If the above facts are true, it's a valid sudoku puzzle. Symmetry is desired for aesthetic effect but is not necessary for a valid puzzle.

I agree that you will probably need to do some brute force searching here, but you can use logic for the majority of the puzzle.

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

[Last edited by disoriented at 06-13-2009 05:54 PM]
06-13-2009 at 05:53 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Briareos
Level: Smitemaster
Avatar
Rank Points: 3517
Registered: 08-07-2005
IP: Logged
icon Re: really hard sudoku (0)  
If guessing is neccessary for a Sudoku, it's underspecified (and might have more than one solution), but it's still a Sudoku.

And it's still BOOORING. :P

np: Seņor Coconut Y Su Conjunto - Autobahn (Cumbia Merengue) (El Baile Aleman)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009) :(
06-13-2009 at 06:21 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Avatar
Rank Points: 2517
Registered: 08-07-2007
IP: Logged
icon Re: really hard sudoku (0)  
Definitely only one solution. :)

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.
06-13-2009 at 06:33 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
NoahT
Level: Smitemaster
Avatar
Rank Points: 1222
Registered: 06-17-2003
IP: Logged
icon Re: really hard sudoku (0)  
Could you please secret that?

-Noah

____________________________
And in the end, the love you take is equal to the love you make.

My stuff:
Click here to view the secret text

06-13-2009 at 07:14 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Dex Stewart
Level: Smiter
Rank Points: 355
Registered: 01-19-2007
IP: Logged
icon Re: really hard sudoku (0)  
This site, claiming to be a Sudoku solver using only logic, finds the sudoku impossible. It can solve it by guessing (in something like 10 seconds, one whole minute if I have it check all cases), and needs to guess and try 22 times to stumble upon the solution.

[Last edited by Dex Stewart at 06-13-2009 09:18 PM]
06-13-2009 at 09:18 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (0)  
Uh... Trickster? If anyone in this thread has still been thinking about this puzzle after two years, they need to get some serious help.

____________________________
-Logan
09-21-2011 at 01:09 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged
icon Re: really hard sudoku (0)  
Yeah, you know DROD players, sitting there crunching away at numbers, methodically and with little to no sleep, for years if that's what it takes to solve a problem.

Wait, I'm thinking of supercomputers.

Still, I don't see the need to go over the whole spiel about necro-ing of threads again. Suffice to say that I'm 0k with it in this instance.

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator
09-21-2011 at 06:02 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (0)  
There are different levels or mentalities behind creating Sudoku puzzles. Not all Sudoku puzzles have a unique solution (which generally is frowned upon) but there are some that require guessing (but still have a unique solution). As an example, as far as is known, the fewest number of filled in squares a puzzle can have and still have a unique solution is 17 but you are going to have to guess. I read about one guy a while back who collects 17-digit puzzles. They're really tough though because lots of guessing is required but that doesn't mean it's not a "real" Sudoku puzzle. Perhaps the American papers try to prevent the need to guess but there are puzzle makers out there who don't.

____________________________
-Logan
09-21-2011 at 07:19 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged
icon Re: really hard sudoku (0)  
Apparently the Sudoku puzzles in the PDF file in the directory here are really hard. (I haven't tried them myself.)

http://www.aisudoku.com/en/

I learned about the Finnish mathematician who composes them via this excellent article on writing a Sudoku solver.

http://norvig.com/sudoku.html

Note that the Norvig article displays the answers to the hard puzzles. You might want to read it carefully if you really, really want to avoid any kind spoilers before trying the puzzles.

09-21-2011 at 08:03 PM
View Profile Show all user's posts This architect's holds Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (0)  
You just "undefined" "guessing", because sure, given enough memory in your "stack", even if verifying a number will work is 25 moves away, it's still not a "guess" by your definition. In that case, no Sudoku puzzle with a unique solution requires guessing because the "unique" part automatically ensures someone, somewhere, will be able to solve it.

What's the point then?

____________________________
-Logan

[Last edited by west.logan at 09-21-2011 09:53 PM]
09-21-2011 at 09:53 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (0)  
But that situation does happen with the more difficult Sudoku puzzles. I wrote a paper on Sudoku puzzle generation and difficulty levels back when I was in university and the hardest ones required some form of "choose a number that might fit and go with it until it works". That might be five, or even ten moves away to find a contradiction, which theoretically you could do in your head (I'm sure I couldn't). The situation you describe does come up, unless I'm misunderstanding your explanation. For my brain, that would be "guessing".

As an interesting piece of information, most Sudoku puzzles are close to being diagonally symmetric. There's no real reason for this, it just looks more pleasing and that's what most puzzle generators make.

____________________________
-Logan
09-22-2011 at 01:15 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
stigant
Level: Smitemaster
Avatar
Rank Points: 1182
Registered: 08-19-2004
IP: Logged
icon Re: really hard sudoku (0)  
Most human solvers and people who construct Sudoku (and other logic puzzles) for other people to enjoy/solve have a very low opinion of puzzles which require guessing. The reason for this is that they realize that any logic puzzle can be solved with a brute-strength guessing algorithm. The enjoyment of the puzzle doesn't come in finding the one solution to the puzzle. It comes in finding a cool, intelligent way to find the one solution to the puzzle. The FUN part of the solve is when you see that little new idea that the constructor took advantage of in constructing the puzzle. From the constructor's point of view, it's fairly trivial to come up with a sudoku/LP that is solvable but not by a human (without guessing). The real challenge is to come up with a puzzle that IS solvable without guessing, but is really hard to see the whiz-bang insight necessary to do so.

As a side note, scanraid says this puzzle is unsolvable without guessing.

____________________________
Progress Quest Progress
09-22-2011 at 08:43 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
stigant
Level: Smitemaster
Avatar
Rank Points: 1182
Registered: 08-19-2004
IP: Logged
icon Re: really hard sudoku (+2)  
Well, ok, trivially, every valid (ie one-solution) sudoku can be solved without guessing by claiming that the particular pattern represented by that Sudoku ALWAYS resolves to the solution of that sudoku.

At any rate, I never said that scanraid's pronouncement proved that it's unsolvable without guessing (though, that could reasonably be inferred from my phrasing). Scanraid does, however, employ every non-guessing technique currently used by top-level human solvers, and several more that are beyond even their (top solvers) ability to implement. It's generally regarded as being the best of the best of the best. If it has to guess, then the number of humans per billion who can solve without guessing can be counted on the fingers of a double-amputee.

____________________________
Progress Quest Progress
09-22-2011 at 09:47 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Schik
Level: Legendary Smitemaster
Avatar
Rank Points: 5528
Registered: 02-04-2003
IP: Logged
icon Re: really hard sudoku (0)  
stigant wrote:
If it has to guess, then the number of humans per billion who can solve without guessing can be counted on the fingers of a double-amputee.
Definitely. Definitely. K-mart sucks.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi
09-22-2011 at 09:52 PM
View Profile Send Private Message to User Show all user's posts High Scores Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (0)  
Schik wrote:
Definitely. Definitely. K-mart sucks.

But...I want boxers!

____________________________
-Logan
09-22-2011 at 10:03 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
stigant
Level: Smitemaster
Avatar
Rank Points: 1182
Registered: 08-19-2004
IP: Logged
icon Re: really hard sudoku (+3)  
I restrict cases all over the grid at the same time with different assumptions until I find a common element to all of them.

You mean you guess...

____________________________
Progress Quest Progress

[Last edited by stigant at 09-22-2011 11:59 PM]
09-22-2011 at 11:59 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Rabscuttle
Level: Smitemaster
Avatar
Rank Points: 2539
Registered: 09-10-2004
IP: Logged
icon Re: really hard sudoku (+1)  
My sudoku solver that I wrote a while ago (for Project Euler) needs to make 5 guesses before it reaches a solution
It reaches a dead end and has to backtrack twice.
It has 21 squares filled in (including the starters) when it first has to guess. (which, looking back, are _just_ the starters)

I'd have to look and see what logical rules it knows, but it makes a guess when none of the rules are applicable.





[Last edited by Rabscuttle at 09-23-2011 06:55 AM]
09-23-2011 at 06:54 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
west.logan
Level: Smitemaster
Avatar
Rank Points: 608
Registered: 03-09-2011
IP: Logged
icon Re: really hard sudoku (+2)  
Trickster wrote:
Nobody has bothered to define "guess", and yet you're all making these extremely definitive claims about an ill-defined concept. Y'all be full of it, I sez. :ras

Okay, since you seem so opposed to the concept, then what about calling it "brute-force"?

Typical methods for solving are
1. CRME (Column, Row, Minigrid elimination)
2. "Lone Ranger" elimination (where there's only one possibility left after looking at rows, columns, and minigrids)
3. Twins (similar to Lone Ranger cells in that there are only two possibilities for two cells
4. Triplets (same idea)
5. Brute-force (i.e., guessing and seeing if you run into a problem later on).

Does that help?

As it stands, what you're saying is akin to saying that you don't really have to guess which number the roulette ball will land on because if you know your physics, someone is observant and sharp enough to know which one. Maybe my "stack" doesn't have enough RAM, but I know I've certainly ran into situations where I had to guess. Just like on Minesweeper :P

____________________________
-Logan
09-23-2011 at 01:56 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
stigant
Level: Smitemaster
Avatar
Rank Points: 1182
Registered: 08-19-2004
IP: Logged
icon Re: really hard sudoku (+3)  
Y'all be full of it, I sez.
Well, yes and no. The fact is that the (known) proofs of most useful patterns starting with pointing pairs and on up require "what any reasonable person would consider a guess" at some level. So, in one sense, if a particular sudoku puzzle requires* pointing pairs, and its the solver's first time doing a sudoku puzzle, then they are likely to see that as a guess. If you've solved plenty of sudokus and see pointing pairs in your sleep, they cease to be guessing, and start being pattern-matching. Guessing is, in some sense, inherently an empirical rather than theoretical concept. It's in the eye of the solver.

* "requires pointing pairs" here is not meant to be a theoretical requirement either, but more of a practical requirement. Sure, you can usually use some other technique, but my conclusion should apply to that technique as well.

Now, I said earlier that the best (current) solvers (both human and computer) would have to guess on this puzzle. I feel confident in that assertion because the technology and abilities of these solvers, over time, has started to converge to a consensus on what a human can reasonably handle without guessing, and scanraid handles that (and more) before it starts to guess. This is not a theoretical definition of when a guess is required, of course, but I think that its less subjective than anything else you can come up with. Will smarter humans in the future be able to solve this puzzle without guessing. Maybe, but I doubt it.

As for your methods, I strongly suspect (though I can't prove) that anything you are doing, short of guessing, is a subset of a technique called The Sledgehammer Technique which was developed by one of the top LP solvers in the world, Wei Hwa.

____________________________
Progress Quest Progress
09-23-2011 at 02:28 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
stigant
Level: Smitemaster
Avatar
Rank Points: 1182
Registered: 08-19-2004
IP: Logged
icon Re: really hard sudoku (0)  
As it stands, what you're saying is akin to saying that you don't really have to guess which number the roulette ball will land on because if you know your physics, someone is observant and sharp enough to know which one.

Supposedly, a team at MIT actually developed a system to do this in the 1970s (pre mass integrated chips) which relied on a small set of observations that could be done during the rolling of the ball, and a basic computer to crunch differential equations. They could, with a high degree of accuracy predict in which 1/8th of the wheel the ball would land, and since you can place bets while the ball is in motion, they had the ability to sway the odds in their favor.

Maybe my "stack" doesn't have enough RAM, but I know I've certainly ran into situations where I had to guess. Just like on Minesweeper

I'm going to quibble a bit with this comment. Guessing and reaching a contradiction in order to eliminate a possibility in a sudoku puzzle is different from the type of guessing that is typical in a minesweeper puzzle. You can reach states in minesweeper (in fact, the STARTING state is one such state) in which there are multiple solutions to the puzzle based only on the information available at the time. Guessing and checking in the Sudoku puzzle is a valid logical deduction. It's just really annoying to have to solve it that way by hand when a computer can do the job much better and faster. Guessing in a minesweeper puzzle is necessary because no further logical deductions with the given information are possible from some states because those states can resolve to two or more different solutions.

EDIT: I'm assuming that by "Minesweeper" you are referring to the MS Windows program which is extremely popular and in which you are initially given no information about the grid rather than the more obscure logic puzzle in which you are usually given enough clues to logically deduce the location of the mines.

____________________________
Progress Quest Progress

[Last edited by stigant at 09-23-2011 05:23 PM]
09-23-2011 at 05:20 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged
icon Re: really hard sudoku (+3)  
I just fill the grid with random digits, put the newspaper down and watch the other commuters look at me as though I'm some sort of demi-God
10-01-2011 at 11:33 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Avatar
Rank Points: 2517
Registered: 08-07-2007
IP: Logged
icon Re: really hard sudoku (0)  
What did I just watch

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.
10-01-2011 at 11:42 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged
icon Re: really hard sudoku (0)  
You watched a clip from Tim & Eric Awesome Show Great Job!, whose mission seems to be to ruin already faint humor with unnecessary grossness. Occasionally they accidentally produce something worth watching. This is not one of those times.

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator
10-02-2011 at 12:44 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Page 1 of 2
2
New Topic New Poll Post Reply
Caravel Forum : Other Boards : Anything : really hard sudoku
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.9
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.