Discover doesn't find palapeli because the appstream data is missing. I searched both for "palapeli" and "puzzle" and it didn't find Palapeli. "Apt search puzzle" did find it, however. This was in a Kubuntu 16.10 vm with the latest KDE Applications. Reproducible: Always Steps to Reproduce: 1. search for "puzzle" or "palapeli" in Discover 2. 3. Actual Results: Lots of other puzzle games, but not Palapeli Expected Results: Find and install Palapeli. This was really a test of the latest Discover but the Kubuntu devels tell me it is actually missing appstream information in the game. Perhaps the missing appstream info could be junior job bugs?
From what I can see, Palapeli is not alone in this. NONE of the KDE Games have appstream data. Is appstream something KDE Games is supporting - or KDE software as a whole for that matter? Not knowing what appstream was, I had a brief look via Google, Wikipedia and freedesktop.org and found it a bit of a turn-off. But then I am approaching 80 and have announced my retirement from KDE Games some time ago. So yeah, maybe a junior job, if the KDE Games group wants to do anything about it.
http://commits.kde.org/palapeli/6de085a058cdd5365ddc81b77567cc958e5aeb49