Sudoku is really not a “really hard puzzle” unless you're you generalize it to larger puzzles—the 9x9 form (used in the paper) is trivially solvable with even an old 6502 processor.

I'd argue that the statement from the conclusion “Beyond MAX-CUT, we solve more complex tasks such as number partitioning and Sudoku, highlighting its practical utility for real-world problems” is simply a lie, akin to claiming that factoring 221 on a quantum computer proves practical utility on real-world problems. At best it's a proof of concept.

Yes, reading those in the same sentence I also thought about a spin on 2048, the game.