I never went through the exact situation you are asking about, but I think my experience transfers correctly here.
I was one of the 4 players, in a group where we all knew each other.
Our characters had some kind of "rollback in time joker". We had been trapped in a room with a strange device.
After some time passed, the device would move and some kind of laser would hit a target, then the room would be engulfed in flames, killing us and triggering the time rollback.
The solution was to move a specific set of lenses in the path of the laser so that when it hit the target it would open a path that we could take to flee. The combination wasn't random but it was very hard to guess so we did a fair amount of trial-and-error before we understood the solution.
The main difference with what you are attempting is that that was a life-or-death situation and it could have ended the campaign if we never found the solution. In your case you don't have that issue.
Make them fail
You want your players to fail (at least the first few times), so there has to be a clear failure condition. I recommend using a hidden timer (something like "ten minutes after someone has entered the room, the puzzle teleports away"), that way you are almost guaranteed that the players won't figure it during the first encounter.
The second time they encounter the puzzle, they will have their previous experience to help them and know they have to be quick (or will suspect that something they did wrong the first triggered the teleportation time and they will be extra careful). That said, they probably didn't think about this puzzle in the meantime so unless your puzzle is easy (it shouldn't) they will fail once again. From then you can expect your players to guess this puzzle probably will come up again later and try to figure it out before that happens.
Let them succeed
Failing may be fun, but you want them to eventually overcome the difficulty! Depending on how good they are with puzzles in general it may happen "naturally", or they may loose interest by the third encounter. However you have a big advantage here compared to most puzzle situations: your players have time. They may think about this puzzle between sessions, or during the lunch break, or any time the DM is taking a bathroom break...
On top of that, there are ways for the PCs to find more information in-universe: maybe they know someone who is fond of puzzles who can try to help them? Even if they don't think about anything you can give them clues in an old dusty book found in a dungeon, or by having an NPC talk to them about the topic the puzzle is about... All those tricks feel cheap when used in solve-or-die kinds of puzzles but here you can take all the time you need to make it subtle.
What follows is only a example, that follows the previous points.
The Lost Crusader was a very powerful Paladin, who killed hundreds of fiends with his legendary blade Hornslayer. Unfortunately some devils tricked him into signing a pact and he died dishonored. For his soul to recover peace, his sword has to be wielded one last time and be used to kill those specific devils, without failing to respect the pact.
The ghost of the Paladin is trying to give his sword to the PCs, but the pact makes it so that he can only appear in the ten minutes that separates day from night at dusk. He also can't speak. For someone to recover the sword they have to kneel and recite the oath of the fiend slayers
During the first encounter, as they are setting a camp the PCs will see a silent ghost who appears to try to hold his sword as if he was trying to give it to them. If they try to take it their hand goes through, and the ghost doesn't seem to understand them. As the last ray of the sun disappears, the ghost vanishes.
A week later, the same ghost appears, and does the exact same thing. The PCs may try to speak to him in different languages, to trade him something, to inspect him... Still no luck so far.
The next day, as they pass by a town, they ask a few of the townsfolk about the ghost, and among various nonsensical rumors someone suggests the ghost may be of a member of the fiend slayers. As the PCs visit the Temple of Fiend Slaying they can see that all the fiend slayers have this same insignia and they don't recall seeing it on the ghost. That's because the ghost is old, the order was founded by him, and only after that they started to wear the crest.
Ten days later, the ghost appears again, and they look for the insignia. They don't find it but notice that the sword looks like the sword on the crest and the helmet has the same shape: clearly there is something fishy here. Still they don't have more idea.
Later on, they rescue Malia a young gal and she tells them she is an apprentice of the Order of Fiend Slaying. She asks them to bring her to one of their temples. As they remember the ghost they ask people there and learn about the Lost Crusader: there are too many similarities for this to be a coincidence! Still they don't know what they are supposed to do with the ghost. A monk suggests that maybe they should try sparring with the ghost (that's a red herring).
Even later, the PCs receive an invitation for Malia's graduation: she is going to swear her vows and become a true Paladin. They come and see the ceremony. At some point her master offers her a sword, she kneels, swears, and receive it. The way the master holds the swords looks a lot like the posture of the ghost.
The next time the PCs encounter the ghost one of them -who was already ready to spend the rest of his life slaying fiends-, decides to kneel and swear. The ghost then gives the sword and vanishes (he actually still inhabits the sword for as long as the devils are alive).
Of course, the PCs could not have got the last clue and still be stuck, but as the DM you always can give more clues, up until the point it becomes very obvious. You should also offer them other ways to solve the situation: let's say none of them are fond of swearing as they don't think they will be able to hold their word, maybe they can convince a paladin NPC to travel with them and swears.