My python solution to this question: http://www.careercup.com/question?id=5380513791475712

8statues

moves = [int('011',base=8), int('0111', base=8), int('01110010', base=8), int('0100100',base=8), int('0101000',base=8), int('010001000',base=8), int('010100000',base=8), int('011000000',base=8)]

finalStates = [0, int('1'*8, base=8), int('2'*8, base=8), int('3'*8, base=8)]

TERMINAL = int('4'*8, base=8)

MASK = int('3'*8, base=8)

def code(c):
	if c == 'N':
		return 0
	elif c == 'E':
		return 1
	elif c == 'S':
		return 2
	elif c == 'W':
		return 3

def solve(string):
	initState = 0
	for i in xrange(len(string)):
		initState += (code(string[i]) << 3*i)
	print initState
	queue = [initState, TERMINAL]
	isVisited = {initState : None}
	count = 0
	while True:
		state = queue[0]
		del queue[0]
		if state == TERMINAL:
			if len(queue) == 0:
				return -1;
			count += 1
			queue.append(state)
		else:
			for i in xrange(8):
				newState = (state + moves[i]) & MASK
				if newState in finalStates:
					return count+1
				if isVisited.has_key(newState) == False:
					isVisited[newState] = None
					queue.append(newState)

'NSWWEWEN' : 10
'SNSWESWS' : 8