Comments for A Blog.

Comment on The hardest eight-puzzle instances take 31 moves to solve by Era Ahmadian

Era Ahmadian — Wed, 23 Nov 2011 07:08:16 +0000

Hi Solnit
we are working on an Optimezd Program which is solved 8 puzzle problem with A* algorithm and with OOP methods in C# .
Our Program Can solve the 31-depth instance easily!
but i have a question of you?!
why u said The hardest eight-puzzle instances take 31 moves to solve?how can u prove it?!
we have of instances that they needs more moves for solving!!!
and the second question is the reflection instances are the same state with every goals position or just the standard one?
truly yours,Era

Comment on The hardest eight-puzzle instances take 31 moves to solve by solnit

solnit — Tue, 16 Aug 2011 12:25:00 +0000

These two states are the same state really. Let’s take first position.

 8 6 7
 2 5 4
 3 . 1

You can reflect this position about main diagonal.

 8 2 3
 6 5 .
 7 4 1

Then you can rename pieces. More precisely, you can swap pieces 2-4, 3-7 and 6-8. It is because in goal state these pieces are symmetric.

 6 4 7
 8 5 .
 3 2 1

Note that this is second hardest position.
Now try to do the same two steps for, say, the following position:

Position A
 1 2 3
 . 5 6
 4 7 8

After reflection:

 1 . 4
 2 5 7
 3 6 8

After renaming pieces 2-4, 3-7 and 6-8:

Position B
 1 . 2
 4 5 3
 7 8 6

Position A can be solved in three moves: U L L (U means “move piece up”).
Position B also can be solved in three moves: L U U.
Moreover, solution to the position B can be obtained by replacing moves U,L,D,R with moves L,U,R,D respectively.
The following position is self-symmetric:

 . 8 7
 6 5 4
 3 2 1

If you reflect this position and then rename tiles you will return to the same position.

Comment on C++ callbacks into Java via JNI made easy(ier) by Timothy Wall

Timothy Wall — Sun, 07 Aug 2011 00:19:11 +0000

You should only detach if not already attached (pseudo-code follows):

attached = (*jvm)->GetEnv(…)
if (!attached) (*jvm)->AttachCrrentThread(…)

// do java callback

if (!attached) (*jvm)->DetachCurrentThread(jvm)

Comment on The hardest eight-puzzle instances take 31 moves to solve by Jason Wolfe

Jason Wolfe — Mon, 04 Apr 2011 18:52:49 +0000

There are only (9 !) / 2 = 181,440 reachable states in the 8-puzzle, so you should be able to solve any instance pretty quickly (on the order of seconds or less) even using brute force, with a decently fast implementation. Repeated-state checking (i.e., a closed list) and proper data structures are essential, of course.

Comment on The hardest eight-puzzle instances take 31 moves to solve by mimighost

mimighost — Mon, 04 Apr 2011 11:43:11 +0000

I got your blog from google.
This is indeed a very difficult puzzle, i wrote a python program and using the A* to solve it, and it takes a really long time.
So, my question is how long does it take for your program to find the answer? Is there any special optimization? I rsearch the web but can’t find many useful information.

Comment on C++ callbacks into Java via JNI made easy(ier) by Oty

Oty — Wed, 09 Dec 2009 12:36:17 +0000

Hi,

I had the same library. But after N call to java from C++ thread.
application crashed!

have you a idea.

Comment on Dynamic type hints in Clojure macros by Konrad Grzanek

Konrad Grzanek — Wed, 09 Dec 2009 08:28:46 +0000

Great advice. That’s exactly what I was searching for. Thanks !!!

Comment on Quick tip for debugging & profiling Clojure code with multimethods by Brandon Gray

Brandon Gray — Fri, 22 May 2009 02:27:07 +0000

This is a great tip for dealing with Clojure’s multimethods. One thing that I’ve found tough about Clojure are the sometimes cryptic compiler messages. Thanks for the info!

Comment on The hardest eight-puzzle instances take 31 moves to solve by Jason Wolfe

Jason Wolfe — Mon, 18 May 2009 06:25:41 +0000

Good point. The post was referring to the standard version where the final state is:

1 2 3
4 5 6
7 8 .

Comment on The hardest eight-puzzle instances take 31 moves to solve by Mati

Mati — Sat, 16 May 2009 23:27:31 +0000

But which is the final state for those puzzles?
Cause there are two disconnected parts in the search space for this problem.
Thx!