Как правильно перемешать пятнашки 4х4?

[Alexu007]

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

[arseniiv]

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

[Alexu007]

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

[arseniiv]

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

[Pphantom]

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

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

[Alexu007]

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

[arseniiv]

Alexu007 в сообщении #1021200 писал(а):

Забил на алгоритмы

[Alexu007]

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

[arseniiv]

Alexu007 в сообщении #1021489 писал(а):

А и наплевать, главное работает.

Удачи с размером $50\times50$.

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

Alexu007 в сообщении #1021489 писал(а):

В роли квадратиков выступают обычные кнопки:

До этого в своё время даже я додумался.

[venco]

arseniiv в сообщении #1021568 писал(а):

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

А ещё лучше "Shuffle".

[arseniiv]

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

[nenefertiti]

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.

[arseniiv]

nenefertiti в сообщении #1036140 писал(а):

Дык в такое кто играть будет? ))

Вопрос был по алгоритму, а о применимости автор ничего не говорил. Значит, подразумевать её не нужно.

[grizzly]

(Оффтоп)

arseniiv в сообщении #1020527 писал(а):

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

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

[glukmaker]

Чтобы перемешать пятнашки, нужно рандомно заполнить первые 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
каждая цепочка с четным числом элементов инвертирует значение функции, а с нечетным не меняет.