如何用数字填充方形二维数组,以便从1到(edge length)2？创建一个按升序排列的连续数字的(随机)路径？
我正在尝试用JavaScript 编写一个Hidato(又名Hidoku)生成器.它不一定是最好的语言,但这就是我目前正在使用的语言.游戏板最初只是部分填充.显示的唯一保证数字是路径中的第一个和最后一个数字.游戏的想法是通过网格(垂直,水平或对角)创建单个数字路径,以便有一个连续的上升数字链.由于考虑了对角线,链条可以重叠.
我被困在板子生成部分.有效的电网必须连续编号从去的(单,非分支)路径1来(grid size)2.我看了看,但发现没什么可能帮助的.是否存在路径跟踪算法,可以使用由连续数字组成的单个路径填充2D阵列？
我最初的,天真的方法是用值和交换值填充2D数组,直到网格是有效的Hidato拼图.这需要永远计算并且效率非常低,所以我放弃了这个想法.
我的下一个想法是使用回溯路径跟踪器用连续值填充网格,但是我不确定如何实现这样的跟踪器.生成一个路径很容易(选择一个随机的相邻单元格并移动到它直到2D数组已满),但我的问题是算法的"回溯性",或者其他一些方法来始终确保随机整个网格中连续数字的路径.我想过一个迷宫追踪器,但这并不涉及没有分叉或死路的单一路径.
我怎么能从这里开始？我应该考虑除路径跟踪器或其他类似算法之外的其他选项吗？
相关问题:
从这篇维基百科文章:
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
在大多数图上快速的哈密顿路径的随机算法如下:从随机顶点开始,如果没有访问的邻居则继续.如果没有更多未访问的邻居,并且形成的路径不是哈密顿量,则随机均匀地选择邻居,并使用该邻居作为枢轴进行旋转.(即,向该邻居添加边缘,并从该邻居中移除一个现有边缘,以便不形成循环.)然后,在路径的新端继续算法.
我不太明白这个旋转过程应该如何工作.有人可以更详细地解释这个算法吗？也许我们最终可以用更清晰的描述更新Wiki文章.
编辑1:我认为我现在理解算法,但它似乎只适用于无向图.任何人都可以证实吗？
这就是为什么我认为它只适用于无向图:
alt text http://www.michaelfogleman.com/static/images/graph.png
假装顶点的编号如下:
123
456
789
让我们说我到目前为止的道路是:9, 5, 4, 7, 8.所有8个邻居都被访问过.假设我选择5来删除边缘.如果我删除(9,5),我最终创建一个循环:5, 4, 7, 8, 5所以我似乎必须删除(5,4)并创建(8,5).如果图是无向的,那很好,现在我的路径是9,5,8,7,4.但是如果你想象那些边被定向,那不一定是有效路径,因为(8,5)是边但是( 5,8)可能不是.
编辑2:我想对于一个有向图我可以创建(8,5)连接,然后让新路径正好4, 7, 8, 5,但这似乎适得其反,因为我必须砍掉以前导致顶点5的所有内容.