[Santa Evita]

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

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

формулировка задачи

Есть шестнадцать квадратов, в каждом углу у квадрата есть цифра от 0 до 9. Необходимо расставить их по полю такого вида:

чтобы суммы цифр в пересечениях углов квадратов были равны 10.
это задача из "Игр Разума", приложения для андроида, и я вполне могла бы найти решение в Интернете, но написать программу - уже дело принципа.

@темы: Алгоритм

Comments

а зачем вам перестановки? проверять нужные суммы по ходу игры - не вариант?

[Santa Evita]

ninelya, по ходу игры я задолбалась, потому и пишу программу )

т.е. вы пишете не саму игру, а её решение? Боюсь, вам всё равно придется перебрать все варианты минимум один раз((

[Скептичный циник]

эпонина из пластилина, здравствуйте (:
Впервые слышу о такой игре посему вопросы. Возможно, глупые. Как должно выглядеть решение?
То есть, почему нельзя просто сгенерить случайную комбинацию n чисел, которая давала бы в сумме 10 (типа 1+2+3+4) и просто расставить их по полю?

Скептичный циник,
я так понимаю, что уже есть квадртаы с цифрами. Их нужно только расставить по полю.

[Santa Evita]

ninelya, да, я пишу решение.
перебрать все варианты минимум один раз - это около 600 часов по верхней оценке. я уверена, что перебор можно оптимизировать )

Скептичный циник, dpleshakov, именно, квадраты уже заданы и их нельзя вертеть или менять )

[Mr.Freedom]

Не будет там 16! Там будет что то похожее на алгоритм деиксты - на каждом шаге проверять не набралось ли у вас уже сумма больше 10 и все будет ок.

[Mr.Freedom]

Ради интереса можете написать и полный перебор 2*10^13 (=16!) я думаю за пару часов современный комп пеереберт

[Santa Evita]

Mr.Freedom, а можно подробнее? у меня нет идей, как это реализовывать.
спасибо)

Mr.Freedom, полный перебор я писала, за ночь не успел

[Mr.Freedom]

алгоритм простой как апельсин:
1 заполняем все свободные нулями
2 берем первую свободну ячейку - ставим 9
3 берем вторую свободную ставим 9 - проверяем - сумму линий - уже не сойдется значит берем 8
если не подошла ни одно из чисел откатываемся назад(в предыдущую ячейку) и меняем там значение.

ПС обратный порядок перебора мне кажется будет быстре в данном случае - хотя скорее всего на копейки.

[Santa Evita]

Mr.Freedom, квадраты с заданными числами уже имеются, задача в том, чтобы их расставить по полю.

[Mr.Freedom]

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

[Santa Evita]

Mr.Freedom, спасибо большое, вроде бы понятно )
только тогда нужно один элемент поставить на первую позицию и зафиксировать его там, я правильно понимаю?

[Mr.Freedom]

я не уверен что задача решается с фиксированным элементом. Псевдокод выглядит так
пока(1){
do{
взять следующий возможный кубик
}
while(проверить ненарушено ли правило суммы)
если по прежнему правило суммы нарушено откатится на предыдущюу ячейку(если это первая ячейка игра не имеет решение)
если все ок - переходим на следующую(если это последняя ячейка - игра пройдена)
}

[Santa Evita]

Mr.Freedom, а, теперь точно понятно.
еще раз спасибо!

[Mr.Freedom]

эпонина из пластилина, классическое решение подобных задач - уж очень часто применяется.

Кстати, задачка в "Играх разума" у меня как-то легко решилась. Точно уже не помню, либо я первым делом раскидал все 9-ки - у них очень мало точек расположения. А остальное расставить - дело техники.
Можно посмотреть, если будут конкретные кубики с цифрами.

[Mr.Freedom]

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