Expected number of moves to reach the end of a board | Matrix Exponentiation | Python3 implementation of the approach ; Function to multiply two 7 * 7 matrix ; Function to perform matrix exponentiation ; 7 * 7 identity matrix ; Loop to find the power ; Function to return the required count ; Base cases ; Multiplier matrix ; Finding the required multiplier i . e mul ^ ( X - 6 ) ; Final answer ; Driver code
import numpy as np NEW_LINE maxSize = 50 NEW_LINE def matrix_product ( a , b ) : NEW_LINE INDENT c = np . zeros ( ( 7 , 7 ) ) ; NEW_LINE for i in range ( 7 ) : NEW_LINE INDENT for j in range ( 7 ) : NEW_LINE INDENT for k in range ( 7 ) : NEW_LINE INDENT c [ i ] [ j ] += a [ i ] [ k ] * b [ k ] [ j ] ; NEW_LINE DEDENT DEDENT DEDENT return c NEW_LINE DEDENT def mul_expo ( mul , p ) : NEW_LINE INDENT s = [ [ 1 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 1 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 1 ] ] ; NEW_LINE while ( p != 1 ) : NEW_LINE INDENT if ( p % 2 == 1 ) : NEW_LINE INDENT s = matrix_product ( s , mul ) ; NEW_LINE DEDENT mul = matrix_product ( mul , mul ) ; NEW_LINE p //= 2 ; NEW_LINE DEDENT return matrix_product ( mul , s ) ; NEW_LINE DEDENT def expectedSteps ( x ) : NEW_LINE INDENT if ( x == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( x <= 6 ) : NEW_LINE INDENT return 6 ; NEW_LINE DEDENT mul = [ [ 7 / 6 , 1 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 1 ] , [ - 1 / 6 , 0 , 0 , 0 , 0 , 0 , 0 ] ] ; NEW_LINE mul = mul_expo ( mul , x - 6 ) ; NEW_LINE return ( mul [ 0 ] [ 0 ] + mul [ 1 ] [ 0 ] + mul [ 2 ] [ 0 ] + mul [ 3 ] [ 0 ] + mul [ 4 ] [ 0 ] + mul [ 5 ] [ 0 ] ) * 6 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 10 ; NEW_LINE print ( expectedSteps ( n - 1 ) ) ; NEW_LINE DEDENT