54
8
In the game of Freecell, you are tasked with building four foundation piles in suit from ace to king, on a layout where you build downward in alternating colours. However, you can only build one card at a time, so you are given four "free cells" each of which can contain one card to help you move entire sequences. The idea is that you weave individual cards in and out of the free cells as required to help you solve the game.
Your task is to build a program that will solve these games in the fewest moves possible.
Your program will take as input a sequence of 52 cards, in the following format:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Which will be dealt in the initial layout in this order:
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52
And return a list of moves to solve the game. Each move will be in this format:
- A number representing the pile number (
1through8), or a free cell (AtoD), representing the source pile. - Another number or letter representing the destination pile or free cell, or
Ffor the foundation of that suit.
The output will look something like this:
18 28 3A 8B 8C 85 B5 35 4F etc.
Once a card is put into the foundation, it cannot be removed. Since only one card is moved at a time, moving a sequence of 3 cards requires 5 moves, and a sequence of 5 cards requires 9 moves.
If a game is unsolvable, your program should indicate as such. However, your program must be able to solve any solvable game.
Your program will be judged on the 32,768 deals found in the original Microsoft FreeCell program. In order to be valid, your program must successfully solve every deal except deal #11,982, which is unsolvable. Your score will be the total number of moves it takes to solve these 32,767 deals, with shorter code being a tie-breaker.
A file with all the decks in the format required by the above specification is available for download here (5.00 MB file): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
Joe Z.
Posted 2015-01-03T18:47:25.657
Reputation: 30 589
1Now I just need to nab the random number generator that they used to generate those 32,768 games. :S – Joe Z. – 2015-01-03T18:49:00.337
3
The generator is here: http://rosettacode.org/wiki/Deal_cards_for_FreeCell
– nutki – 2015-01-03T19:25:55.040Thanks, nutki. Lemme generate a text file with the decks in them, for testing. – Joe Z. – 2015-01-04T01:37:07.043
It would be nice if your example input sequence included at least one ace. – n8chz – 2015-01-24T22:21:08.410
Oh, sorry, aces are A. – Joe Z. – 2015-01-24T23:37:20.077
A quick question: Must the code handle the free cells as four separate "slots" or can the free cells be seen as a "stack" of max 4 cards? Codewise it would be unnecessary complicated to check which of the four slots is empty when that sub-problem can be reduced to wether any of the slots is free. Output-wise, the only changes would be that putting a card to the free cell would be i.e. "1C", "2C" instead of "1C1" or "1C2" or "1C3" or "1C4", the solution would still be valid. – Lars Ebert – 2015-03-18T10:49:12.063
1That's a good point. How would you deal with the case in which, say, two cards of the same colour and number (such as 7C and 7S) are both in free cells? Then if you move from "C" to a black 8, it could be either of those two cards. – Joe Z. – 2015-03-18T15:14:56.323
I think this problem has much larger hurdles than worrying about how to golf a few more bytes due to how the free cells are treated. That could be done with a bit field showing whether a cell is occupied, or perhaps representing the free cells as a 4-byte string and searching for the first blank, or some other creative method. – GuitarPicker – 2016-07-20T12:49:38.690
1.@Lars Ebert: The free cells are no 4-card stack but four 1-card.2.@Joe Z.: How about naming them A,B,C,D instead of C1..C4? I consider that easier to read. – Titus – 2016-07-20T13:45:19.160@Titus That would work, actually. – Joe Z. – 2016-07-25T04:36:19.177
2You could possibly get some answers by removing the restriction that all solvable deals must be solved by the submission. Then, score based on number of deals solved, then by fewest moves. – mbomb007 – 2017-02-16T21:59:36.280
Is Freecell a solved game, at least from all valid starting positions? If so, this is... well, not trivial, but fairly simple. If not, I'd rather not spend decades proving that it's the fewest possible moves. – Fund Monica's Lawsuit – 2017-03-02T01:06:18.503
Of interest: FreeCell solutions to 1000000 games
– Guy Coder – 2017-03-15T19:15:17.370It's hard to understand from your description - how does that array relate to any of the piles? Do the rows (or the columns) each represent a pile? Or something else. It's also very unclear what the valid moves are - I think it would help to show some examples (with "before" and "after" grids) showing representative valid and invalid moves. It might help if you can link to a reference site, as it's probably not a very widely played variant. – Toby Speight – 2017-04-06T13:15:05.853
Freecell is a solved game, thus it is known that there are unwinnable layouts. E.g. seed 11982 on the Windows version. – Draco18s no longer trusts SE – 2017-05-10T20:05:20.237
1can the cards be 0-Indexed? – tuskiomi – 2017-07-11T15:45:31.247
Can the "10" card be represented by a
Tinstead of a10? That way, each individual card (AS,2C) is two characters (TH) instead of sometimes three (10H). – Brian J – 2017-07-25T16:15:02.960@mbomb007 nah. Been there done this – Christopher – 2017-08-21T00:12:14.667
Do we really need to solve every one? It took 2 days to solve the first ~700 – Christopher – 2017-09-06T21:50:30.103
Here´s a solution (including C source and a JavaScript port): http://fc-solve.shlomifish.org/. Idk if it´s really fewest moves, but it´s pretty good.
– Titus – 2017-09-11T20:52:46.650