This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Meaningless Drivel and the fly likes Possible Sudoku Spoiler Alert Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Possible Sudoku Spoiler Alert" Watch "Possible Sudoku Spoiler Alert" New topic
Author

Possible Sudoku Spoiler Alert

Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
For some reason, I'm spending some of my precious time trying to figure out Sudoku-solving-strategies on my own. I'm sure I could just Google these, but what the heck.

So, what follows could be a spoiler for those of you who are also going it alone

I figure I'm a "pretty good" Sudoku-er - I focus on only the hardest problems in whatever book I've grabbed. But sometimes they stump me. I recently had a conceptual breakthrough - still time before the spoiler...

This so-called "breakthrough" of mine is based on the idea that for each puzzle there is only one solution.

Given that "na" means "not applicable" and "(x)" means one of two possible locations,

Let's say you have this rough situation in two of the nine boxes (in the same row or column):

na na na

na na na

(91) 7 (91) <--- previously calculated that only 9 and 1 could go in these two locations

-----------

na na na

na na na

(91) na (91) <--- this is not a valid "possibilities" notation, because it would allow two solutions.


It turns out that this strategy applies a lot when I'm stuck. Is this a no-brainer that I was just slow to get to?


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Well, your drawing doesn't quite convey what I think you're talking about. But I think you mean this:

You can't have 1's and 9's like this, because then you could switch the 1's and the 9's and there would be two solutions (unless some of the 1's and 9's are pre-printed).

Yes, that's a strategy that I use, rarely. But also yes, it wasn't one of the first strategies I discovered. When I mentioned it to my father he acknowledged that it was a strategy that he used, too.

However I did once find a correct solution to a published Sudoku which wasn't the same as the correct solution in the back of the book...
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

I must admit I don't like that sort of technique (you get similar cases in other types of logic problem - for some reason I don't think to use it as often in sudoku), because it assumes the existence of a unique solution, and intellectually I consider proving the solution is unique as part of the puzzle. But it's valid enough if you trust the setter.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41180
    
  45
Matthew Brown wrote:it assumes the existence of a unique solution

I think proper Sudokus have exactly one solution, so it'd be fine to make that assumption.


Ping & DNS - my free Android networking tools app
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Oh, I know it's OK. I just don't find it as satisfying.

(And then you do get the occasional poorly formed one like Paul found)
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
That's interesting, for some reason when it hit me I found it enormously satisfying. Like a sideways or heuristic leap. Like coming in through the back door
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

And I had exactly the same feeling that Matthew describes when I found it.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

There's a famous math problem which has a similar basis (at least it's famous among those who were calculus teaching assistants):

You have a sphere, and you drill a straight, circular, hole through the centre. (Along a diameter of the sphere.) The length of this hole is 10 centimetres. What is the volume of the remaining material?
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
Paul,

I'm sure I'm falling for something here but don't we need to know the diameter of the drill bit?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

And what is the diameter of the of the sphere? The question implies 10 centimeters, but that's assuming the hole went all the way through the sphere.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Bert: no, the diameter of the hole is one of the unknowns.

Stephan: no, the diameter of the sphere is also one of the unknowns. And sorry for the unclarity, the hole does go all the way through the sphere. (So the diameter of the sphere is at least 10 centimetres but can be greater.)
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Anyway, the point was that it is a fairly straightforward, but tedious, first-year calculus problem. (The volume is the result of a certain area being rotated around a central axis, so you would have to figure out what integral to do, and so forth. Details are left for the interested student.)

But every year there was one or two students who would say "Look, there's a unique answer to this, or you wouldn't have asked it. So it must be independent of the diameter of the hole. So let's set the diameter of the hole to be zero, then what we have is a sphere whose diameter is 10 centimetres and therefore the answer is just given by the formula for the volume of a sphere."

And it turns out, if you grind your way through the calculation correctly, that the answer is indeed independent of the diameter of the hole.

This always made for an interesting classroom discussion when the homework was graded and returned. Was that a legitimate assumption or not? (But we always gave those smart-asses full credit for showing good mathematical instincts.)
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14



How can it be independent from the size of the drill? Like you said, for diameter zero, the solution equals the volume of the entire sphere. If we use a wider drill (possibly one that is so large that we grind away the entire sphere!) won't the solution be different from the volume of the original sphere? Doesn't that imply that the outcome *does* depend on the diameter of the hole (as one would intuitively think)?

Maybe I'm completely misunderstanding the question.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
I am SO NOT going to dig out my old Calc text, but I think I get the drift and it's cool

So, if I'm understanding this correctly, you could start with a sphere of diameter 100 cm. In order to have a hole 10 cm high, the bit would have to be almost 100 cm. itself, so the resulting shape would be this thin donut-y thing (10 cm high)... is that the gist?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Stephan van Hulst wrote: If we use a wider drill (possibly one that is so large that we grind away the entire sphere!) won't the solution be different from the volume of the original sphere?


If you use a wider drill, then you need a bigger sphere so that the length of the hole is still 10 centimetres. (Remember, that's the only length you know.) Like Bert said, if the sphere is really big then you need to drill a really wide hole so that it's length is only 10 centimetres. Imagine drilling such a hole through the earth, for example -- you'd end up with a ring 12,800 kilometres around which was 10 centimetres high and thinner than a sheet of paper.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

Oh geez... So the premise is "Drill a hole wide enough so that you're left with a ring that's 10cm high". I call shenanigans on the phrasing :P
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Nice.

I suppose the question is whether you want to encourage the "trick" or not. If not, it would be easy enough to rephrase it "find the volume and prove that it is independent of the width of the drill bit" if you wanted to discourage it.

Or even just the "prove" bit, leaving room for some intuitive shortcuts. Just been googling, and found a neat proof of it without going to the trouble of calculating the volume.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3003
    
    9
Stephan van Hulst wrote:Oh geez... So the premise is "Drill a hole wide enough so that you're left with a ring that's 10cm high". I call shenanigans on the phrasing :P

Eh, I think that part was clear enough. But I don't think the phrasing here actually justifies the assumption that there's a single numeric answer. The answer could have been a formula based on the radius of the sphere, for example. And I think students need to be prepared to consider outside-the-box answers to questions, including "there are infinitely many solutions" and "there is no solution" for a given problem. Training them to assume there is one unique solution isn't good practice, because the real world isn't always like that. Still, I would be inclined to give full credit to students taking the shortcut, because it's good to consider such alternate approaches.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Mike Simmons wrote:But I don't think the phrasing here actually justifies the assumption that there's a single numeric answer. The answer could have been a formula based on the radius of the sphere, for example. And I think students need to be prepared to consider outside-the-box answers to questions, including "there are infinitely many solutions" and "there is no solution" for a given problem. Training them to assume there is one unique solution isn't good practice, because the real world isn't always like that. Still, I would be inclined to give full credit to students taking the shortcut, because it's good to consider such alternate approaches.


Yes, that was the gist of the classroom discussion which would take place. Bear in mind that first-year calculus problem sets basically consist entirely of calculations which result in a single correct number as the answer, so the assumption that there was a single correct number as the answer isn't exactly out-of-the-box. However identifying that as an assumption is in itself a problem-solving methodology; most students just take it for granted and are unable to articulate it as such.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
Back to the original Sudoku idea, since I first started this thread I've done a few more puzzles, and this "unique solution" strategy is helping me crack a LOT of puzzles that had stumped me before. On the other hand, I have noticed that certain puzzles tend to be more tractable using a given strategy, so it's possible that I've just run into a collection of puzzles whose style is suited to analysis with this strategy.

Still, it feels like this is going to be an important tool in my Sudoku toolkit.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

In high school I once started a Delphi project to make a Sudoku solver. I only added strategies to it that I used myself when I was solving a puzzle 'by hand', so I could see how far my strategies got me before I would have to 'guess' cells. My solver only ever managed to complete the simplest of puzzles
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30138
    
150

Bert,
One of the sudoko books I have listed this as a strategy. Making it a good strategy and not a spoiler .


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Possible Sudoku Spoiler Alert
 
Similar Threads
91% scwcd
passed with 91%
cleared wcd - 91%
Passed SCJP with 91%
91%