I walked out to Cape Solitude in early April of 2005. I suppose that ice and snow could be a bit of problem in such season, some years, but not this trip.
The trailhead would vary, depending on whether your vehicle has high clearance and four-wheel drive, and how insistent you are upon availing yourself of such mechanics. I would recommend walking. Take the road that goes from the Desert View congestion area, just by the entrance gates, more or less due east, by the ranger station and the NPS staff areas, out to a turnoff to a cesspool with a great view of Humphries Peak. Park your vehicle on a pulloff just beyond this turnoff. (I parked at this pulloff on two trips and no one appeared to have any objections.)
The entire route follows old jeep tracks that gradually dwindle to mere traces. The first bit follows a very strongly incised road that would take you eventually to Cedar Mountain, a nice day hike to the flat-topped butte you see off to the east from the tower of Desert View. This road descends by switchbacks through middle elevation forest, mostly pine, with occasional views off to the left of the Grand Canyon and more frequent views ahead of Cedar Mountain, the gorge of the Little Colorado, the semi-desert prairies surrounding it, the Echo Cliffs and even Navajo Mountain off to the north. The same views you get from Desert View, but with constantly varying angle. Take a left turn to the north after a couple of miles; this turn off is signalized (or was when I was there) by a sign forbidding motorized traffic. So you'll have to get out of your desert buster here.
The track drops down a wash for a mile or so, tracklessly in places, but you can't get lost. At the bottom of this wash you are crossing Straight Canyon, so named in comparison to some other canyons I suppose. Ascend the dodgy but unmissable track up the opposite tributary wash and in another mile or so you'll reach a "T" intersection. The left track will vanish in an elk stomping ground in less than a mile, after which you can bushwack to the rim of the Grand Canyon, with Comanche Point accessible with some cussing and route-finding. For Cape Solitude you take the right fork.
As there is no water on this route, I cached a gallon at this point, cradling it in some suitably armored desert vegetation, hoping to shelter it from the ravens that way. It was there when I returned, so it worked. I can't imagine they weren't watching me. In the Grand Canyon, they're always watching.
Beyond this, you descend for three miles or so through hilly grasslands, with expansive but prairie-like views to the NE, not quite what people associate with the Grand Canyon. You're angling toward a little butte, which I call Little Butte, as I didn't have the topo quadrangle covering it. You'll need the "Desert View" and "Cape Solitude" quadrangles for this trip, by the way. If you need them. It isn't really necessary, unless you're planning to bushwhack out to Comanche Point or elsewhere off the track. At the bottom of the descent, just shy of "Little Butte", you enter, very briefly, the turf of the Navajo Nation. Officially, non-Navajo's (or non-Indians? not sure) need a use permit at 5 dollars a day to hike in the Rez. This permit is obtainable at the Ranger Station (for this part of the Navajo Nation) in Cameron. I'd recommend visiting that facility 8 - 4 Monday thru Friday, if you're passing through, though the ranger may be out in the field.
This is where the only "route-finding" bit comes in. The track enters the Nation, through a fence, then branches off to the left after about 100 yards, exiting the Nation after fifty more. But this junction is astonishing hard to see from downhill, so I recommend just following the fence north on the NPS side across the wash that comes down from the west at that point. You'll pick up the continuation of the Cape Solitude track going off to the NW. There is very pretty stopping point a bit back up the wash, with a nice flat place under a rock with a few isolated cedars.
From here it's another few miles out to Cape Solitude, gently uphill then more or less flat. Halfway over the North Rim comes back into view, looking really more like a mountain range than a canyon rim. This impression was heightened by the snow that was still covering that area when I was there.
It was in this area that I encountered a large herd of elk, two to three hundred animals, I would guess. There was a great cloud of dust and a thunder, more felt than heard, as the animals fled. Where they get their water when they're in this area I couldn't tell you. Maybe they can get down to the Little Colorado to the east. The elk tracks cross and recross the now faint trail several times in this area. You might want to lay some signs for your return trip, as the true trail may not be so evident on the way back.
The track hits the rim of the Grand Canyon about a mile short of Cape Solitude. I set up camp in the open here. It had been a long walk with the backpack from the Desert View cesspool. As I stepped over to look almost straight down at the Colorado River (over 3 thousand feet), there was a rattle. Can't mistake that sound. I stepped back. Never did see the critter.
Packless, I continued out to Cape Solitude. I won't try to describe the views. I'd have to say that aloneness is what I felt most, on a dimming and nearly windless Spring evening. I sensed the noise of the river but am not sure I actually heard it.
The way back the next day was sweatier but not really much more difficult, as the total ascent to Desert View is only about a thousand feet, with probably another 4 to 5 hundred picked up on the return to the "T" intersection and lost in descending to the bottom of Straight Canyon.
I had intended to bug out to Comanche Point on the way back, but was too lazy. I did, however, just go due west from the "T" and continue in that direction from the elk stomp. Taking that route, with a short and very unproblematic bushwhack, you'll soon hit the Rim. But take your compass, just in case you get confused. Odd how you can spot these old tracks from a distance but miss them when you walk right across them.
I wound up spending the second night in a forested elbow of the rim half a mile by raven from the Desert View tower. There was a light in the thing all night. I had thought this violate the essence of the place but it actually had an effect akin to seeing a distant lighthouse on the Atlantic, increasing the sense of remoteness, with the anthropic element being put into charmingly small scope, that light and me.
This is a great trip if you don't mind a long walk across a topography that's pretty mild by Grand Canyon standards, don't have permits for the more popular areas, and are seeking the namesake solitude. I didn't see anyone on this trip. I saw prints, tire and foot, on the first leg between the trailhead and the first turnoff. Odd, though. I left my hiking stick somewhere beside the trail between the Rez boundary and Cape Solitude. But I never found it on the way back. I can't help thinking that the two ravens who followed me most of the day picked it up and flew off with it. That or a ghost.
Gate Policy: If a gate is closed upon arrival, leave it closed after you go through. If it is open, leave it open. Leaving a closed gate open may put cattle in danger. Closing an open gate may cut them off from water. Please be respectful, leave gates as found.
WARNING! Hiking and outdoor related sports can be dangerous. Be responsible and prepare for the trip. Study the area you are entering and plan accordingly. Dress for the current and unexpected weather changes. Take plenty of water. Never go alone. Make an itinerary with your plan(s), route(s), destination(s) and expected return time. Give your itinerary to trusted family and/or friends.