As Sudoku is now part of GNOME, the correct package is gnome-games.
** Changed in: gnome-sudoku (Ubuntu)
Sourcepackagename: gnome-sudoku => gnome-games
Status: Unconfirmed => Confirmed
--
GNOME sudoku menu entry's tooltip is not phrased as a verb
https://launchpad.net/bugs/89342