You are on the right track I think. Perhaps half the party the thinking part of the party is abducted by a wizard or some such npc. They are trapped in their dungeon, lair, castle whatever. Now they have several oppurtunities to try to free themselves, they just have to come up with ways to do it. Once they are free of confinement, perhaps halls filled with traps and the like twart their attempts at simply just running away. Give them some time to come up with ways to get around the clever traps. Perhaps if the traps get them, they incapacitate the pcs rather then killing them.
The pcs wake up, once again in their cell, only this time it is harder to escape, repeat as necessary.
The other half has to find some clue that would lead them to where the pcs are being held, and they simply have to fight there way into the area where the pcs are being held. This could include minions, monsters, and of course the big boss guy who started the whole event.
The problem is keeping one half of the party interested while the other party is playing. Not too hard for the puzzle people, they will need time to consider, but making the fighters wait while the puzzle players are playing, could lead to distraction.