I think ultimately it should be both winnable and losable and entertaining in some way. As a roguelike it should be more losable than winnable, which also helps boost the third criteria
I remember when first developing Gruesome I went from having a simple character exploring random caves, to a character exploring random caves and avoiding spinning lighthouses. This small change made a big difference - it was suddenly fun to play and very challenging, and had both win and lose conditions. It was all I needed to justify releasing it, and in spite of its simplicity no one has ever questioned its status as a game.
Ultimately of course it comes down to the developer what he classes as complete. Out of the 25 "successes" last year I remember 2 in particular that didn't really qualify as proper completions, and the developers themselves admitted so after I reviewed them.