One possibility is to generate or change small parts of the puzzle each turn. For minesweeper for example you start out with an empty field, and after the first click you generate the mines.