rail, 196 bytes

Result

AC

Code [DL]

$'d'
 -(!!)()()#
$'p'   #{p}()s1-@
 -(!!)()o{d}1q<
          #(!!)-@
$'f'
 -(!!)2c(!c!)9s(){p}(c)()9()g#
$'g'-i2mc2c(!!)1ap()p{g}#
 -e<
    #
$'h'
 -{f}<
 {h}a1-@
$'main'
 -[0909090909]{d}p{g}0{h}

stdin

5178971291510398900718619264131154473923649788399384412351932865901400755948487159575566619558549001

stdout

0000000011111111111111122222333333334444444444555555555555556666666777777778888888888999999999999999

stderr

Crash: No valid move

strace