Patience Accordion problem suggestion

According to Wiki on Accordion (card game): "The odds of winning have been estimated as being around one in a hundred." So no wonder that you have not won a game yet ... :)

But rather that starting from a random position, the inital setup could be chosen in a way that a solution exists.

Friends, Hi and sorry for delay!

Thanks for suggestion. I played it a bit - and even have won once (out of dozen or more games). However I don't have idea about algorithmic solution too. Adding such problem doesn't require solving it, of course, but I'm not sure it is correct, until we know some good approach exists, at least heuristic.

being around one in a hundred.

To Mathias - thanks for the link to wiki. I found they describe different games really. It looks like original version is "automatic", with obligatory moves and so doesn't give freedom of choice to the player.

That version in "Aisle Riot" is different since it creates great "search-tree" of moves. Upon my small experience I feel there may be more than one ways to win (if initial setup is winnable) but at the same time much more opportunities to make wrong move (which may become obvious only later).

Probably algorithm could employ some rule to choose good moves and avoid bad ones (since I don't think bruteforce is feasible). But it's just a vague idea.

So returning to implementing this as a problem - I'd prefer to wait that any of us - perhaps our guru-colleagues - say "I have an idea (or a hope of idea) and want to try it" :)

BTW googling immediately gives online version of the game for everyone to try:

Accordion Solitaire online

P.S. I don't know where this 1/100 comes from - just have tried implementing "automatic" older version of the game - it looks like winning chances lay anywhere between 1/200 and 1/5000. But it may yet depend on rules of obligatory moves (their precedence is not 100% clear and may be user decidable).

I obviously miss some obvious idea. Or perhaps my thoughts on the problem tend to incline to some very wrong direction. If there is possible some very slight hint, it is much appreciated!

Sometimes it might not matter what order you make particular moves in. Could that help to reduce the search space?

You have the initial state; you have a way to generate all legal next states; the way you reach a particular state doesn't matter, only the state itself does; and you have a way to check if you are in an exit state. To me, this suggests a certain family of algorithms.

Also, since all solutions will have the same number of moves, there is no need to invest in the algorithm that guarantees to find the shortest solution.

Having read the previous two comments I began to suspect that there was an aspect of this problem that I had completely mis-judged. In any solution where backtracking is employed it is vital to avoid making the same sequence of moves over and over again (albeit in a different order each time). There is considerable scope for making this error in this problem; hence the comment from Mathias. It makes sense to concentrate on distinct states of the system; as suggested by Vladimir. At this point we appear to have a major problem. The number of distinct states is absolutely enormous! There is no possibility of keeping track of more than a very tiny fraction of them. Just for curiosity I took one of the 15 card example problems and generated all of the distinct states. There were 131,041 of these. I didn't attempt to do the same for a 28 card problem because my computer would clearly run out of memory long before getting anywhere near the total.

Add to this the fact that a previous post on the site suggested that a typical 52 card game (with a random deal) has only a 1% chance of being soluble. (Although I am sure that I have heard that this is more like 1 in 3 or 33%.) Clearly the puzzles on CodeAbbey are guaranteed to be soluble since they have been generated backwards from the finish. However, the statistics from random games suggests that there are likely to be only a small number of distinct solutions to any one of these puzzles (this assumes that we regard two solutions as the same if they differ only in the order of the moves). With a colossal number of distinct states and small number of distinct solutions it seemed that the only way forward was to devise a very good strategy for choosing the next move from the current selection of available moves. Combining this with distinct states would hopefully solve the problem. The fact that 5 people had already solved it also suggested that this approach was going to work.

When I read Vladimir's comments there was no hint that a sophisticated move choice was necessary, or that there was a problem with the huge number of distinct states. I began to suspect that I had been completely wrong in my assessment of the number of solutions. I returned to my own solution to the problem and replaced the move choice algorithm with one which simply selected moves in the order that they were found. I was amazed to find (using ordinary Python) that this approach went through puzzles up to 70 card size very quickly. It only began to struggle with 80 cards. I added a count of distinct states visited and discovered that this was surprisingly small. The obvious conclusion is that the number of distinct solutions is very large; such that it is very easy to find one of them. I looked again at the 15 card problem and discovered to my amusement that the solution could end with any one of 13 cards as the final card. It is obvious that neither of the first two cards can become the final card so it is possible to find solutions where any one of the remaining cards can be chosen to become the final card.

I now find that I do not believe the claims for a random deal of a 52 card pack. I suspect that the chance of this being soluble is very close to 100%. It clearly cannot be exactly 100% because it is a trivial exercise to deal the cards manually in such a way that there is no valid first move.

I think you are right, and the wikipedia article referenced earlier seems to have this very wrong (or I am missing some important detail). A quick simulation with shuffled decks (I learnt about random.shuffle()) suggests that they are almost always solvable, just as you argue. Furthermore, this research paper from 2019 (https://arxiv.org/pdf/1906.12314.pdf) states that Accordion is "very close to 100% solvable".