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:

Status badges

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)

trac_7770_hanoi_tower_graph.patch (11.3 KB) - added by Rob Beezer 13 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 13 years ago by Rob Beezer

Authors: Rob Beezer
Status: newneeds_review

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 vertices
3,142,656 edges
240 seconds

Distance between vertex 0 and (4^10)-1, ie
the 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).

Changed 13 years ago by Rob Beezer

comment:2 Changed 13 years ago by David Joyner

Status: needs_reviewneeds_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 in reply to:  2 Changed 13 years ago by David Joyner

Status: needs_workneeds_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 David Joyner

Status: needs_reviewpositive_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 Rob Beezer

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 Mike Hansen

Merged in: sage-4.3.1.alpha0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.