Nearly every description of the game that I've read says redeals can be done "when no other moves can be made," but every computer implementation I've seen allows you to redeal at any time. Allowing redeals at any time certainly increases your options and improves your chances of winning the game. Sometimes the only way to win is by redealing when there are still movable cards.
You can read the rules for Cruel or play the game on Politaire.com or on many other websites.
This game resembles Indefatigable and Royal Marriage but is more difficult for human players. Those games allow building both up and down on the tableau. Redeals are done in a manner that more thoroughly disrupts the card order, collecting cards column by column, and dealing them dealt row by row. Only a limited number of redeals are permitted.
Note: Many people who play this game or create certain computerized versions thereof erroneously believe that the cards are "shuffled" by taking the last pile and putting it on top of the next-to-last pile and so on, then putting the bottom four cards in the first pile, the next four cards in the second, and so on. The technically correct order is to "shuffle" by taking the cards on the first pile, putting them on top of the cards from the second pile, then on top of the third, and so on, then taking the top four cards and putting them back in the first pile, then the next four cards in the second, and so on. Only about one in six to one in five people can win the game using the incorrect "shuffling" method; however, the chances of winning using the correct method are significantly higher, about one in three or two in five.The redeal method really does make a significant difference to the play of the game. Digging cards out from the bottom of the first column is always a challenge in Cruel. The example below shows the different result of a correct and incorrect redeal after one card has been removed from the first column:
The next image shows the results of the two redealing methods after one card has been added on top of the first column:
I find it easier to describe the correct algorithm as:
The anonymous author of the Wikipedia page includes estimated win rates for a human player of 33% to 40% with the correct dealing algorithm or about half that with the incorrect dealing algorithm. We'll analyze both options here.
If we use the alternate, bottom to top, deal order, then only 466,977 out of a million games were solvable, for a 46.7% win rate. Clearly the Wikipedia page was correct in saying that the game is much harder when it is played this way, and its estimate that it is about twice as hard was not far off.
My solver doesn't work well if we allow redeals to be done at any time, instead of only when there are no other moves to be made, but partial results are sufficient to indicate that allowing redeals at any time significantly improves the percentage of games that are winnable. I ran that version of the solver on 10,000 random Cruel deals (Politaire seeds 0 through 9999) and was able to solve about 87% of them. For most of the remaining games, the solver got lost in a combinatorial explosion and had to be terminated without a result. Less than 2% of the puzzles were conclusively proven to be unsolvable. This means the percentage of winnable games is actually somewhere between 87% and 98%.
To win games of Cruel, it is clearly important to chose the right moments to redeal, so that the redeal will bring cards you want to the surface. This is not too hard for a human player to do if you are only looking one redeal ahead, but looking ahead over multiple redeals quickly becomes nearly impossible. Thus the human player's win rate is going to fall far short of the theoretical maximum win rate.