aspose file tools*
The moose likes Programming Diversions and the fly likes Nine dots Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Nine dots" Watch "Nine dots" New topic
Author

Nine dots

Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Hi all
I read this puzzle somewhere. Here it goes

Now the challenge is to use just 4 lines(is it possible to solve it with lesser no. lines ) to cover all the dots without lifting the pen/pencil and crossing a point that has been earlier marked. I wasn't able to solve this and don't have the solution.
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 29287
    
140

If you want the solution:
Nine dots answer


[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
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Hi Jeanne
Thanks for the answer.
Roy Tock
Ranch Hand

Joined: Jul 16, 2001
Posts: 83
There is a three line solution to the stated problem. Honest - no kidding.
I'll hold off on posting it...maybe somebody else can come up with it.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Well, I can think of two one-line solutions - depending which of the unstated "standard" assumptions we wish to violate. There's a three-line solution too, which is a bit easier to justify, given the way the problem was phrased. I'd be interested in seeing you make a good ASCII diagram of the 3-line solution though, Roy.
[ August 05, 2003: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Roy : I'll hold off on posting it...maybe somebody else can come up with it.
Jim : I'd be interested in seeing you make a good ASCII diagram of the 3-line solution though, Roy.

So Jim is waiting for Roy and Roy for Jim to give the answers.
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Jim : Well, I can think of two one-line solutions - depending which of the unstated "standard" assumptions we wish to violate.

I also thought of one but thats with three lines use three pens.
Bhau Mhatre
Ranch Hand

Joined: Jun 11, 2003
Posts: 199
Hi Jeanne, the solution that you gave crosses the lower-left point twice. Anupam's question reads "without lifting the pen/pencil and crossing a point that has been earlier marked"


-Mumbai cha Bhau
Bhau Mhatre
Ranch Hand

Joined: Jun 11, 2003
Posts: 199
Originally posted by Roy Tock:
There is a three line solution to the stated problem. Honest - no kidding.
I'll hold off on posting it...maybe somebody else can come up with it.

I know one three-line solution that involves using bigger sized dots
Is that what you have?
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Originally posted by Mumbai cha bhau:
Hi Jeanne, the solution that you gave crosses the lower-left point twice. Anupam's question reads "without lifting the pen/pencil and crossing a point that has been earlier marked"

Yeah in the answer yes it does. But you can surely start from the second dot of the first vertical row.
[ August 05, 2003: Message edited by: Anupam Sinha ]
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
I guess in the original version, no overwriting was also a rule. So I guess that the Jeanne's solution wouldn't hold in that case. But yes if we start from the second dot of the first vertical row, then it does answers my question.
Now another thing, is it possible to solve this puzzle with the orignal challenges and adding these two as well.
1. No overwritting. (no crossing of lines)
2. Use exactly four lines (no more no less)
Now is it solvable. Or is it solvable by us. Without using bigger dots and thin lines or so kinda approach.
[ August 05, 2003: Message edited by: Anupam Sinha ]
Bhau Mhatre
Ranch Hand

Joined: Jun 11, 2003
Posts: 199
Originally posted by Anupam Sinha:
Yeah in the answer yes it does. But you can surely start from the second dot of the first vertical row.

Didn't think about that
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I guess in the original version, no overwriting was also a rule.
If by "no overwriting" you mean "no crossing of lines, ever" then I doubt this was part of the original problem; it makes an elegant solution impossible. If "no overwriting" just means "don't pass through any dot more than once" then that's fine.
Now another thing, is it possible to solve this puzzle with the orignal challenges and adding these two as well.
1. No overwritting. (no crossing of lines)
2. Use exactly four lines (no more no less)
Now is it solvable. Or is it solvable by us. Without using bigger dots and thin lines or so kinda approach.

Well, I don't need bigger dots - the dots you gave us in the first place are already big enough. Seriously, you did use 'o' to indicate the dots, rather than '.' - to me that indicates that the dots do have nonzero width. Any width is sufficient for a 3-line solution (if the paper is really big); adding a 4th line is not difficult. Plus I've still got a 1-line solution you haven't excluded yet; I can add lines to that as necessary.
I had two 1-line solutions, but one required a really big marker. I suppose that was excluded by the very vague "without using bigger dots and thin lines or so kinda approach." I've still got the other solution though...
Roy Tock
Ranch Hand

Joined: Jul 16, 2001
Posts: 83
Jim and Mumbai both allude to the three-line solution I have in mind.
Since the dots have thickness, it's possible to draw lines through, say, the top three dots on a small non-zero angle from horizontal. With that observation, and the observation that your lines can be as long as you wish, you can see that it is possible to connect the nine dots with three lines.
ben ben
Greenhorn

Joined: Apr 04, 2005
Posts: 1
does anyone know the solution to a 16 dots sq? max 6 lines and a added challenge of no criss-crossing of the lines.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10929
    
  12

I assume we're talking about the dots being on a standard, Euclidian plane? I'm not SURE, but i'd wager that if you could put the dots on a curved plane (possibly a sphere), you could do it in fewer lines...

and if you could curve the plane enough, you could then draw a single line through the 3D world that hit all 9 points
[ April 04, 2005: Message edited by: fred rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Hi everybody,
I am not able to see this solution link because of some policies of company. Cound any body please draw that solution here for me.
Thanks a lot.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 989
    
    1
Ok, has anyone found a solution to the puzzle that the original author was trying to pose that uses four lines that DON'T cross? I'm convinced there isn't one, but I'm not positive.

- Nine zero-size points in a 3x3 square on a non-foldable euclidean plane.
- The line segments are zero-width.

Ryan
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I don't believe the original author of this thread required that the lines never cross. It was required that they not cross "a point which has earlier been marked." I took this to mean that for the nine points/dots which are shown originally, you can't go through those points more than once. However it's legal for two lines to cross at some other point besides those nine - and indeed, I don't believe a solution is possible otherwise. (Unless we violate one of the other originally-unstated assumptions of the problem, as discussed above.)

Recently a similar problem was posted here with the restriction "you should not overwrite a line". If this means that a line cannot intersect another line at all, and our other restrictions are also in place, then I don't believe a solution is possible. This is just another problem that, depending on how carefully it's stated, may have too many solutions, or none at all.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Nine dots
 
Similar Threads
reg a mock exam
Boone's mock exam Q47
Boonie's Exam: 47 - mistake??
Reassigning
Counting Dots