Генерация 10-значного номера с помощью клавиатуры телефона

Question

Учитывая телефонную клавиатуру, как показано ниже:

1 2 3
4 5 6
7 8 9
  0

Сколько разных 10-значных чисел можно сформировать, начиная с 1?Ограничение состоит в том, что движение от 1 цифры до следующей аналогично движению Рыцаря в шахматной игре.

Например,если мы находимся на 1, то следующая цифра может быть 6 или 8, если мы находимся на 6, тогда следующая цифра может быть 1, 7 или 0.

Повторение цифр разрешено - 1616161616 является действительным числом.

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

РЕДАКТИРОВАТЬ: Я пытался смоделировать это как график, где каждая цифра имеет 2 или 3 цифры в качестве соседей.Затем я использовал DFS для перехода на глубину до 10 узлов, а затем увеличивал количество чисел каждый раз, когда достигал глубины 10. Это, очевидно, не полиномиальное время.Предполагая, что у каждой цифры есть только 2 соседа, это потребовало бы по крайней мере 2 ^ 10 итераций.

Переменная здесь - это количество цифр.Я взял пример.из 10 цифр.Это также могут быть n-цифры.

Answer 1

Рекурсивная функция в Java:

public static int countPhoneNumbers (int n, int r, int c) {
        if (outOfBounds(r,c)) {
            return 0;
        } else {
            char button = buttons[r][c];
            if (button  == '.') {
                // visited
                return 0;
            }  else {
                buttons[r][c] = '.'; // record this position so don't revisit.
                // Count all possible phone numbers with one less digit starting
                int result=0;
                result = countPhoneNumbers(n-1,r-2,c-1)
                                         + countPhoneNumbers(n-1,r-2,c+1)
                                         + countPhoneNumbers(n-1,r+2,c-1)
                                         + countPhoneNumbers(n-1,r+2,c+1)
                                         + countPhoneNumbers(n-1,r-1,c-2)
                                         + countPhoneNumbers(n-1,r-1,c+2)
                                         + countPhoneNumbers(n-1,r+1,c-2)
                                         + countPhoneNumbers(n-1,r+1,c+2);
                }
                buttons[r][c] = button; // Remove record from position.
                return result; 
            }
        }
    }

Answer 2

Эта проблема также может быть смоделирована как проблема удовлетворения ограничений (сокращенно CSP).

Я предлагаю использовать Minion решатель (быстрый и масштабируемый), который вы можете найти здесь .

Моделирование может быть утомительным и трудоемким (крутая кривая обучения).

Вместо использования ввода на языке Minion мой совет - сформулировать модель с помощью независимого языка моделирования, такого как ESSENCE , и найти соответствующий преобразователь.