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.
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.
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.