Where are the cows?

[desh]

The best maze ever is apparently online!

"Where Are the Cows?" was first published in Scientific American in 1996 as probably the only self-referential flowchart word maze in existence. I fell in love with it, and I think I even solved it. (Can't remember for sure.)

I went looking for it again about 4 years ago, and found it in a book called SuperMazes, by the maze's author, Robert Abbott. To my surprise, he said that this maze "may be too difficult for anyone to solve", making me really wish I could remember for sure if I solved it the first time around.

Just now I went looking for it online, to see if I could share it, and I found a copy. (Logically the same, as far as I can see, but a bit shabbier presentation-wise.) I present it to all of you.


The rules: Start with a pointer on box #1 and another pointer on box #7. A move consists of choosing one of your two pointers, following the instructions in that box, and then moving that pointer from that box, along the appropriate line, to another box. Generally the "instructions" are a yes/no question, and the "appropriate line" is either the one labeled "yes" or the one labeled "no". (Note that you do not "officially read" the new box you move to at that time; in other words, you don't follow the directions on the moved-to box until you choose that pointer again on a subsequent move.) On most moves, the only choice you make is which pointer to move.




I'm interested in what y'all think of the maze, because I think it's a great judge of what sort of intellectual exercise you enjoy or don't enjoy. Also please tell me if you attempt it, solve it, diagram it, can't even figure out how to move, or whatever. (And I might even give hints.)

Oh, and my second-favorite maze from SuperMazes is online and Javafied! Check out http://home.att.net/~robtabbott/sliding.html.

Comments

Cows.java:

[mrputter.livejournal.com]

import java.util.Hashtable;
import java.util.Stack;

public class Cows {
	public static void main( String[] potato ) {
		Cows c = new Cows();
		
		// What happens if both markers are on box #26?
		//  true  - chosen marker moves on 'Yes' path
		//  false - chosen marker moves on 'No' path
		boolean selfRef = true;
		
		c.solve( selfRef );
	}
	
	public Cows() {
		s = new Solver();
		visited = new Hashtable<String, Boolean>( 1024 );
		trail = new Stack<String>();
		max = 0;

		System.out.println( "Starting maze with marker A on square #1 and marker B on square #7...\n" );
	}
	
	public void solve( boolean selfRef ) {
		visit();
		if (! move( 0, false )) {
			if (! move( 1, false )) {
				loseGame();
			}
		}
	}
	
	private boolean beenHere() {
		if (visited.containsKey( mapState() )) {
			return true;
		}
		return false;
	}
	
	private void visit() {
		visited.put( mapState(), new Boolean( true ) );
	}
	
	private boolean move( int marker, boolean lugnut ) {
		String crumb = String.valueOf( (char) (marker + 65) ) + (lugnut ? "(lugnut)" : "");
		trail.push( crumb );
		if (trail.size() > max) {
			max = trail.size();
		}
		if (s.move( marker, lugnut )) {
			winGame();
			return true;
		} else {
			if (!beenHere()) {
				visit();
				if (move( 0, false )) {
					return true;
				}
				if (move( 1, false )) {
					return true;
				}
				
				// Lugnut moves
				if (s.getPosn().a == 55) {
					if (move( 0, true )) {
						return true;
					}
				}
				if (s.getPosn().b == 55) {
					if (move( 1, true )) {
						return true;
					}
				}
			}
		}
		trail.pop();
		s.backtrack();
		
		return false;
	}
	
	private String mapState() {
		Marker posn = s.getPosn();
		return (posn.a < 10 ? "0" : "") + String.valueOf( posn.a ) + (posn.b < 10 ? "0" : "") +
			String.valueOf( posn.b ) + (s.getGreen() ? "t" : "f") + String.valueOf( s.getLastMove() );
	}
	
	private void winGame() {
		String out = trail.pop();
		while (! trail.empty()) {
			out = trail.pop() + "->" + out;
		}
		System.out.println( "Move sequence:" );
		System.out.print( out );
		System.out.println( "\nA winnar is you!!" );
		System.out.println( "Number of moves: " + String.valueOf( max ) );
	}
	
	private void loseGame() {
		System.out.println( "D'oh! Can't get there from here." );
		System.out.println( "Went to a max depth of: " + String.valueOf( max ) );
		System.out.println( "Number of visited states: " + String.valueOf( visited.size() ) );
	}
	
	private Solver s;
	private Hashtable<String, Boolean> visited;
	private Stack<String> trail;
	private int max;
}

Re: Cows.java:

[desh]

Neat! Except that I don't really speak java. What exactly do these do? Do they simply present a java way of exploring the maze, or do they try to help solve it? Do they handle all the quirks of the various weird states that can come up? (I've found that 9, 26, and 60 make for a slightly-harder-than-trivial state graphs; not that I've gone through the entire graph yet.)