Сгенерировать все возможные последовательности цифровой клавиатуры / клавиатуры

Я пытаюсь сгенерировать все возможные последовательности клавиш (сейчас только 7 цифр). Например, если мобильная клавиатура выглядит так:

1 2 3
4 5 6
7 8 9
  0

Некоторые из возможных последовательностей могут быть такими:

123698
147896
125698
789632

Требуется, чтобы каждая цифра номера была соседней с предыдущей цифрой.

Вот как я планирую начать это:

Информация о соседе изменяется с клавиатуры на клавиатуру, поэтому мы должны жестко закодируйте его так:

neighbors = {0: 8, 1: [2,4], 2: [1,3,5], 3: [2,6], 4: [1,5,7], 5: [2,4,6,8], 6: [3,5,9], 7: [4,8], 8: [7,5,9,0], 9: [6,8]}

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

РЕДАКТИРОВАТЬ: Обновленные соседи, диагонали не допускаются РЕДАКТИРОВАТЬ 2: Цифры можно использовать повторно