Next Permutation

Aim: Find a larger permutation

We must move a larger number forward. So we should go from the tail to find any new number is smaller than a number behind it. If no next permutation, reverse list.

more ...

24 Game Solver

24 game is an arithmetic game with a simple rule: Given 4 numbers and use + - * / to get 24.

  • A simple example is 1, 2, 3, 4, and you find 1*2*3*4=24
  • A more difficult one is 5, 5, 5, 1, the answer is 5*(5-(1/5))=24, which includes fractions.

24game project provides a powerful C++ solver for the 24 game. And you can play with the PyQt5 based graphical front end.

more ...



拼图游戏之可解性条件

可解的必要条件

游戏中只能由不断的空块和相邻的块做交换完成。而可解性也由交换数的奇偶性决定,交换数定义为通过交换任意块使得其恢复原状需要的次数。

考虑包含空块在内的交换数:空格子移动一步的时候,进行了一次交换,交换数的奇偶性发生改变。显然最后的奇偶性取决于空格移动步数的奇偶性。而移动步数奇偶性不依赖于具体路径,只依赖于初末位置。我们可以找一条最简单的路径的长度(曼哈顿距离)的奇偶性来判断可解性。

必要条件 移动步数奇偶性必须等于排列数/交换数的奇偶性

more ...