如何生成 'crack the code' 的拼图？

Question

我在一本拼图书中发现了以下拼图：

标题是荷兰语，但我可以简短地描述它：

在0...6范围内有一个数字序列，没有给定
有 6 个数学陈述（下面列出）是正确的
通过使用逻辑并划掉某些您知道肯定不是的数字，玩拼图的人都可以找到数字序列（代码）。

例如图中的例子，我们知道A+C=5，因此可以推断A和C都不可能是6，这样反复做，就可以找到序列[=19] =]

现在，我的问题是：如何编写生成这些拼图值的算法？我试图想出一个随机序列，并用 6 个类似的数学陈述来描述它，但在某些情况下，这个谜题将无法解决。

这种无法解决的情况/语句例如当序列为 012345 时，语句 A+B=1 B+C=3 C+D=5 D+E=7 E+F=9 F+A=5

Answer 1

首先，针对这个问题S阐述一下解决方案：

For each variable, create a set {0,1,2,3,4,5,6} with its possible values.

Analyse each equation and cut values from the variables' sets based on the equations.

example: A + B = 3 (we can cut 4, 5 and 6 from A and B sets).

When all sets have only 1 element, that's your answer.

On the other hand, if all equations are analysed and no set changes, it's impossible.

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)
--------------------------------------------------

现在，知道如何解决了，我会按照以下方式创建谜题：

Choose a random answer.

example: (4, 1, 3, 2, 0, 5).

Generate 6 random equations with it.

Run S with this equations.

If S ends, you have a possible group of equations.

Otherwise, restart.

Answer 2

有 7^6 = 117649 个可能的代码。有 6 个问题，我们只需要每个问题删除 6/7 的搜索 space。如果前几个做得更多，那就更好了。

这三道题，很简单。当您查看求和或求差的方法分布时，您会发现求答案的方法不会超过 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），然后是单一的可能性。

考虑到随机问题平均会使您的搜索 space 减少至少 6/7，随机问题很可能很容易做到这一点。（挑战在于验证答案。）

Answer 3

这似乎只不过是简单的代数替换。此外，方程式中运算的选择并不重要。来自

(D, B) (B, C)

我们得到

(D, C)

然后从

(D, C) (C, A)

我们得到

(D, A)

(A, D) 的方程式已经存在，所以我们可以同时求解。从那里，很容易看出如何完成解决方案。

为了创造一个谜题，从任何这样的双方程开始，比如说

(E, F) (E, F)

然后把其中的一个拆分成比较晦涩的，比如

(E, B) (B, F)

这给了我们六个方程式中的三个（记住操作的选择可以是纯随机的）。我离开 reader 以更多地考虑完成。

我不希望完成和实施是微不足道的，但希望这能让我们了解如何在不回溯的情况下有意识地完成这项工作。

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);

如何生成 'crack the code' 的拼图？

How to generate puzzles to 'crack the code'?

algorithm

math

puzzle