Edge-coloring problems, of which Eternity II is an instance, are generally NP-Complete, and under the reasonable hypothesis that NP$\not\subseteq$BQP are not thought to have any exponential advantage relative to classical algorithms.
Nonetheless in the context of quantum algorithms there are at least some interesting questions we can ask about such problems and particularly about Eternity II.
For example, in the particular puzzle there are $256$ tiles, each of which can be in one of four different orientations, with each of the four edges of each tile selected from among twenty-three colors; each color can be represented with one qudit with $d=23$, or alternatively five qubits because $2^4\lt 23\lt 2^5$. Naively, each tile can be represented by a register of, say, $4\times 5=20$ qubits for (orientation$\times$color), and we have $256$ such tiles, for a total of at most $20\times 256=5120$ qubits to represent a state of the puzzle. Calling "valid puzzle-state" a permutation of the $256$ tiles laid out in a $16\times 16$ grid and a "solved state" a permutation of the $256$ tiles laid out in the $16\times 16$ grid to satisfy the edge-matching rules, these $5120$ qubits can be in superposition representing the puzzle, whether solved or not (indeed, whether a valid puzzle-state or not).
With such edge-matching puzzles, a local Hamiltonian almost immediately presents itself - in particular, we should add an energy penalty anytime neighboring edges don't match. Although I haven't studied the D-Wave paper mentioned in the comments, I suspect that D-Wave proposes to stoquastically evolve from a uniform superposition to the ground state of such a local Hamiltonian.
Another idea that may be worth considering is to consider a quantum walk along the state-space of all valid puzzle-states. For example, we can consider generators of $S_{256}$ - the symmetric group on the $256$ tiles, as well as generators of $C_4$ - the cyclic group of the four edges. A classical walk on such a Cayley graph is akin to a person starting with a puzzle-state and randomly SWAPing and/or rotating pieces. To get a continuous-time quantum walk we can trotterize over small root-of-SWAPs and root-of-rotations with respect to these generators, to simulate such a Hamiltonian. If we start in a valid puzzle-state initially, then we stay in the subspace of all valid puzzle-states by walking along this Cayley graph. Indeed we can prepare a $5120$-qubit register in a superposition over two puzzle-states and run a quantum phase estimation protocol to see if we can learn anything neat about the particular generators and the particular tiles in the puzzle.
But as mentioned in @Sanchayan's comment from even back in 2019 we are probably still far away from having the hardware to explore such approaches.
