  In 1987, Vaidman, Aharanov, and Albert put forward a puzzle called the Mean
King's Problem (MKP) that can be solved only by harnessing quantum
entanglement. Prime-powered solutions to the problem have been shown to exist,
but they have not yet been experimentally realized for any dimension beyond
two. We propose a general first-of-its-kind experimental scheme for solving the
MKP in prime dimensions ($D$). Our search is guided by the digital discovery
framework PyTheus, which finds highly interpretable graph-based representations
of quantum optical experimental setups; using it, we find specific solutions
and generalize to higher dimensions through human insight. As proof of
principle, we present a detailed investigation of our solution for the three-,
five-, and seven-dimensional cases. We obtain maximum success probabilities of
$72.8 \%$, $45.8\%$, and $34.8 \%$, respectively. We, therefore, posit that our
computer-inspired scheme yields solutions that exceed the classical probability
($1/D$) twofold, demonstrating its promise for experimental implementation.
