Opened 13 years ago
Closed 13 years ago
#7770 closed enhancement (fixed)
Implement Tower of Hanoi graph
Reported by: | Rob Beezer | Owned by: | Robert Miller |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.3.1 |
Component: | graph theory | Keywords: | tower of hanoi graph |
Cc: | Merged in: | sage-4.3.1.alpha0 | |
Authors: | Rob Beezer | Reviewers: | David Joyner |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The Tower of Hanoi puzzle can be described by a graph whose vertices are possible states of the disks on the pegs, with edges represdenting legitimate moves of a single disk.
Attachments (1)
Change History (7)
comment:1 Changed 13 years ago by
Authors: | → Rob Beezer |
---|---|
Status: | new → needs_review |
Changed 13 years ago by
Attachment: | trac_7770_hanoi_tower_graph.patch added |
---|
comment:2 follow-up: 3 Changed 13 years ago by
Status: | needs_review → needs_work |
---|
This looks like an interesting patch but
sage -t "devel/sage/sage/graphs/graph_generators.py"
seems to fail (sage 4.3, imac, 10.6.2).
comment:3 Changed 13 years ago by
Status: | needs_work → needs_review |
---|
Replying to wdj:
This looks like an interesting patch but
sage -t "devel/sage/sage/graphs/graph_generators.py"seems to fail (sage 4.3, imac, 10.6.2).
Arrgghh ...
Ignore this. I'll keep refereeing it.
comment:4 Changed 13 years ago by
Status: | needs_review → positive_review |
---|
Positive review.
Installs fine on 64bit ubuntu and imac 10.6.2 running sage 4.3. Passes sage -testall on the ubuntu machine and has (I think only) unrelated failures on the imac. Also I check the html output for the reference manual and it looks good.
Thanks for this patch Rob! I have used it already in some lecture notes I'm working on for next semester.
comment:5 Changed 13 years ago by
Reviewers: | → David Joyner |
---|
Hi David,
Thanks for the quick review, and I'm especially glad to hear it is being used *immediately*. ;-)
I'm going to send you some extra info on the graph off-list. (I don't have permission to post it yet).
Rob
comment:6 Changed 13 years ago by
Merged in: | → sage-4.3.1.alpha0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Some rough timing information on a 3 GHZ Core 2 Duo:
4 pegs, 10 disks, no labels, no layout info
2^20 = 1,048,576
vertices3,142,656 edges
240 seconds
Distance between vertex 0 and
(4^10)-1
, iethe minimum number of moves to solve the puzzle:
742 ms
I could probably provide timing on sage.math for a release tour (along with a nice graphic).