当前在线人数8408
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: 8-puzzle
[同主题阅读] [版面: 葵花宝典] [作者:blaze] , 2005年02月03日18:22:25
blaze
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: blaze (blaze), 信区: Programming
标  题: Re: 8-puzzle
发信站: Unknown Space - 未名空间 (Thu Feb  3 18:23:16 2005) WWW-POST

LOL, that seems not right to me.  But you have sharp eyes.

In fact, a general solution is as easy, which also works for
4x4 and 6x6. Just a better approach to linearization.  In my
last post I say from left to right and from top to bottom, which
is for the simplicity of presentation.  We can in fact do the
following:

For odd number lines from left to right, for even number lines from
right to left.  So this is like a snake shape.  For instance,

1 2 3
4 5 6
7 8

goes

1 2 3 6 5 4 7 8

This works for all cases, regardless of the shape and size of the
matrix at all.


【 在 Foxwell (大熊星座) 的大作中提到: 】
: I guess the following solution:
:
: Assume the dimension of matrix is n X n.
: Let m be the number of reversed pairs.
:
: if m is a multiplier of (n-1), it can be solved; otherwise not.
:
: so if it's true, blaze's method may only work for 3 X 3 matrices.
:
: I wish it was right. :-)
:
: 【 在 Foxwell (大熊星座) 的大作中提到: 】
: : Yes, your method works for 3X3, 5X5, ... matrices,
: : but how about 4X4, 6X6 ... matrices?
: :
: : Thanks.
: :
: : 【 在 blaze (blaze) 的大作中提到: 】
: : : This is an interesting question and I thought about
: : : the same 11 years ago.
: : :
: : : In fact there is a simple way as follows.  You linearize
: : : the numbers in the matrix from left to right, and top to
: : : bottom to obtain a sequence.  Then you see the parity of
: : : this sequence.  If it is even, then there exists a solution,
: : : otherwise not.
: : :
: : : The parity of a sequence is a standard notion, which is defined
: : : as the parity of the number of the reverse orders in a sequence.
: : : For instance, for the sequence
: : :
: : : 1, 2, 3, 4
: : :
: : : the number of reverse orders is 0.  For the sequence
: : :
: : : 4, 3, 2, 1
: : :
: : : the number of reverse orders is C(4, 2) = 6. For the sequence
: : :
: : : 1 3 2 4, the number of reverse order is 1 (resulting from the
: : : 3 2).
: : :
: : :
: : : 【 在 TonnyZB (Hallo) 的大作中提到: 】
: : : : Since not every initial configuration has a solution (only 9!/2 are
: : solvable),
: : : : is there a way to efficiently search if the initial configuration is
: : solvable
: : : : or not?
: : : : Are there some deep thoughts in the 8-puzzle problem, or can we make
the


--
剑在手,问天下谁是英雄。

※ 修改:·blaze 於 Feb  3 18:23:16 修改本文·[FROM: 128.197.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 128.197.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996