All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
God and the Devil (Posted on 2005-02-08) Difficulty: 4 of 5
God and the Devil decide to play a game. God will start by picking an infinite sequence of moves of the form "left", "right", "up", and "down". The Devil responds by creating a finite maze with an exit and by placing God somewhere inside. God then follows His pre-selected sequence to traverse the maze. Unmakable moves are ignored; for example, if the next move is "left" and there is a wall to the left of the current square, God goes on to the next move in the sequence without moving.

If God escapes the maze in finite time, He wins. Otherwise, the Devil wins.

Assuming both agents act optimally, who will win?

(assume that the maze is formed by deleting some edges from a rectangular grid, and that it has no isolated regions; i.e., it is always possible to get to the exit from any point inside the maze)

See The Solution Submitted by David Shin    
Rating: 3.6842 (19 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
My idea, for what it's worth | Comment 1 of 67
I guess that God moves left, right, forwards, bacwards (Or God'd go up and always left and be out).
So then I think that if God (Notice how carefully I avoid he and she) moved randomly, the distance from the starting point will increase with SQR(MOVES).  The edges may stop movement for a while in one direction, but on the long run every direction will be covered and the exit will be reached.
  Posted by Hugo on 2005-02-08 20:14:46
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information