The chessboard is empty. In the center is the king. He can move only one square at a time, but in any direction — or he can choose not to move at all. How many turns would it take him, moving randomly, to exit the chessboard?
A chessboard is an 8-by-8 grid. For this month’s Exercise, create a 9-by-9 grid so that you can place the king directly in the center. Figure 1 illustrates how this setup might look by using primitive text graphics output from a C program.
Figure 1. The king is poised to wander.
Each turn, the king moves to one of 9 squares: north, northeast, east, southeast, south, southwest, west, northwest, or the king can stay where he is, as illustrated in Figure 2, which uses better graphics than Figure 1.
Figure 2. The king can move in any of these 8 directions or not at all.
Moving randomly, at some point, the king wanders off the chessboard (game grid) and ends the simulation.
Your task for this month’s Exercise is to code the Wandering King puzzle:
Start with the king in the center of a 9-by-9 game grid. Each turn, move the king in one of the nine directions illustrated in Figure 2. Keep in mind that not moving is also an option.
When the king slips from the game grid, report the number of turns it took him to do so. In my trials, it was surprising that sometimes the king wandered right off but other times it took more than 100 turns for him to find his way out.
You can optionally display the game grid each turn.
Please try this Exercise on your own before you look at my solution.
To make this into a meaningful simulation it might be useful to record the frequency of each step-count. I think it would follow some kind of skewed normal distribution but I’m not too sure.
You could then derive a formula for the probability of each number of steps.
I assume your solution has a limit built in as there is a possibility, however small, that the king will go on wandering around forever without actually falling off. And of course he could just stand there in the middle for ever and never move!
That was my original intent: Run the simulation a given number of times and see what the probability is. Also, see how the probability changes as you alter the grid size.
I do try to keep the Exercises here brief, however. I figured the king’s movement would be interesting enough that I didn’t have to pile on the extra coding.
My solution has no limit. In the iterations I ran the code, the highest value was 119 turns.