Problem 61067. Transition Matrix for the Royal Game of Err

Bored of tedious court assemblies, King Neduchadneddar the Procrastinator has found a cunning way to keep his advisors, councilors, viziers, and other courtly lackeys busy: he plays a simple and pointless board game with them.
Players move their pawn along a path of n squares, starting at square 1, with the goal of being the first to reach square n. On each turn, they roll an m-sided die to determine how many squares to move. However, if their move would take them beyond the nth square, they stay put. Also, players cannot land on any of the numbers that King Neduchadneddar has decided are the unlucky numbers of the day. If their move would land them on any of these squares, they stay put instead.
To keep his courtiers on their toes (so they have less time to plot his downfall), the king changes the number of squares (n), the number of sides of the die (m), and the list of unlucky forbidden squares each day.
Needing to know how much time he will waste with each game, the king in his wisdom (and/or insanity) has appointed you Chief Royal Mage of Matrix Computations and tasked you with determining the average number of moves it will take a player to complete a game according to today’s setup.
Your first task to achieve this important goal is to build the transition matrix for the game, given n, m, and nogo (a vector of the forbidden numbers). The transition matrix T is an n-by-n matrix where T(j,k) is the probability of moving from square j to square k in one move.
Example
If n = 8 and m = 3, with no forbidden squares the transition matrix would be:
0 1/3 1/3 1/3 0 0 0 0
0 0 1/3 1/3 1/3 0 0 0
0 0 0 1/3 1/3 1/3 0 0
0 0 0 0 1/3 1/3 1/3 0
0 0 0 0 0 1/3 1/3 1/3
0 0 0 0 0 1/3 1/3 1/3
0 0 0 0 0 0 2/3 1/3
0 0 0 0 0 0 0 1
Generally, from square j there is a 1/3 chance of moving to j+1, j+2, or j+3. However, for j = 6, there is a 1/3 chance of moving to 7, a 1/3 chance of moving to 8, and a 1/3 chance of remaining at 6 (from rolling a 3). For j = 7, there is a 1/3 chance of moving to 8, and a 2/3 chance of remaining at 7 (from rolling a 2 or a 3). Once at 8, you remain there forever (the game is over).
If 5 is a forbidden square, the transition matrix becomes:
0 1/3 1/3 1/3 0 0 0 0
0 1/3 1/3 1/3 0 0 0 0
0 0 1/3 1/3 0 1/3 0 0
0 0 0 1/3 0 1/3 1/3 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1/3 1/3 1/3
0 0 0 0 0 0 2/3 1/3
0 0 0 0 0 0 0 1
Now for j = 2, 3, or 4, there is a 1/3 chance of staying put (by rolling a 3, 2, or 1, respectively). T(:,5) = 0 because there is no way to get to square 5. T(5,:) = 0 because there is no way to come from square 5.
Algorithm
One way to build T is to follow this procedure (example with n = 7, m = 4, nogo = [2 5]):
1. Start with a matrix of zeros with 1/m on each of the m superdiagonals (to account for regular movement):
0 1/4 1/4 1/4 1/4 0 0
0 0 1/4 1/4 1/4 1/4 0
0 0 0 1/4 1/4 1/4 1/4
0 0 0 0 1/4 1/4 1/4
0 0 0 0 0 1/4 1/4
0 0 0 0 0 0 1/4
0 0 0 0 0 0 0
2. Add (1:m)/m to the last m elements of the main diagonal (to account for staying put unless you land exactly on the final square):
0 1/4 1/4 1/4 1/4 0 0
0 0 1/4 1/4 1/4 1/4 0
0 0 0 1/4 1/4 1/4 1/4
0 0 0 1/4 1/4 1/4 1/4
0 0 0 0 1/2 1/4 1/4
0 0 0 0 0 3/4 1/4
0 0 0 0 0 0 1
3. For each forbidden square j, add the values of the jth column to the main diagonal (to account for staying put if you would have landed on a forbidden square); replace the entire jth column and jth row with zeros (to account to never being able to land on or come from a forbidden square):
1/2 0 1/4 1/4 0 0 0
0 0 0 0 0 0 0
0 0 1/4 1/4 0 1/4 1/4
0 0 0 1/2 0 1/4 1/4
0 0 0 0 0 0 0
0 0 0 0 0 3/4 1/4
0 0 0 0 0 0 1
Assumptions
Even King Neduchadneddar would be bored rolling a 1-sided die, so m ≥ 2. To ensure games last more than a single turn, n > m. To avoid the game being impossible to play, the court astrologers always ensure that the king's unlucky numbers for the day are within the range 2 to (n-1), and that there aren't too many of them. Every so often, the king is feeling particularly lucky, which means the list of forbidden squares will be given as an empty array.
Solve

Solution Stats

47.06% Correct | 52.94% Incorrect
Last Solution submitted on Nov 12, 2025

Solution Comments

Show comments

Problem Recent Solvers23

Suggested Problems

More from this Author33

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!