Проблема с решением игровой задачи

222

22 декабря 2017, 02:21

У меня возникла проблема с реализацией алгоритма для игровой задачи.

Задание такое: Найти такие 12 натуральных чисел, которые не превышают 19, что бы их сума по всем направлениями, указаными стрелкой, были равны 38. Числа не должны повторятся.

Ячейки я решил рассматривать как двумерный массив int значений, если его чуть-чуть наклонить.

Сразу же его инициализировал, согласно условию.

int mass[5][6]={{3,17,18,-1,-1,-1},{0,0,1,0,-1,-1},{16,2,0,0,0,-1},{0,0,0,0,-1,-1},{10,0,0,-1,-1,-1}};

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

Answer 1

Ваш массив не даёт вам лёгких путей подбора. Я бы пошёл по другому пути - создал бы класс, который:

хранил бы в себе массив значений и координат. Можно использовать обычную декартовую, а можно - гексагональную, так будет проще строить векторы. С другой стороны, у вас всего-то 19 ячеек, так что векторы вы можете даже задать руками.
реализовывал методы, позволяющие получить вектор со значениями и его сумму.
реализовывал инструмент (в виде массива, или ещё как-то) с остаточным набором чисел.

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