Рубрики

Решение Криптарифметических Пазлов | Откат-8

Backtracking

Газеты и журналы часто имеют загадочно-арифметические загадки вида:

  SEND
+ MORE
--------
 MONEY
--------


Цель здесь — присвоить каждой букве цифру от 0 до 9, чтобы арифметика работала правильно. Правила заключаются в том, что все вхождения буквы должны иметь одну и ту же цифру, и никакая цифра не может быть назначена более чем одной букве.

  • Сначала создайте список всех персонажей, которых нужно назначить для передачи в Solve.
  • Если все символы назначены, верните true если головоломка решена, иначе false
  • В противном случае, рассмотрим первый неназначенный символ
  • для (любой возможный выбор среди неиспользуемых цифр)

    • сделать этот выбор, а затем рекурсивно попытаться назначить остальных персонажей
    если рекурсия прошла успешно, верните true
    если! успешно, отмените назначение и попробуйте другую цифру

  • Если все цифры были опробованы и ничего не работает, верните false, чтобы вызвать возврат

/ * ExhaustiveSolve
* ---------------
* Это "не очень умная" версия криптарифметического решателя. Занимает
* сама головоломка (с 3 строками для двух сумм и суммы) и
* Строка букв еще не назначена. Если нет больше букв для назначения
* тогда мы добрались до базового случая, если текущее преобразование букв в цифры решает
* загадка, мы закончили, в противном случае мы возвращаем false, чтобы вызвать возврат
* Если у нас есть буквы для назначения, мы берем первую букву из этого списка, и
* попробуйте присвоить ему цифры от 0 до 9 и затем рекурсивно работать
* Решая головоломку отсюда. Если нам удастся сделать хорошее задание
* это работает, мы добились успеха, иначе нам нужно отменить этот выбор и попробовать
* другая цифра. Эту версию легко написать, поскольку она использует простой
* подход (очень похож на перестановки, если вы думаете об этом), но это
* не такой умный, потому что не учитывает структуру
* ограничения головоломки (например, когда две цифры для дополнений имеют
* был назначен, нет никаких причин, чтобы попробовать что-либо, кроме правильного
* цифра для суммы), но она пытается много бесполезных комбинаций независимо
* /

bool ExhaustiveSolve(puzzleT puzzle, string lettersToAssign)

{

    if (lettersToAssign.empty()) // больше нет выбора

        return PuzzleSolved(puzzle); // проверяет арифметику, чтобы увидеть, работает ли

    for (int digit = 0; digit <= 9; digit++)   // попробуем все цифры

    {

        if (AssignLetterToDigit(lettersToAssign[0], digit))

        {

            if (ExhaustiveSolve(puzzle, lettersToAssign.substr(1)))

                return true;

            UnassignLetterFromDigit(lettersToAssign[0], digit);

        }

    }

    return false;  // ничего не получилось, нужно вернуться

}

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

Ниже псевдокод, в данном случае, имеет более особые случаи, но тот же общий дизайн

  • Начните с изучения самой правой цифры самого верхнего ряда, с переносом 0
  • Если мы находимся за самой левой цифрой головоломки, верните true, если нет переноса, иначе false
  • Если мы в настоящее время пытаемся назначить символ в одном из дополнений
    Если char уже назначен, просто вернитесь в строку ниже этой, добавив значение в сумму
    Если не назначен, то
    • для (любой возможный выбор среди неиспользуемых цифр)
      сделайте этот выбор и затем в строке под ним, в случае успеха, верните true
      если! успешно, отмените назначение и попробуйте другую цифру
    • вернуть false, если не сработало назначение, чтобы вызвать возврат
  • Иначе, если попытаться назначить символ в сумме
  • Если символ назначен и соответствует правильно,
    повторить в следующем столбце слева с переносом, если успех вернет истину,
  • Если символ назначен и не совпадает, вернуть false
  • Если символ не назначен и правильная цифра уже используется, верните false
  • Если символ не назначен и правильная цифра не используется,
    назначить его и повторить в следующем столбце слева с переносом, если успех вернет true
  • вернуть false, чтобы вызвать возврат

Источник:
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

Рекомендуемые посты:

Решение Криптарифметических Пазлов | Откат-8

0.00 (0%) 0 votes