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

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

Чтобы понять проблему,

Вот некоторые данные в формате JSON, соответствующие исходному изображению на карте

{"wallX":[0,2],"wallY":[0,2],"startX":0,"startY":1,"maxX":3,"maxY":3}

введите здесь описание изображения

{"wallX":[],"wallY":[],"startX":1,"startY":4,"maxX":6,"maxY":6}

введите здесь описание изображения

Правила

  1. 99 представляют стену. X&Y стены[индекс] представлены стенойX[индекс] и стенойY[индекс].
  2. 01 представляют начальную точку Змеи. X&Y из 01 представлены startX и startY
  3. maxX представляет столбец двумерного массива, а maxY представляет строку двумерного массива. Оба maxX и maxY ‹= 9
  4. На начальном двухмерном массиве/карте любая плитка, отличная от 01 или 99, будет плиткой 00.
  5. Змея может двигаться только до 00
  6. Змея двигается 4 способами [слева, сверху, справа, снизу]

Ввод программы - это формат JSON.

Вывод программы должен быть:

  1. 2-мерный массив состоит из 99 и/или (от 01 до 0X) без оставшихся 00 плиток, которые представляют карту решенной.
  2. Исходный двумерный массив, который представляет, что больше нет возможных ходов, но есть как минимум 1 из 00

Вот некоторые другие входные данные, соответствующие их выходному изображению 2D-массива

{"wallX":[0,0,1,2,3,4,5],"wallY":[0,4,5,1,1,1,4],"startX":0,"startY" :3,"максХ":6,"максУ":8}

{"wallX":[0,1],"wallY":[0,1],"startX":0,"startY":1,"maxX":2,"maxY":2}

{"wallX":[0,2],"wallY":[0,2],"startX":1,"startY":1,"maxX":3,"maxY":3}

введите здесь описание изображения

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

  1. Я попытался выполнить поиск в Google по ключевому слову, такому как «Заполнить», но большинство результатов показали мне [Алгоритм заполнения-заполнения]. Большинство Flood Fill, которые я читал, не могут быть применены здесь, так как Snake или [LastNumber] должны быть смежными с [LastNumber+1].

  2. Я также пытался найти о Pathing, но кажется, что PathFinding работает, если есть Start и Destination, но эта проблема, похоже, не имеет четкого Destination.

Пожалуйста, поправьте меня, если я ошибаюсь в этом ^

Заранее спасибо за вашу помощь


algorithm flood-fill pathing
person Yogie Soesanto    schedule 04.03.2020    source источник
comment
Это трудная проблема. Это эквивалентно нахождению гамильтонова цикла в графе (ячейки являются вершинами, а соседние ячейки имеют ребро). en.wikipedia.org/wiki/Hamiltonian_path_problem   -  person Dave    schedule 04.03.2020
comment
@Dave Тот факт, что проблема X может быть указана как частный случай NP-полной проблемы Y, не означает, что X является NP-полной. Таким образом, задача нахождения гамильтоновых циклов в прямоугольных сетках с некоторыми пропущенными узлами может быть полиномиальной, даже если та же задача для общих графов является NP-полной.   -  person btilly    schedule 05.03.2020
comment
В этом случае см. hindawi.com/journals/jam/2012/475087 показывая некоторый успех в решении такого рода задач для некоторых прямоугольных форм. Учитывая, что это опубликованное исследование и простая версия общей проблемы, можно предположить, что проблема сложная. Но это все еще возможно. По крайней мере, необходимая проверка четности черных/белых квадратов на шахматной доске может позволить многим расстановкам стен быстро признать невозможными.   -  person btilly    schedule 05.03.2020
comment
Я подозреваю, что путь Гамильтона в графах сетки с произвольными стенами сложен, но Angluin--Valiant может быть достойной эвристикой на практике: stackoverflow.com/questions/15898884/   -  person David Eisenstat    schedule 05.03.2020
comment
NB: странно видеть свойство с именем maxX, когда оно не предоставляет максимальное значение для X, а еще одно — поскольку ваши примеры показывают, что система координат отсчитывается от нуля. Лучшими именами были бы sizeX или endX.   -  person trincot    schedule 05.03.2020
comment
@btilly Это NP для подграфов решетки или квадратной сетки (согласно статье в Википедии)   -  person Dave    schedule 06.03.2020