24点游戏求解算法
2019-04-15 本文已影响10人
客昂康
24点游戏简介
一副牌中抽去大小王，从剩下的52张中任意抽取4张牌，用加、减、乘、除和括号把牌面上的数算成24，每张牌都必须使用，且只能用一次。举例如下：
【1】 1、2、3、4，那么1x2x3x4 = 24，4/(1/(2x3)) = 24，(1+2+3)x4 = 24等等。
【2】 4、6、8、10，那么(8-6)x10+4 = 24，(10-6)x4+8 = 24。
【3】 5、4、3、3，那么(5+4)x3-3 = 24，(5-3)x4x3 = 24，(3/3+5)x4 = 24等等。
求解算法
用穷举法列出所有算式，如果结果等于24则输出。那么如何穷举呢？
-
经过观察，无论什么样的算式，不管运算符顺序怎么样，不管括号怎么加，都可以用如下方法穷举：
【1】最开始是4个数，例如 6、7、8、9。
【2】从4个数中选择两个数，例如6和7。4选2共6中选法。
【3】将两个数进行加减乘除运算，例如加法运算，6+7。
【4】运算结果13和剩余的2个数8和9组成3个数，13、8、9。
【5】从三个数中选择两个数，例如13和8。3选2共3中选法。
【6】将两个数进行加减乘除运算，例如除法运算，13/8，或者8/13。
【7】运算结果和剩余的1个数组成2个数，例如13/8、9。
【8】最后一步加减乘除运算，例如乘法运算，13/8 x 9。
注意步骤【3】、【6】、【8】，因为加法和乘法符合交换律，不分顺序，所以一共6中四则运算。对于除法，还要检查除数是否为0。 -
例如上面提到的算式
(1+2+3)x4 = 24，可以看做：
【1】4个数1、2、3、4。
【2】选择1和2。
【3】选择加法。
【4】运算结果3和剩余2个数组成3个数 3、3、4。
【5】选择3和3。
【6】选择加法。
【7】运算结果6和剩余1个数组成2个数 6、4。
【8】选择乘法。 -
再举一个例子，例如算式
(11-3)/(5-7) = -4，可以看做：
【1】4个数3、5、7、11。
【2】选择3和11。
【3】选择后面的数减前面的数的减法。
【4】运算结果8和剩余2个数组成3个数 8、5、7。
【5】选择5和7。
【6】选择减法。
【7】运算结果-2和剩余1个数组成2个数 -2、8。
【8】选择后面的数除以前面的数的除法。 -
绘制个示意图：
C语言代码
实际代码中，对于求解算法的步骤【3】、【6】、【8】中的减法，只保留了较大的数减去较小的数的运算，丢弃了较小的数减去较大的数的运算。总的穷举次数也能算出来，6 x 5 x 3 x 5 x 1 x 5 = 2250 次。
//==============================================================================
// Copyright (C) 2019 王小康. All rights reserved.
//
// 作者: 王小康
// 描述: 24点游戏求解程序
// 日期: 2019-04-15
//
//==============================================================================
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct {
int integer;
int remainder;
int denominator;
char *string;
} VALUE_T;
static int level_3(VALUE_T *a, VALUE_T *b){
int va, vb, integer, remainder, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
integer = (va + vb) / denominator;
remainder = (va + vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s+%s = 24\n", a->string, b->string);
num++;
}
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
integer = (va - vb) / denominator;
remainder = (va - vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s-%s = 24\n", a->string, b->string);
num++;
}
}
else{
integer = (vb - va) / denominator;
remainder = (vb - va) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s-%s = 24\n", b->string, a->string);
num++;
}
}
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
integer = (va * vb) / denominator;
remainder = (va * vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%sx%s = 24\n", a->string, b->string);
num++;
}
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
integer = va / vb;
remainder = va % vb;
if((integer == 24) && (remainder == 0)){
printf("%s/%s = 24\n", a->string, b->string);
num++;
}
}
if(va){
integer = vb / va;
remainder = vb % va;
if((integer == 24) && (remainder == 0)){
printf("%s/%s = 24\n", b->string, a->string);
num++;
}
}
return num;
}
static int level_2(VALUE_T *a, VALUE_T *b, VALUE_T *c){
char stringBuffer[32];
VALUE_T value;
int va, vb, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
value.integer = (va + vb) / denominator;
value.remainder = (va + vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%s+%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
value.integer = (va - vb) / denominator;
value.remainder = (va - vb) % denominator;
sprintf(stringBuffer, "(%s-%s)", a->string, b->string);
}
else{
value.integer = (vb - va) / denominator;
value.remainder = (vb - va) % denominator;
sprintf(stringBuffer, "(%s-%s)", b->string, a->string);
}
value.denominator = denominator;
value.string = stringBuffer;
num += level_3(&value, c);
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
value.integer = (va * vb) / denominator;
value.remainder = (va * vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%sx%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
value.integer = va / vb;
value.remainder = va % vb;
value.denominator = vb;
sprintf(stringBuffer, "(%s/%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
}
if(va){
value.integer = vb / va;
value.remainder = vb % va;
value.denominator = va;
sprintf(stringBuffer, "(%s/%s)", b->string, a->string);
value.string = stringBuffer;
num += level_3(&value, c);
}
return num;
}
static int level_1(VALUE_T *a, VALUE_T *b, VALUE_T *c, VALUE_T *d){
char stringBuffer[32];
VALUE_T value;
int va, vb, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
value.integer = (va + vb) / denominator;
value.remainder = (va + vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%s+%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
value.integer = (va - vb) / denominator;
value.remainder = (va - vb) % denominator;
sprintf(stringBuffer, "(%s-%s)", a->string, b->string);
}
else{
value.integer = (vb - va) / denominator;
value.remainder = (vb - va) % denominator;
sprintf(stringBuffer, "(%s-%s)", b->string, a->string);
}
value.denominator = denominator;
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
value.integer = (va * vb) / denominator;
value.remainder = (va * vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%sx%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
value.integer = va / vb;
value.remainder = va % vb;
value.denominator = vb;
sprintf(stringBuffer, "(%s/%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
}
if(va){
value.integer = vb / va;
value.remainder = vb % va;
value.denominator = va;
sprintf(stringBuffer, "(%s/%s)", b->string, a->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
}
return num;
}
static int level_0(int a, int b, int c, int d){
char buffer[4][4];
sprintf(buffer[0],"%d", a);
sprintf(buffer[1],"%d", b);
sprintf(buffer[2],"%d", c);
sprintf(buffer[3],"%d", d);
VALUE_T value[4];
value[0].integer = a;
value[0].remainder = 0;
value[0].denominator = 1;
value[0].string = buffer[0];
value[1].integer = b;
value[1].remainder = 0;
value[1].denominator = 1;
value[1].string = buffer[1];
value[2].integer = c;
value[2].remainder = 0;
value[2].denominator = 1;
value[2].string = buffer[2];
value[3].integer = d;
value[3].remainder = 0;
value[3].denominator = 1;
value[3].string = buffer[3];
int num = 0;
num += level_1(&value[0], &value[1], &value[2], &value[3]);
num += level_1(&value[0], &value[2], &value[1], &value[3]);
num += level_1(&value[0], &value[3], &value[1], &value[2]);
num += level_1(&value[1], &value[2], &value[0], &value[3]);
num += level_1(&value[1], &value[3], &value[0], &value[2]);
num += level_1(&value[2], &value[3], &value[0], &value[1]);
return num;
}
////////////////////////////////////////////////////////////////////////////////
static int parameterCheck(int argc, char* argv[]){
char *p;
int value;
while(*argv){
p = *argv;
if((*p < '1') || (*p > '9')) return 1;
p++;
while(*p){
if((*p < '0') || (*p > '9')) return 1;
p++;
}
value = atoi(*argv);
if((value < 1) || (value > 13)) return 1;
argv++;
}
return 0;
}
static void help(char *name){
printf("Usage : %s num1 num2 num3 num4\n", name);
printf("Example: %s 5 5 5 1\n", name);
}
int main(int argc, char* argv[]){
if(argc < 5){
help(argv[0]);
return 0;
}
if(parameterCheck(argc-1, argv+1)){
help(argv[0]);
return 0;
}
int num = level_0(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]));
printf("total = %d\n", num);
return 0;
}
运行测试
错误的参数测试
测试 12、2、9、10 以及运行时间
上面是普通测试，下面是网上搜索的，被称为超难的几组24点游戏题，看看求解效果：
（5、5、5、1）
（1、4、5、6）
（1、3、7、8）
（2、5、5、10）
（3、3、8、8）
（1、2、7、7）
（2、5、7、8）
（1、3、4、6）
如何去重问题
对于算式字符串字面值完全相同的算式非常容易去重，但是
有些算式字符串字面值不同而含义明显相同，例如：
((1+2)+3)x4 = 24和(1+(2+3))x4 = 24含义重复；
((5+9)-6)x3 = 24和((9-6)+5)x3 = 24含义重复；
((9-5)x3)x2 = 24和((9-5)x2)x3 = 24含义重复等等。
留待以后想办法解决。
记于2019-04-15
