Более эффективный подход к Словесной арифметике / Alphametics?

Большой вопрос здесь: можете ли вы (хотите ли вы) логически вывести определенные ограничения и применить их к своему алгоритму, или вы хотите использовать его методом грубой силы? Предполагая первое, некоторые из них довольно очевидны:

• B = 1
• T не может быть 0 (потому что он первый в THE), поэтому ни S, ни E также не могут быть 0.
• T = E + S% 10

Таким образом, у вас есть S, E, H для циклического перебора, давая вам не более 9 * 8 * 8 комбинаций, что составляет 576. Добавьте к этому тот факт, что H + T должно быть больше или равно 9, и вы Это еще больше уменьшу.

Обновление Вот быстрое и уродливое решение. Он основан только на 3 ограничениях, перечисленных выше.

public class Puzzle {
  public static void main(String[] args) {
    for (int S = 1; S<10; S++) {
      for (int E = 1; E<10; E++) {
        if (S==E) continue; // all letters stand for different digits
        for (int H = 1; H<10; H++) {
          if (H==E || H==S) continue; // all letters stand for different digits
          checkAndPrint(S, E, H);
        }
      } // for
    } // for
  } // main

  private static boolean checkAndPrint(int S, int E, int H) {
    int T = (S + E) % 10;
    int S1 = (E + H) + (S + E) / 10; // calculates value for 'S' in 'BEST' (possibly + 10)
    if (S1 % 10 != S) return false;
    int E1 = H + T + S1 / 10; // calculates value for 'E' in 'BEST' (possibly + 10)
    if (E1 % 10 != E) return false;
    System.out.println(H + "" + E + "" + S + " + " + T + "" + H + "" + E + " = 1" + E + "" + S + "" + T);
    return true;
  }
}

Вместо того, чтобы перебирать все значения букв, перебрать возможные значения для S, E и T. S + E% 10 должно быть T. Как только у вас есть набор потенциальных решений S, E, T, найдите цикл через возможные E + H + (0 или 1, в зависимости от того, больше ли S + E, чем 9) = S решений ... и так далее, и так далее.

Эффективность вылетает из окна, если стандартным подходом является грубая сила , как предлагается здесь. Наиболее эффективный способ, использующий только циклы, вероятно, включает в себя вычисление исчерпывающего набора возможностей, их сохранение, а затем повторение каждого из них, чтобы увидеть, работает ли он.

ммм, вы могли бы многое сделать в форме оптимизации в своем подходе.

Прежде всего, получите максимальное значение для "BEST". предположим, что «HES» имеет максимально возможное значение, 987, тогда «THE» будет X98, поэтому максимальное значение для «THE» равно 698, что дает 987 + 698 = 1685.

если «THE» имеет максимальное значение, THE будет 987, а HES будет 876 -> 876 + 987 = 1863, что больше, чем 1685, так что 1863 - это верхняя граница для «наилучшего». Таким образом, вы можете настроить в своей программе верхнюю границу для «B» на 1 (что в данном случае уже дает вам первую цифру ..). нижняя граница для BEST проста, так как это 1023.

затем вы делаете что-то вроде этого:

for(i=102;i<=987;i++)
{
    for(j=1023-i;j<=(1863-i < 987 ? 1863-i:987);j++)
    {
        //check if the solution matches and doesn't have duplicate digits
    }
}

таким образом вы сразу отбрасываете множество невозможных комбинаций через значения во внутреннем цикле for. и я уверен, что есть аналогичные способы более ограничить пространство возможных решений.

И программа намного менее сложна.

Этот класс проблем - это пример оптимизации запросов. Java не для этого.

Если у вас меньше нескольких десятков миллиардов состояний, используйте грубую силу. На выполнение поиска методом грубой силы потребуется гораздо меньше времени, чем на создание оптимизирующего механизма запросов.

Я не эксперт, но, возможно, стоит взглянуть на языки, которые управляют ограничениями, такие как Prolog. Здесь есть очень похожая проблема:

Вычислить список различных нечетных чисел (если таковой существует), чтобы их сумма была равна заданному числу

Пролог - это другой тип языка, но если вы делаете это для ваше собственное образование, тогда оно обязательно будет тренировать ваш мозг: -)

Можно будет закодировать общие подходы к алфавитам - а не только довольно простой здесь.

Альтернатива - которая не гарантирует результата - заключается в использовании такого метода оптимизации, как генетические алгоритмы. Угадайте несколько решений и вычислите, насколько они близки к правильному, а затем скорректируйте их. Вы можете получить частичные решения этим методом.