Permutations of the Fifteen Puzzle

Question

The Challenge

Consider the following diagram of the Fifteen Puzzle in its solved state:

_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

At every move, an excited puzzler has the opportunity to move one piece adjacent to the blank space into the blank space. For example, after 1 move, we have 2 possible scenarios (let 0 be a blank space):

1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

After 2 moves, the puzzle has 5 different outcomes (Note that the two cases above are excluded, since they cannot be reached in 2 moves). One of these situations is the original solved state, and can be reached in two different ways.

Your task in this challenge is to produce the number of different outcomes that a certain number of moves can lead to. As input, take a number N >= 0, and output the number of unique situations that may appear after N moves.

Rules

• This is code-golf. Shortest code wins!
• Standard loopholes are disallowed.
• Your code should be able to compute the case for N = 10 within a few minutes. I will likely not test this rule unless an obvious abuse of time exists in an answer.

Test Cases

(Results generated from summations of OEIS A089484 (As Geobits described in chat), automated by Martin Büttner's script. Thanks for all the help!)

0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356

Answer 1

Pyth, 36 bytes

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

Demonstration. Test harness.

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat <input> times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.

Answer 2

CJam, 54 52 51 50 49 47 45 bytes

G,ari{{:S0#S{4md2$4md@-@@-mh1=},f{Se\}}%:|}*,

Try it online in the CJam interpreter (should take less than 10 seconds).

How it works

G,a       e# Push R := [[0 1 ... 15]].
ri{       e# Do int(input()) times:
  {:S     e#   For each S in R:
    0#    e#     Push the index of 0 in S (I).
    S{    e#     Filter S; for each J in in S:
      4md e#       Push J/4 and J%4.
      2$  e#       Copy I.
      4md e#       Push I/4 and I%4.
      @-  e#       Compute (I%4)-(J%4).
      @@- e#       Compute (J%4)-(I%4).
      mh  e#       2-norm distance: a b -> sqrt(aa + bb)
      1=  e#       Check if the distance is 1.
    },    e#     Keep all values of J with distance 1 from I.
    f{    e#     For each J:
      S   e#       Push S. 
      e\  e#       Swap S at indexes I and J.
    }     e#     This pushes an array of all valid modifications of S.
  }%      e#   Collect the results for all S in R in an array.
  :|      e#   Reduce the outmost array using set union (removes duplicates).
}*        e#

Answer 3

Retina, 289 276 bytes

^
,abcd%efgh%ijkl%mnox,
(`(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,
,.{19},(?=.*1)|,[^,]{20},(?=[^1]*$)|y|1$

+)`([^,]{19})(.*),\1,
$1$2
[^a]

a
1

Takes input and prints output in unary.

You can put each line in a single file or run the code as is with the -s flag. E.g.:

> echo -n 111|retina -s fifteen_puzzle
111111111111

The core of the method is that we keep track of all possible positions (without repetition) which can occur after exactly k steps. We start form k = 0 and repeat the substitution steps (using the (` and )` modifiers) until we reach the input number of steps.

During this computation our string always has the form of

(,[puzzle_state]y?,)+1*

where puzzle_state is abcd%efgh%ijkl%mnox with some permutation of the letters. x stands for the empty place, the rest of the letters are the tiles. %'s are row delimiters.

y marks that the state is generated in the current step (k) so it shouldn't be used to generate other states in this step.

1's mark the number of steps left.

The basic mechanic of the Retina code is that every match of an odd line is changed to the next (even) line.

The code with added explanation:

initialize string
^
,abcd%efgh%ijkl%mnox,

while string changes
(`

for every old (y-less) state concatenate a new state with moving the empty tile to r/l/d/u if possible
right
(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
left
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
down
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
up
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,

if we should have made this step (there are 1's left) remove old states
,.{19},(?=.*1)

if we should not have made this step (no more 1's left) remove new states
,[^,]{20},(?=[^1]*$)

remove y markers
y

remove one 1 (decrease remaining step count)
1$


remove duplicates until string changes (with + modifier)
+`([^,]{19})(.*),\1,
$1$2    

end while
)`

remove non-a's, 1 a stays from each state
[^a]

change a's to 1's
a
1

10 bytes saved thanks to @MartinButtner.

Answer 4

Python, 310 253 243 229 bytes

Latest version with improvement suggested by @randomra:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:j=t.index(0);j%4and e(j-1,j);j%4>2or e(j,j+1);j<4or e(j-4,j);j>11or e(j,j+4)
print len(s)

My own version, which was longer (243 bytes), but easier to read:

s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:
  j=t.index(0)
  if j%4:e(j-1,j)
  if j%4<3:e(j,j+1)
  if j>3:e(j-4,j)
  if j<12:e(j,j+4)
print len(s)

Simple breadth first search, encoding the states as tuples, and storing them in a set to keep them unique.

Takes about 0.03 seconds on my laptop for N=10. Running time does increase substantially for larger numbers, for example about 12 seconds for N=20.

Answer 5

Perl, 148

#!perl -p
$s{"abcd.efgh.ijkl.mno#"}=1;for(1..$_){$x=$_,map{$r{$_}=1if
s/($x)/$3$2$1/}keys%s for
qw!\w)(# #)(\w \w)(.{4})(# #)(.{4})(\w!;%s=%r;%r=()}$_=keys%s

Example:

$ time perl 15.pl <<<20
2244884
real    0m39.660s
user    0m38.822s
sys 0m0.336s