在一本谜题书中,我发现了以下谜题。
标题是用荷兰语写的,但我可以简单描述一下。
例如,在图中的情况下,我们可以知道 A+C=5
,因此我们可以推断,A和C都不可能是6。通过反复做这些,你会发现序列。
现在,我的问题是:我怎样才能写出一个算法来生成这些谜题值呢?我曾试着想出一个随机序列,并用6个类似的数学语句来描述它,但在某些情况下,谜题将是无法解决的。
这样的无解情况语句例如当序列为012345时,语句为 A+B=1
B+C=3
C+D=5
D+E=7
E+F=9
F+A=5
首先,让我们来阐述一下解决方案 S
对于这个问题。
为每个变量建立一个{0,1,2,3,4,5,6}的集合,其中包括其可能的值。
分析每个方程,并根据方程从变量集中切出数值。
example: A + B = 3 (we can cut 4, 5 and 6 from A and B sets)
.当所有的集合都只有1个元素时,这就是你的答案。
另一方面,如果所有的方程都分析过了,集子没有变化,那就不可能了。
Example: (1) A + C = 5 (2) B - D = 5 (3) B + C = 6
(4) E * F = 6 (5) B - E = 3 (6) A + D = 6
Analysing (1): Reduce A and C to {0,1,2,3,4,5}.
Analysing (2): Reduce B to {5,6}. Reduce D to {0,1}.
Analysing (3): Reduce C to {0,1}
Analysing (4): Reduce E and F to {1,2,3,6}.
Analysing (5): Can't reduce.
Analysing (6): Reduce A to {5}. Reduce D to {1}.
--------------------------------------------------
Not over yet, but something changed. Restart:
--------------------------------------------------
Analysing (1): Reduce C to {0}
Analysing (2): Reduce B to {6}.
Analysing (3): Can't reduce.
Analysing (4): Reduce E and F to {1,2,3,6}.
Analysing (5): Reduce E to {3}.
Analysing (6): Can't reduce.
--------------------------------------------------
Not over yet, but something changed. Restart:
--------------------------------------------------
Analysing (1): Can't reduce.
Analysing (2): Can't reduce.
Analysing (3): Can't reduce.
Analysing (4): Reduce F to {2}.
Analysing (5): Can't reduce.
Analysing (6): Can't reduce.
--------------------------------------------------
Over. All sets of size 1. Answer: (5,6,0,1,3,2)
--------------------------------------------------
现在,知道了如何解题,我会用下面的方法来制作谜题。
随机选择一个答案.
example: (4, 1, 3, 2, 0, 5)
.用它生成6个随机方程。
运行
S
与此方程。如果
S
结束,你有一个可能的方程组。否则,重新开始。
有 7^6 = 117649
可能的代码。 6个问题,我们只需要每个问题去掉67个搜索空间。 如果前几道题做的多,那就更好了。
对于这三道题,很容易。 当你看一下求和或求差的方法分布时,你会发现,不可能有超过 7/49 = 49
的方法来获得答案,而且通常更少。 所以把A、B、C、D、E、F分成3对2,供给随机操作,你剩下的可能答案不超过343个。
以你的例子,我随机生成了 D-A=4
, C+F=7
, D-B=2
. 对于第一对,我们有3种可能性,第二对有6种可能性,第三对有5种可能性。
现在我们需要做的是实际构造所有的可能性(在这种情况下有90种可能性)。 然后你可以构造随机语句,只接受那些在通往1解的路径上的语句。 也就是说,在剩下3道题的情况下,你至少以立方根的系数削减(在这种情况下,留下的可能性不超过20个),以平方根的系数削减2个(留下的可能性不超过4个),然后再削减一个可能性。
考虑到一个随机问题平均会使你的搜索空间至少减少67,随机问题很可能很容易做到这一点。 (挑战在于验证答案)。
这看起来不过是简单的代数替换。此外,方程中运算的选择并不重要。从
(D, B) (B, C)
我们得到
(D, C)
然后从
(D, C) (C, A)
我们得到
(D, A)
(A,D)的方程已经存在,所以我们可以对两者进行求解。从那里,我们很容易看到如何完成解题。
为了创建一个谜题,从任何这样的双方程开始,比如说
(E, F) (E, F)
然后把其中的一个拆成比较隐晦的,像
(E, B) (B, F)
这就给了我们六个方程中的三个方程(记住运算的选择可以是纯随机的)。我让读者对完成多加思考。
我不会期望完成和实现是微不足道的,但希望这能让我们了解如何在不走回头路的情况下很有意识地完成这个任务。
JavaScript代码。
const vars = ["A", "B", "C", "D", "E", "F"];
function getOps(pair){
return pair.includes(0) ? ["+", "-"] : ["+", "-", "*"];
}
function getRandom(k, list){
let result = [];
for (let i=0; i<k; i++)
result = result.concat(
list.splice(~~(Math.random()*list.length), 1));
return result;
}
function getNum(a, b, op){
return eval(`${ a } ${ op } ${ b }`);
}
function getEquation(a, b, op, idxs){
// Randomise the order of the variables
if (Math.random() > 0.5)
[a, b] = [b, a];
return `${ vars[idxs[a]] } ${ op } ${ vars[idxs[b]] } = ${ getNum(a, b, op) }`;
}
function f(){
let remaining = [0, 1, 2, 3, 4, 5, 6];
let result = [];
// Remove one entry
remaining.splice(~~(Math.random()*7), 1);
// Shuffle
remaining = getRandom(6, remaining);
const idxs = Object.fromEntries(
remaining.map((x, i) => [x, i]));
// Select equation pairs
const [a, b] = getRandom(2, remaining);
const [c, d] = getRandom(2, remaining);
result.push(
getEquation(a, c, getRandom(1, getOps([a, c])), idxs),
getEquation(a, d, getRandom(1, getOps([a, d])), idxs),
getEquation(b, c, getRandom(1, getOps([b, c])), idxs),
getEquation(b, d, getRandom(1, getOps([b, d])), idxs)
);
const [e] = getRandom(1, remaining);
const [f] = remaining;
const [aa] = getRandom(1, [a, b, c, d]);
result.push(
getEquation(e, f, getRandom(1, getOps([e, f])), idxs),
getEquation(e, aa, getRandom(1, getOps([e, aa])), idxs)
);
const legend = Object.entries(idxs)
.map(([x, i]) => [vars[i], Number(x)])
.map(([a, b]) => `(${ a } ${ b })`)
.sort()
.join(' ');
return {
equations: getRandom(6, result).join('\n'),
legend: legend
};
}
var result = f();
console.log(result.equations);
console.log('');
console.log(result.legend);