Помогите с задачей на логику или комбинаторику

[TDz]

Нужно выложить доминошки (их 28 всего насколько я знаю) так чтобы начиналось с 1 и заканчивалось 6.

Правила игры в домино думаю все знают. Я пытался создать таблицу чтоб решить комбинатрикой - с помощью графической леснички пости складывается - н овсё равно пару остаёться.

Может кто-то сталкивался с такой задей или знает алгоритм или вообще имеет какие-то мысли - помогите плз

[dyr_farot]

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

[TDz]

Problema v tom shto nado ispolzovat vse kosti a kazhdij raz podhodjashih minimum neskolko. Mne sobsno ne progu nado napisat a prosto zadachu reshit - najti takuju cepochku kotoraja ispolzuja vse dominoshki nachinaecca s 1 a konchaecca 6

[dyr_farot]

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

[TDz]

ja hot po softu no ne siljon v programminge
toest prosto nado napisat progu dlja perebora vseh variantov?

[dyr_farot]

совсем проще говоря -- да

[TDz]

Itogo immem
mnozhestvo domino - {00, 01,02,03,04,05,06,11,12,13,14,15,16,22,23,24,25,26,33,34,35,36,44,45,4 6,55,56,66}

pravilo slozhenija abs(domino1-domino2)==10 || abs(domino1-domino2)<=6
toest nado proverit 27! variantov

Ja poka raberacca budu kak eto sdelat bez 27 pod-ciklov mog bi plz pomoch s kodom dlja generacii vsego lista - toest prosto shtob sgeneriroval ves spisok variantov a ja ego sam rasparsju i videru nuzhnuju stroku ottuda

[dyr_farot]

начал код ваять и понял что правил не помню
кость 2:0 и 0:2 -- одинаковы или их две
+ сколько всего костей?

[TDz]

Tolko odna. Kostej 28 kazhecca

added: Pereschital spisok shto daval vishe - taki 28

[Ghost]

TDz
Вот, наковырял на делфе консольную прогу (в турбо-паскале - Stack Overflow ). Только работает она очень долго. Сижу думаю, как ее уменьшить...

program domino;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  n = 28;
  d: array [1..28] of byte = (
    00, 01, 02, 03, 04, 05, 06,
        11, 12, 13, 14, 15, 16,
            22, 23, 24, 25, 26,
                33, 34, 35, 36,
                    44, 45, 46,
                        55, 56,
                            66);

var
  r: string;

procedure outDomino(s: string);
var
  i: byte;
begin
  for i := 1 to length(s) do write(d[ord(s[i])]:3);
  writeln;
end;

procedure chain(s: string; last: byte); far;
var
  i: byte;
begin
  if r <> '' then exit;
  if length(s) = n then begin
    if last = 6 then r := s;
  end else begin
    for i := 1 to n do if pos(chr(i), s) = 0 then begin
      if ((d[i] mod 10) = last) or ((d[i] div 10) = last) then
        chain(s + chr(i), (d[i] mod 10) + (d[i] div 10) - last);
    end;
  end;
end;

begin
  r := '';
  chain('', 1);
  writeln('result:');
  outDomino(r);
end.

[Saruman]

Имхо, рекурсия тут не катит - слишком много вариантов для перебора получается. Нужно по-другому как-то подходить.

[Ghost]

Гыхм... Выкинул дупли (один черт потом можно вставить в любое место) и сделал отсечение неполных цепочек, если не осталось костей с 6-кой. Все равно прога что-то долго перебирает... Думаю дальше....

Сижу и вот и думаю: а с использованием всех костей точно можно выстроить цепочку с разными числами на концах? Потому что, смотрю на строки, которые выдает прога - получается постоянно цепочка с 1 на концах...

Прога не решаема
Объясняю: количество костей с одинаковыми значениями (исключаю дупли - они никакой роли ни на что не влияют) четно, но 1 и 6 в наборе должно быть нечетное число. Если выкинуть 1-6, задачу решить можно. А с данными условиями - нельзя

[Saruman]

Угум, Ghost прав. Привожу другое доказательство.
Представим набор домино в виде графа, вершины 0-7 соответственно номерам на костяшках домино, каждая костяшка - ребро, соединяющее соответствующие вершины. Тогда для того, чтобы получить незамкнутую цепочку костяшек (как в условии задачи), нужно, чтобы ровно две вершины имели нечетное число ребер. В нашем же случае число ребер у всех вершин четно => имеет только замкнутые цепочки.
Если нужно получить незамкнутую цепочку, нужно из полного набора домино удалить одну костяшку (не дубль).

PS: условие взято из решения к задаче про домино вот здесь

[Ghost]

Saruman
Добавлю еще то, что удалять нужно именно 1-6. Если удалить другую, то и на концах цепочки будут значения с удаленной костяшки. О как

[TDz]

Тоесть спользуя все доминошки можно сделать только неразрывную цепь. Чтобы получить цепочку как надо надо вынять один элемент - в данном случае 1-6 ака 6-1

[Saruman]

TDz
Аха, именно.

[dyr_farot]

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

[TDz]

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

[dyr_farot]

так они ложаться так ( если не ошибаюсь):

4
_
2
1|2 2|2 2|3
2
_
5
а если выкладывать именно цепочкой нужно...

с пробелами проблема
боковые костяшки -- над 2/2

[TDz]

hm da eto vopros
nado obmozgovat