请教大家一种游戏的算法和代码，谢谢了

Tetris

做个游戏来玩谁不会啊……
这个题挺难的，我还没有想到启发式搜索时的评价方法。

Tetris

Post by doubleelec
那就再详细一点，一种盲目搜索算法：

首先，从初始状态开始，穷举所有可能的选择（这里没有考虑原题中的具体数据，假设0-8都可以选），可以得到 9 种新状态（如果有重复的要去掉，则结果少于 9 种），比较新状态是否目标状态。

然后，从每种新状态出发，穷举（假设0-8），又各得到 9 种新状态（如果与已经出现过的状态重复，要去掉，或称合并），比较新状态是否目标状态。

依次类推......形成一个图：状态就是图节点，如果从一个状态一步可以到达另一状态，这两个状态（节点）之间就有一条弧（有向的）。最终，会找到一个状态和目标状态一致。建立图的过程到此为止。

最后，在图上找到一条从初始状态到目标状态的路径，输出。如果用深度优先搜索并及时释放没用的路径也可以避免最后这一步。（完毕）


附：上面只是个粗略的过程，翻翻书还是有好处的。是你要解决问题，如果你都不想翻书，又怎能期望别人花时间帮你。

这个方法实现起来很简单，但时间和空间上都是指数复杂度，计算上可能无法做到。

macarthor

都是牛人诶

doubleelec

Post by Tetris
这个方法实现起来很简单，但时间和空间上都是指数复杂度，计算上可能无法做到。

至少表面上看这道题限制挺多的，应该复杂度不大。

以前我有同学用盲目搜索实现自动求解“华容道”，比这复杂得多，0.3秒搞定。

评估函数搞起来确实很难，因为每一步都有若干位置被“翻转”，到底如果是更接近目标的状态很难评价，弄不好可能是吃力不讨好的事。倒是在判断重复状态上多下点功夫会有比较明显的效果。