The least appealing thing (to me, at least) about solitaires is the amount of randomization that keeps them going: while randomization is really common in multiplayer games, too, many of them relinquished any form of randomization in favor of a more competitive gameplay, more aimed to rewarding the better player (see Chess).
The reason this is doable in multiplayer is that there is an opponent who can think and counter your moves, while we lack that in solitaires.
As of that, my favourite kind of solitaire is Perfect Information Solitaire (PIS). PIS are, essentially, puzzles: you get a starting board that you have to solve. Just for reference, Sudoku is a PIS and Lights Out is a PIS, too.
However, as you can see, those two have a striking difference: the set-up.
Sudoku needs someone to study the board beforehand, to check it's legal, solvable and only has 1 solution (I'm also putting in this category stuff like Chess Solitaire, that have a relatively small number of starting boards pre-designed); on the other hand, Lights Out can be freely randomized to have a starting board that requires no checking (actually, there are a couple of unsolvable boards, but you can work out your starting board by randomly pressing on the buttons and obtain a legal board the same you'd do with shuffling a rubik's cube).
The latter is what I'm aiming to: the objective of this thread is to think up some PIS that have randomized starting boards to enhance replay value by having almost infinite starting boards.
The biggest problem with designing one of those is the math behind it: as you can see, even in Lights Out not all the boards are solvable, and as such you cannot just randomly decide which slots to have on and which off, but have to rely on the mechanical system to backtrack the solution to the starting point. This isn't always doable, though, because sometimes it might actually spoil the fun if you don't have such a mechanical way to randomize but have to think in order to apply the rules and because backtracking isn't always possible at all.
As of now, I've only been able to think about two concepts:
1. Equalize: roll some dice, then line them up. The objective is making them all threes in the least amount of moves and/or time possible. You do so by picking one die, increasing or decreasing it and, respectively, decreasing or increasing the adjacent dice.
2. Playstyle: this is really only a concept and have yet to find a game to implement this in, but the idea is to have an AI that follows a certain playstyle (which means, some rules in regards to how it plays the game. I kind of dislike playstyles like "aggressive" or "defensive" in which the player arbitrarily decides whether a play fits that playstyle or not). To increase the amount of playstyles available, a playstyle should be the combination of 3 (or more) "traits" (the rules that make up the playstyle).
What do you think about PIS? Do you have any idea or can think of an existing boardgame that fits the points?
I guess you are interested in a challenging abstract puzzle that the player can generate easily on their own in a few seconds.
Some random thoughts:
1. I like the idea of generating the puzzle with dice. I think making a 4 by 4 grid with the dice or a 5 by 5 grid might make a nice starting position for some type of game. Dice are a fast generator of random starting positions.
2. I don't like the idea of counting the least number of moves to do something as the victory condition . Better is a countdown where you have a move limit or you lose. Or better still is something bad is growing in your game while you are trying to achieve your goal. You need tension. Most games should come down to the wire.
3. A good solitaire should allow for clever combinations of moves. There must be some quality mental challenge.
4. The most interesting concept that I have seen is from a solitaire wargame called Peloponnesian War. In that game you play one side and try to win, If you do badly you are stuck with that side, if you do well then you are forced to switch sides. So you are playing against yourself.
5. Getting back to a dice grid...How about each number allows certain actions. For example: Raising a 2 to a 3 allows all the other numbers in a row to be reduced by 1. Or lowering a 1 to a 6 (1 loops to 6) allows all adjacent numbers to be increased by 1. Or whatever. Moves have to have good and bad. And allowed moves are determined by the board position.
Good luck with your project.
If you don't play freecell, you really ought to learn and play while you're working on this project. It's my favorite perfect information solitaire and doesn't require careful setup, just a regular deck of cards.
It does have some unwinnable permutations but many (I'd even say most) are winnable. The original windows distro all but 1 of the games was winnable. I'm not sure what percentage of all possible permutations was included but freecell is a game that you can randomly generate with a high degree of confidence that if you lose it was your fault.