[Unofficial] 15 puzzle - 4.672 average of 12, 4.319 average of 5 (ben1996123)

[Noahaha]

Why aren't all the programs using random state? It sounds like it should be easy. I wrote a sim in Excel (vba) which was random state scrambling, although I didn't investigate how to identity parity so it's not quite complete.

Generate Random state.
Check for parity.
If parity then generate again. Etc.

Why not just switch two pieces?

But yeah, I agree with that. I made one like that once.

EDIT: I can't find it now, but I found a page a while back that gave a simple algorithm for checking for parity.

EDIT2: Found it!

 

[TDM]

On 15 puzzle? I very much doubt that that happened with a proper scrambling algorithm (the probability of a solved scramble is about one in 10^13). It is almost guaranteed that you found a bug, or that the program you were using just had a bad scrambler. Something like "do X random moves" may look decent most of the time but will occasionally generate very poor scrambles.

EDIT: If it was on Ben's sim, it must have been on an old version (the new ones don't allow solved scrambles, since like v12.3) and also involved some other bug (making the program think you were doing a solve when you weren't).

Yea, I think it was on an older version. I remember it was a while after he said he'd removed solved as a 2x2 scramble though. Not sure if it was since v12.3 or not.

But I still hold the 3 puzzle UWR!

Doesn't everyone?

 

[Stefan]

It's not that difficult. Something simple like this should return a solveable random-state scramble. Just keep track on how many switches (2-cycles) you made.

A={1,2,3,...,15}
switchCnt = 0
for (i = 0, i < 13, i++){
   j = random(i, 14)
   switch(A[i],A[j])
   if (i != j)
      switchCnt++
}
if (switchCnt%2 == 1)
   switch(A[13],A[14])
return A[/QUOTE]

Where do you handle the space at all?

Instead of "switchCnt++" you could do "switch(A[13],A[14])" right there and then don't need to do that in the end.

(And in what language is "{1,2,3,...,15}" not an [u]unordered[/u] set?)

 

[Jakube]

Where do you handle the space at all?

Oops, completely forgot about the space. My code returns a valid 15-puzzle in which the space is at the position 16.

(And in what language is "{1,2,3,...,15}" not an unordered set?)

In C++ you can initialize an array in this way.

int A[15] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

 

[Stefan]

In C++ you can initialize an array in this way.

int A[15] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

Oh right... apparently I haven't written C++/Java for so long that I forgot. And it's one more reason to dislike them, as it contradicts math notation

 

[KongShou]

Oh right... apparently I haven't written C++/Java for so long that I forgot. And it's one more reason to dislike them, as it contradicts math notation

Whats your main language then?

 

[Carrot]

It's not that difficult. Something simple like this should return a solveable random-state scramble. Just keep track on how many switches (2-cycles) you made.

A={1,2,3,...,15}
switchCnt = 0
for (i = 0, i < 13, i++){
   j = random(i, 14)
   switch(A[i],A[j])
   if (i != j)
      switchCnt++
}
if (switchCnt%2 == 1)
   switch(A[13],A[14])
return A

A={1,2,3,...,16}
switchCnt = 1
for (i = 0, i < 13, i++){
   j = random(i, 14)
   switch(A[i],A[j])
   if (i != j)
      switchCnt++
}
j = 2*random(0, 8)+(switchCnt%2)
switch(A[15],A[j])
return A

That should solve the blank spot ;-)

 

[Jakube]

A={1,2,3,...,16}
switchCnt = 1
for (i = 0, i < 13, i++){
   j = random(i, 14)
   switch(A[i],A[j])
   if (i != j)
      switchCnt++
}
j = 2*random(0, 8)+(switchCnt%2)
switch(A[15],A[j])
return A

That should solve the blank spot ;-)

There's still a problem. With this code, you can't generate the valid state 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Space 15 (which you can solve with one move).

 

[Owen]

Forgive my ignorance, but how can you detect parity from an arbitrary position?

 

[BoBoGuy]

Wow.

 

[qqwref]

Forgive my ignorance, but how can you detect parity from an arbitrary position?

My way is to just move the space to the bottom right (with actual moves) and then check the parity of the remaining permutation. That should be equivalent to the parity of the permutation of 16 pieces + the parity of the number of moves from bottom right the space is.

 

[Stefan]

I [post=906615]posted[/post] a short simulator recently, the scrambler basically was:

[noparse]A = [1, ..., 15, ' ']
for i = 2 to 15:
  r = random from {0, ..., i}
  if r<i and (i<15 or r%2==r/4%2):
    swap A[0] and A[1]
  swap A[i] and A[r]
[/noparse]

Stefan: according to Ben, his scrambling algorithm does a large number of random 3-cycles (~3-4 times the number of pieces).

Meh. Don't know how bad that is, but I don't trust it. Why do such an ugly hack when it can be done properly?

Whats your main language then?

Python.

 

[antoineccantin]

I [post=906615]posted[/post] a short simulator recently, the scrambler basically was:

[noparse]A = [1, ..., 15, ' ']
for i = 2 to 15:
  r = random from {0, ..., i}
  if r<i and (i<15 or r%2==r/4%2):
    swap A[0] and A[1]
  swap A[i] and A[r]
[/noparse]

It's not working for me...

 

[Stefan]

It's not working for me...

What do you mean? "Doesn't work" isn't very helpful.

Edit: I just implemented it in Python, looks fine to me (also already in the original javascript implementation, which I believe to be equivalent):

Try it and see output on http://ideone.com/VRANNB

import random
for s in range(10):

  A = range(1, 16) + [' ']
  for i in range(2, 16):
    r = random.randint(0, i)
    if r<i and (i<15 or r%2==r/4%2):
      A[0], A[1] = A[1], A[0]
    A[i], A[r] = A[r], A[i]
  print A

 

[qqwref]

Since this topic has been bumped, I feel it's worth it to point out that since a few weeks ago Ben has done many updates to the sim, and one of them was to implement the transposition style of scrambler Stefan mentioned.