Interesante reflexión. Contestando, mis primeras impresiones creo se debería de mirar lo siguiente:
-A) La solución del juego debe ser múltiple, debe tener mas de un posible camino la solución del juego planteado.
-B) El set-up del juego debe poder plantearlo el mismo jugador de múltiples maneras.
Si cumple B y cumple A, cómo El Ricochet Robot o Set por ejemplo, son juegos, aunque ya los juegos actuales tienen algùn tipo de set up aleatorio cómo el Dominion.
Si no cumple B y cumple A, diriamos que son juegos también, en el caso de que admita varios jugadores. Si es para un sólo jugador creo que sería un puzzle si no hay elementos con azar.
Si no cumple B y no cumple A, diría que son puzzles. Un Sodoku por ejemplo.
Si cumple B y no cumple A, diría que son puzzles. El cubo de Rubik. Los juegos de rapidez cómo Fantasma de Blitz tienen set-up aleatorio, son juegos.
Esto creo que es lo que llevo pensando desde siempre aunque igual habría que especificar algún detalle ya que es un mundo muy variopinto.