I suspect they have either a massive database of proven-winnable shuffles, or before the game presents a new deck to you, it solves it in the background to prove it's winnable.

Personally I dislike this feature. Yeah it sucks to get an unwinnable shuffle, but that's just how card games work. Ensuring every game is winnable just seems like addiction engineering when it's next to the Microsoft logo.

Part of the fun is the uncertainty that a game is possible to win. If you know up front that a deck is guaranteed solvable, it really colors how you play the game.

There's an assumption with computer card games that the computer shuffles the deck once just like a real card game but that doesn't have to be true on the computer if you don't want it to be

Now, any reasonable player would notice if you reshuffle the deck in solitaire, but you could swap around the face down cards without any problem. You could have just one stack of face down cards in memory and always pop from the top when a card is flipped

Edit: Maybe this wouldn't be winnable 100%, but you could certainly nudge every hand towards being winnable