I will be going to Japan for 3 weeks with the wife in July. This is the suggested itinerary I found:
http://www.japan-guide.com/e/e2400_tokyo_19.html
We will probably skip Himeji since its under construction. And a friend who lived in Nagasaki for many years suggested that it may not be worth the 4-5 hour train ride to go there.
Thoughts?