Rubik's cube is exactly the examplar case that gives me trouble. I think emotionally we feel the cube is a puzzle. But it's hard for me to deny that 'produce a cube with solid-coloured faces' is a victory condition for a one-player game, and there are a clear set of legal moves to use to achieve it. (That there is a known algorithm for achieving it is clearly not an obstacle; there's a known solution to Connect 4 as well but it's clearly a game.)
Pace gomad's answer, I think single-player games and puzzles usually both possess a defined winning condition (a goal), and a legal sequence of moves to attempt to achieve it.
Proposal: A single-player activity with a goal and legal moves is a game, as opposed to a puzzle, if it also possesses a clear losing condition; that is, a game-state under which the goal can no longer be achieved.
This rules out Rubik's cube, crosswords, and other puzzles where you can always keep trying. It allows Freecell and other solitaire card games (they usually have a can't-try-any-more-moves end-state). And importantly for my peace of mind, will always allow solitaire games such as, say, solitaire Pandemic or Death Angel, which we clearly do wish to be on topic!