Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Fiver как написать эту игру
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
RAPIST RAPIST вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.06.2007
По умолчанию Fiver как написать эту игру - 29.08.2007, 17:09

Закачал себе на телефон игрушку “fiver”. (для тех кто не знает условия игры: задается поле размером 3*3, 4*4, 5*5, 6*6 или 7*7. изначально все поля белые закрашивая одно поле закрашиваются также все соседние. Суть: закрасить все поля за меньшее число ходов). 3*3 и 4*4 решив в легкую, 5*5 бился неделю- сначала искал алгоритм, после уже тыкал куда попало, пока не сходилось. Но за мин. число так и не набрал. Плюнул на все, написал программку:
3*3 - 5 ходов (это точно минимум)
4*4 - 8 ходов (УЖОС – я в ручную за 4 закрыл)
5*5 - 15 ходов (даже не знаю, на ско-ка верно)
6*6 - вообще зациклилась…
7*7 – 33 хода (ну должно быть решение пооптимальней- нутром чую, доказать не могу)
Ответить с цитированием
  (#2 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 29.08.2007, 20:51

Ох, заразил. Буду думать. По идее, возможно чисто математическое решение.

Ясно одно: "зацикливание" невозможно. Потому что два раза щелкать по одной клетке не имеет смысла - результат не зависит от порядка нажатия клеток. Так что число вариантов конечно.
Ответить с цитированием
  (#3 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 30.08.2007, 16:32

A*
Ответить с цитированием
  (#4 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 30.08.2007, 16:52

Цитата:
A*
Это Вы к чему, уважаемый коллега?

В общем, там получается симпатичная система линейных уравнений над Z2
Ответить с цитированием
  (#5 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 30.08.2007, 17:10

Цитата:
Это Вы к чему, уважаемый коллега?
A* - это название известного алгоритма поиска. Для этой задачки он очень хорошо подойдет.

Цитата:
В общем, там получается симпатичная система линейных уравнений над Z2
Интересно. Опубликуете?
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
D_K D_K вне форума
Member
 
Сообщений: 1,681
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.11.2005
По умолчанию 30.08.2007, 17:11

Если будет время, тоже подумаю на выходных, только вот отпишусь не раньше понедельника-вторника, раньше к инету доступа не будет...
Цитата:
A*
Хм..Интересная мысль
Ответить с цитированием
  (#7 (permalink)) Старый
RAPIST RAPIST вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.06.2007
По умолчанию 30.08.2007, 18:01

Цитата:
Ясно одно: "зацикливание" невозможно. Потому что два раза щелкать по одной клетке не имеет смысла - результат не зависит от порядка нажатия клеток. Так что число вариантов конечно.
Ну это и так понятно. Я сразу отказаться от перебора, а стал искать определенный алгоритм. Функция находит определенное правильное решение, а после смотрит: если число нажатий- четное, то не нажимаем, если- не четно нажимаем. Видно алгоритм не универсален.
Ответить с цитированием
  (#8 (permalink)) Старый
RAPIST RAPIST вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.06.2007
По умолчанию 31.08.2007, 11:57

Вот какой алгоритм я использовал:
1 Закрашиваю первую ячейку (в счетчик изменений 1-ой ячейки добавляю 1)
2 Ищу следующую "не закрашенную" в строке, закрашиваю ее. (Добавляю 1 в счетчик изменений этой ячейки)
3 Перехожу на следующую строку, повторяю п.2
4 Дойдя до конца массива проверяю были изменения или нет
5 Если да, повторяю пп 2-4
6 Если нет, то все элементы закрашены => смотрю скока раз менялась каждая ячейка, если четное, то значение счетчика сбрасываю на 0, если если нечетное, сбрасываю на единицу.
7 Там где единица надо закрашивать.

Вроде все логично, НО... Как я уже говорил: не оптимальное число ходов, и зацикливание...
Ответить с цитированием
  (#9 (permalink)) Старый
RAPIST RAPIST вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.06.2007
По умолчанию 04.09.2007, 14:20

Цитата:
A*
Не пойдет :
1. У нас нет начальной клетки для поиска. (1,1) не подходит (она может не принадлежать конечному решению).
2. Как будите оценивать цену перемещения "G"? (мы вольны закрашивать в любом месте хоть в начале, хоть в конце, без всяких приоритетов).
3. Да и цена приближения к цели "H" тоже неопределяема. (Иначе будет выбор закраски с максимально-возможным числом закрашиваемых соседних элементов, а это не всегда верно).

С другой стороны я не очень подробно разобрал А*, если есть другое применение этого алгоритма в данном случае будет интересно посмотреть.
Ответить с цитированием
  (#10 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 04.09.2007, 20:28

До качественного исследования матрицы руки не дошли, но решение, если существует, однозначно определяется выбором набора нажатий для клеток первой строки.
Ответить с цитированием
  (#11 (permalink)) Старый
RAPIST RAPIST вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 26.06.2007
По умолчанию 05.09.2007, 14:13

Цитата:
До качественного исследования матрицы руки не дошли, но решение, если существует, однозначно определяется выбором набора нажатий для клеток первой строки.
Тогда выходит перебор всех вариантов нажатия первой строки? Да, пока самый верный вариант. Если не будет других мыслей попробую проработать эту. (1-ая странность: 4*4 собирается при любой выборке первой строки, разница шагов варьируется от 4 до 8 )
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как написать игру для PALM iporozov PalmOS 12 15.05.2017 00:21
Как написать игру шашки *Vladimir* Java 12 06.01.2012 18:21
Написать игру шашки на С++ Репрезендум Вопросы начинающих программистов 2 21.11.2011 23:22
О счастливчик как написать игру moonstorm Вопросы начинающих программистов 12 29.07.2011 16:23
Как написать игру пятнашки Алексеи4 Вопросы начинающих программистов 0 04.06.2011 19:40
Как написать маленькую квест-игру на С++ Fomb Вопросы начинающих программистов 4 07.01.2011 15:24
Пятнашки как написать похожую игру nataliano Delphi 3 29.01.2008 01:39
Написать компьютерную игру точки Underminer Вопросы начинающих программистов 4 23.02.2007 02:28
Как написать игру морской бой imported_SwIFT Lisp 1 16.06.2006 17:52
На чем лучше написать 3d игру Ноябрь Вопросы начинающих программистов 12 23.01.2006 13:28
Как написать игру 21 очко RahXephon Pascal 50 29.11.2005 00:19
Snake3d как написать игру konstantinus Зацените! 0 30.08.2005 13:31



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов