2

我想创建一个小型 Jumbler 游戏。我打算使用 Java 编程语言来制作这个游戏。以下是游戏的小屏幕截图。我找不到包含此游戏的任何其他网站。

页面末尾的游戏截图

在这个游戏中，我想添加两个功能。

1. Manually solve the problem.
2. Automatically solve the problem.

手动解决问题

意味着我们玩游戏并找到解决方案以使数字按升序排列

直观地解决问题

表示计算机以图形方式显示解决方案所需的最少移动次数。这意味着计算机以图形方式显示运动并以最少的运动识别解决方案。

那么如何编程这种情况呢？

我在互联网上搜索并获得了一些与线性编程相关的教程。为了解决这类问题，我应该学习什么？我不知道如何解决自动解决方案。请提供一些好的教程，让我可以轻松掌握。

4

2 回答 2

1

When all you've got is a hammer, everything looks like a nail - so I'd say that this type of problem can be solved using constraint programming. But that's just what I've got a little experience in.

Basically, you have a board layout, and there are a small number of valid moves at each 'step'. The aim is to move into a known layout (ascending order).

To do this 'automatically', you need to have the program search for a solution path. The steps to do this are something like this:

  1. From the current layout, determine the valid moves.
  2. Calculate the layout after taking each of the valid moves.
  3. Check if any of the calculated layouts is the solution; if it is, you're finished.
  4. If none of the moves resulted in the solution, work out all the newly-valid moves, and repeat from 1.

You'll have some issues doing this. Firstly, memory constraints (making a bazillion copies of your board layout might not work). Secondly, time/computational constraints (it might take a long, long time to find a solution). There are some things you can do to at least minimize the damage from these issues.

  1. Choose a good search method. Breadth-first as opposed to Depth-first, for example. This will both decrease the time taken to find a solution and decrease the memory requirements.
  2. Some moves are "backwards". For example, moving square A to B, and then square B to A (repeating moves). Searching these 'loops' is both pointless and resource-wasting, so you'd want to ensure you don't do that.
  3. There is the possibility of symmetries in the search space. I haven't solved your particular problem, and I couldn't give you examples specific to you, but the n-queens has a nice section on symmetries specific to that problem - it might be worth a read if you're trying to find symmetries in your problem.

That might give you some information, or thoughts to start looking.

于 2012-08-01T14:37:35.710 回答
0

我不知道我是否明白...

最小发生率和最小路径是一个动态规划问题

http://en.wikipedia.org/wiki/Dynamic_programming

简而言之，您必须计算所有解决方案并显示更好的解决方案。动态编程并不是那么容易理解和开发，但你可以尝试...

但是，我建议您记住如何混合它并展示该解决方案...

于 2012-08-01T09:46:40.407 回答