2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как правильно перемешать пятнашки 4х4?
Сообщение27.05.2015, 21:33 


24/05/09

2054
Если тупо рэндомом - они не всегда собираются. Можно проверить расстановку рэндомом на собираемость?
Можно конечно много и случайно гонять по полю белый квадратик, но этот лёгкий путь я использую, если других не найдётся.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение27.05.2015, 22:05 
Заслуженный участник
Аватара пользователя


27/04/09
27204
Первый же результат по randomizing fifteen в гугле: http://www.sitepoint.com/randomizing-sliding-puzzle-tiles. Если бы я сразу знал, как игра называется правильно, результат получился бы вообще наверняка (а так это просто была удача).

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение27.05.2015, 22:27 


24/05/09

2054
По русски ничего нету?

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение27.05.2015, 22:40 
Заслуженный участник
Аватара пользователя


27/04/09
27204
Что ж, не запрещаю ввести в гугл и русскоязычный запрос.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение27.05.2015, 22:47 
Супермодератор
Аватара пользователя


09/05/12
21216
Кронштадт
Назовем инверсией некоторого положения фишек положение, получающееся из первого перестановкой двух соседних по горизонтали или вертикали квадратиков (непустых). Если стартовое положение можно перевести в желаемое с помощью четного числа инверсий, то задача решается. Если с помощью нечетного числа - нет.

Все. Осталось написать код, что, в общем, тривиально. :-)

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение29.05.2015, 19:34 


24/05/09

2054
Забил на алгоритмы, делаю 1000 случайных ходов и ещё - до тех пор, пока не очистится правый нижний квадрат. Нормально всё перемешивается.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение29.05.2015, 21:11 
Заслуженный участник
Аватара пользователя


27/04/09
27204
Alexu007 в сообщении #1021200 писал(а):
Забил на алгоритмы
:facepalm:

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение30.05.2015, 12:31 


24/05/09

2054
А и наплевать, главное работает. Вон какие симпатяшки, и рисовать ничего не пришлось. В роли квадратиков выступают обычные кнопки:

Изображение

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение30.05.2015, 17:21 
Заслуженный участник
Аватара пользователя


27/04/09
27204
Alexu007 в сообщении #1021489 писал(а):
А и наплевать, главное работает.
Удачи с размером $50\times50$.

Кстати, опять же, мало кто с первого взгляда поймёт, что такое FIFTEENs (по ссылке же можно увидеть, что это называется по-английски sliding puzzle), и чего именно change (думаю, даже new было бы куда ясней).

Alexu007 в сообщении #1021489 писал(а):
В роли квадратиков выступают обычные кнопки:
До этого в своё время даже я додумался. :roll:

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение30.05.2015, 19:17 
Заслуженный участник


04/05/09
4515
arseniiv в сообщении #1021568 писал(а):
Кстати, опять же, мало кто с первого взгляда поймёт, что такое FIFTEENs (по ссылке же можно увидеть, что это называется по-английски sliding puzzle), и чего именно change (думаю, даже new было бы куда ясней).
А ещё лучше "Shuffle".

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение30.05.2015, 20:43 
Заслуженный участник
Аватара пользователя


27/04/09
27204
Да, это самое лучшее! Пытался вспомнить, но вспомнил не то слово scramble, поглядел в словаре и решил не писать, хотя в одной игре, когда ходы заканчивалось, перемешивание звалось именно так.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение12.07.2015, 13:12 
Аватара пользователя


19/11/14

80
д. Новые Кабаны =)
venco в сообщении #1021612 писал(а):
А ещё лучше "Shuffle".
А еще лучше - "New game" =). "Shuffle" для процедуры в коде пойдет ).
Alexu007 в сообщении #1021200 писал(а):
Забил на алгоритмы, делаю 1000 случайных ходов и ещё - до тех пор, пока не очистится правый нижний квадрат. Нормально всё перемешивается.

Свои плюсы ) легче сделать разные уровни сложности. Легкий уровень (10-20) перемешиваний, средний (20-30) перемешиваний и сложный.
arseniiv в сообщении #1021568 писал(а):
Удачи с размером $50\times50$.
Дык в такое кто играть будет? ))
arseniiv в сообщении #1020527 писал(а):
Первый же результат по randomizing fifteen в гугле: http://www.sitepoint.com/randomizing-sliding-puzzle-tiles. Если бы я сразу знал, как игра называется правильно, результат получился бы вообще наверняка (а так это просто была удача).
За ссылку спасибо. Я вот нарыл только для квадратных http://e-maxx.ru/algo/15_puzzle.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение12.07.2015, 17:31 
Заслуженный участник
Аватара пользователя


27/04/09
27204
nenefertiti в сообщении #1036140 писал(а):
Дык в такое кто играть будет? ))
Вопрос был по алгоритму, а о применимости автор ничего не говорил. Значит, подразумевать её не нужно.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение12.07.2015, 17:45 
Заслуженный участник
Аватара пользователя


09/09/14
6230

(Оффтоп)

arseniiv в сообщении #1020527 писал(а):
Если бы я сразу знал, как игра называется правильно, результат получился бы вообще наверняка (а так это просто была удача).

Есть простой способ в подобной ситуации правильно перевести нужный термин (а также найти все релевантные переводы) на другой язык (иногда вообще незнакомый, типа китайского): найти нужное в ру-вики и перейти на нужное-вики.

 Профиль  
                  
 
 Re: Как правильно перемешать пятнашки 4х4?
Сообщение12.08.2015, 20:40 


30/06/14
47
Чтобы перемешать пятнашки, нужно рандомно заполнить первые 15 ячеек числами от 1 до 15 (16-я пустая).
Далее нужно проверить будет ли складываться полученная комбинация. Если не будет, нужно поменять местами любые 2 числа.
Как я понимаю проблема именно в том чтобы проверить является ли полученная комбинация корректной, т.е. складываемой?

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

допустим у нас есть масив
A[1..15]: array of integer;

тогда функция проверки (на Delphi) будет выглядеть так (правда при проверке она испортит проверяемый массив, так что нужно либо сделать заранее копию массива, либо чуть изменить алгоритм).
код: [ скачать ] [ спрятать ]
Используется синтаксис Delphi
function check:boolean;
var
p,k,i:integer;
begin
  Result:=true;
  for i:=1 to 14 do
  begin
    p:=i;
    while i<>A[p] do
    begin  
      k:=p;
      p:=A[p];
      A[k]:=k;
      Result:= not Result;
    end;
    A[p]:=p;
  end;
end;


Смысл в том что мы перебираем все закольцованные цепочки переставленных элементов.
допустим a[1]=4, a[4]=10, a[10]=1, тогда у нас это является цепочкой с длинной 3
каждая цепочка с четным числом элементов инвертирует значение функции, а с нечетным не меняет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group