But writing the game would involve generating puzzles, wouldn't it?
There are sample puzzles around. I'm sure I could dig a couple up.
Really to show off your program you'd only have to develop maybe 4 or 5... and they could all be simple.
Maybe we'd have to add a requirement that puzzles have to be loaded externally. Then the compo itself could have the puzzle files and your version of the game would have to load and play them.
Puzzles could be just text files. For example, the puzzle on the Wikipedia page could be:
That could be an extra feature people could code into their program ;)
But even that would be extremely tricky. It's really hard to make a good sokoban puzzle that can actually be solved. It might even be harder than writing a solver.