二十四点游戏求解算法设计

问题

给定4个10以内的正数，要求使用加、减、乘、除运算得到24，其中每一数必须用到一次，而最多也只能用一次。

例如，给定的四个数为6、8、8、9，则

8*9-8*6=24

这一游戏可以采用扑克牌来玩。如果事先将花牌全部抽走，数的范围就限制在1到10之间；加上花牌一起玩时，一般将J作为11，Q作12，K作13。从趣味性来看，抽走花牌要好完一些，因为大部分人对两位数乘除运算的心算能力较弱。且对于4个1到10之间的数，很少有算不出24来的时侯。

问题分析

下面我们来考虑玩24点游戏的程序。

首先将4个数可能的算式归纳为5类:

((b0 op0 b1) op1 b2) op2 b3

(b0 op0 (b1 op1 b2)) op2 b3

(b0 op0 b1) op1 (b2 op2 b3)

b0 op0 ((b1 op1 b2) op2 b3)

b0 op0 (b1 op1 (b2 op2 b3))

其中b0、b1、b2、b3是4个数的一种可能的排列，op0、op1、op2代表一个算术运算符，它可以是加、减、乘、除运算之一。

由于容许除法运算，计算结果将出现分数。因此，我们用分数来表示参加运算的每一个数，例如，2可以表示为2/1，中间结果和最后结果也用分数表示。分数的加、减、乘、除运算定义为:

(a/b)+(c/d)=(ad+bc)/bd

(a/b)-(c/d)=(ad-bc)/bd

(a/b)*(c/d)=ac/bd

(a/b)/(c/d)=ad/bc

问题求解程序的基本思想是：对于4个输入数的每一种排列、对于每一类算式、对于每类算式中三个运算符的全部可能情况进行枚举，然后对每一个具体的表达式计算其值，看看结果是否24。若结果不是24，就试探下一种情况，直到找到一个解或全部情况都判断完为止。由于全部可能的算式数为4！（4个数的排列数）×5（算式种类数）×4 ³（每种算式中运算符的可能情况数）＝7680，因此程序的时间开销非常小。

C程序

// File: Game24.C

#include "AIProb.h"

#define OPERAND_NUM 4

#define MAXOPERAND 13

typedef struct tagFRACT

{

int m;

int n;

} FRACT;

char OpName[]={'+', '-', '*', '/'};

FILE *fp;

////////////////////////////////////////////////////////////////////////////

// Function Prototypes

BOOL SearchSolution(int *a, BOOL bFindAll);

FRACT FractCalc(FRACT oprand1, int op, FRACT oprand2);

void GenExpress(int nExpressType, int *b, int op1, int op2, int op3);

////////////////////////////////////////////////////////////////////////////

void main()

{

int nSuc, nTotal;

int a[OPERAND_NUM];

BOOL bRet;

fp = fopen("game24.dat", "w");

for (i = 0; i < OPERAND_NUM; i++)

{

fprintf(fp, "Input the %d operand:", i+1);

scanf("%d", &a[i]);

}

nSuc = 0;

nTotal = 0;

for (a[0] = 1; a[0] <= MAXOPERAND; a[0]++)

for (a[1] = a[0]; a[1] <= MAXOPERAND; a[1]++)

for (a[2] = a[1]; a[2] <= MAXOPERAND; a[2]++)

for (a[3] = a[2]; a[3] <= MAXOPERAND; a[3]++)

{

//bRet = SearchSolution(a, TRUE); // Find all solutions

fprintf(fp, "Four operand: %d,%d,%d,%d.", a[0],a[1],a[2],a[3]);

bRet = SearchSolution(a, FALSE); // Find a solution

nTotal++;

if (bRet == FALSE)

fprintf(fp, "There is no solution/n");

else

nSuc++;

}

fprintf(fp, "------------------------------------------------------------/n");

fprintf(fp, "Total = %d, Success time = %d/n", nTotal, nSuc);

fprintf(fp, "Successful rate=%f/n", (float)nSuc/ (float)nTotal);

fclose(fp);

}

BOOL SearchSolution(int *a, BOOL bFindAll)

{

int b[OPERAND_NUM], p[OPERAND_NUM];

int i, j, n, t;

int lo, hi;

FRACT oprand, res, res1, res2;

int k;

BOOL bNoFind;

int op1, op2, op3;

k = 0;

bNoFind = TRUE;

// Generation a permutation and test

n = OPERAND_NUM;

for (j = 0; j < n; j++)

p[j] = j;

while (bNoFind || bFindAll)

{

// Generate a permutation of the four operands

for (j = 0; j < n; j++)

b[j] = a[p[j]];

// Test if there is a solution refer to as the operands order

for (op1 = 0; op1 < n && (bNoFind || bFindAll); op1++)

for (op2 = 0; op2 < n && (bNoFind || bFindAll); op2++)

for (op3 = 0; op3 < n && (bNoFind || bFindAll); op3++)

{

/* ((b0 op1 b1) op2 b2) op3 b3 */

res.m=b[0];

res.n=1;

oprand.m=b[1];

oprand.n=1;

res=FractCalc(res,op1,oprand);

oprand.m=b[2];

oprand.n=1;

res=FractCalc(res,op2,oprand);

oprand.m=b[3];

oprand.n=1;

res=FractCalc(res,op3,oprand);

if (res.m > 0 && res.m == 24 * res.n)

{

bNoFind=0;

GenExpress(0,b,op1,op2,op3);

}

/* (b0 op1 (b1 op2 b2)) op3 b3 */

res.m=b[1]; res.n=1;

oprand.m=b[2]; oprand.n=1;

res=FractCalc(res,op2,oprand);

oprand.m=b[0]; oprand.n=1;

res=FractCalc(oprand,op1,res);

oprand.m=b[3]; oprand.n=1;

res=FractCalc(res,op3,oprand);

if (res.m>0 && res.m==24*res.n && (bNoFind || bFindAll))

{

GenExpress(1,b,op1,op2,op3);

bNoFind=0;

}

/* (b0 op1 b1) op2 (b2 op3 b3) */

res1.m=b[0]; res1.n=1;

oprand.m=b[1]; oprand.n=1;

res1=FractCalc(res1,op1,oprand);

res2.m=b[2]; res2.n=1;

oprand.m=b[3]; oprand.n=1;

res2=FractCalc(res2,op3,oprand);

res=FractCalc(res1,op2,res2);

if (res.m>0 && res.m==24*res.n && (bNoFind || bFindAll))

{

bNoFind=0;

GenExpress(2,b,op1,op2,op3);

}

/* b0 op1 ((b1 op2 b2) op3 b3) */

res.m=b[1]; res.n=1;

oprand.m=b[2]; oprand.n=1;

res=FractCalc(res,op2,oprand);

oprand.m=b[3]; oprand.n=1;

res=FractCalc(res,op3,oprand);

oprand.m=b[0]; oprand.n=1;

res=FractCalc(oprand,op1,res);

if (res.m>0 && res.m==24*res.n && (bNoFind || bFindAll))

{

GenExpress(3,b,op1,op2,op3);

bNoFind=0;

}

/* b0 op1 (b1 op2 (b2 op3 b3)) */

res.m=b[2]; res.n=1;

oprand.m=b[3]; oprand.n=1;

res=FractCalc(res,op3,oprand);

oprand.m=b[1]; oprand.n=1;

res=FractCalc(oprand,op2,res);

oprand.m=b[0]; oprand.n=1;

res=FractCalc(oprand,op1,res);

if (res.m>0 && res.m==24*res.n && (bNoFind || bFindAll))

{

GenExpress(4,b,op1,op2,op3);

bNoFind=0;

}

// Find the rightmost place where p[i] < p[i+1]

i = n - 2;

while (i >= 0 && p[i] > p[i+1])

i--;

if (i < 0) break;

// Find p[j], the smallest element to the right of p[i] and

// greater than it.

j = n - 1;

while (p[i] > p[j])

j--;

// Interchanger p[i] and p[j]

t = p[i];

p[i] = p[j];

p[j] = t;

// Reverse p[i+1],...,p[n-1]

lo = i + 1;

hi = n - 1;

while (lo < hi)

{

t = p[lo];

p[lo] = p[hi];

p[hi] = t;

lo++;

hi--;

}

return 1 - bNoFind;

}

FRACT FractCalc(FRACT oprand1, int op, FRACT oprand2)

{

int m1,n1,m2,n2,m,n;

FRACT res;

m1=oprand1.m;

n1=oprand1.n;

m2=oprand2.m;

n2=oprand2.n;

switch (op)

{

case 0:

m=m1*n2+m2*n1;

n=n1*n2;

break;

case 1:

m=m1*n2-m2*n1;

n=n1*n2;

break;

case 2:

m=m1*m2;

n=n1*n2;

break;

case 3:

m=m1*n2;

n=n1*m2;

if (n < 0)

{

n=-n;

m=-m;

}

break;

}

res.m=m;

res.n=n;

return res;

}

void GenExpress(int nExpressType, int *b, int op1, int op2, int op3)

{

switch (nExpressType)

{

case 0:

fprintf(fp, "((%d%c%d)%c%d)%c%d=24/n",