Играјуће везе
У компјутерској науци, играјуће везе, познатије као DLX је техника која је препоручена од стране Доналда Кнута као ефикасан метод имплементације Кнутовог алгоритма Икс. Алгоритам Икс је рекурзиван, недетерминистички, дубински, бек-трекинг алгоритам који проналази сва решења за проблем тачног омотача. Неки од познатијих проблема те врсте су проблем теселације, проблем n дама и судоку.
Техника је добила име играјуће везе због начина на који тај алгоритам функционише, због тога што везе "играју" са суседним везама у веома добро кореографисаном плесу. Име су осмислили јапански информатичари Хироши Хитотумату и Кохеи Ношита 1979. године, али је Кнут популаризовао овај назив.

Имплементација 

Идеја DLX се заснива на томе да у дупло повезаној кружној листи

x.levo.desno ← x.desno;

x.desno.levo ← x.levo;

избацује чвор x из листе, а

x.levo.desno ← x;

x.desno.levo ← x;

враћа x у листу.

Ово важи чак иако је број чворова у листи једнак 1.

У наивној имплементацији алгоритма икс, превише времена се троши на тражењу јединица у матрици, јер када изаберемо једну колону, јединице се траже у целој матрици, када се бира ред, јединице се траже у целој колони, а пошто изаберемо ред, у том реду и у више колона тражимо јединице.

Да би се сложеност ове претраге смањио од О(н) на О(1), Кнут је имплементирао ретку матрицу, то јест матрицу у којој су само 1 и 0.

Свака јединица у тој матрици садржи показивач на јединице лево и десно од себе, и изнад и испод себе и на заглавље колоне. Тако се матрица састоји од кружно повезаних листа које чине редове и колоне.

Колоне 

Свака колона у DLX има своје заглавље која заједно чине први ред матрице. Свако заглавље колоне може да чува број елемената у својој колони тако да налажење колоне са најмање елемената буде сложености О(n) уместо О(n*m) где је n број колона, а m број редова матрице.

У Алгоритму Икс, редови и колоне се стално уклањају и поново уписују у матрицу. Ако се изабере колона која нема редове у себи, проблем је нерешив и морамо бек-трековати. У елиминисаном реду, свака колона која је имала 1 у том реду се брише заједно са свим редовима који имају 1 у тим колонама.

Референце

Спољашње везе 

 -{A distributed Dancing Links implementation as a Hadoop MapReduce example}-

Алгоритми претраживања
Судоку
У компјутерској науци , играјуће везе , познатије као DLX је техника која је препоручена од стране Доналда Кнута као ефикасан метод имплементације Кнутовог алгоритма Икс . Алгоритам Икс је рекурзиван , недетерминистички , дубински , бек-трекинг алгоритам који проналази сва решења за проблем тачног омотача . Неки од познатијих проблема те врсте су проблем теселације , проблем n дама и судоку . Техника је добила име играјуће везе због начина на који тај алгоритам функционише , због тога што везе " играју " са суседним везама у веома добро кореографисаном плесу . Име су осмислили јапански информатичари Хироши Хитотумату и Кохеи Ношита године , али је Кнут популаризовао овај назив . Имплементација Идеја DLX се заснива на томе да у дупло повезаној кружној листи x.levo.desno ← x.desno ; x.desno.levo ← x.levo ; избацује чвор x из листе , а x.levo.desno ← x ; x.desno.levo ← x ; враћа x у листу . Ово важи чак иако је број чворова у листи једнак У наивној имплементацији алгоритма икс , превише времена се троши на тражењу јединица у матрици , јер када изаберемо једну колону , јединице се траже у целој матрици , када се бира ред , јединице се траже у целој колони , а пошто изаберемо ред , у том реду и у више колона тражимо јединице . Да би се сложеност ове претраге смањио од О( н ) на О( 1 ) , Кнут је имплементирао ретку матрицу , то јест матрицу у којој су самои Свака јединица у тој матрици садржи показивач на јединице лево и десно од себе , и изнад и испод себе и на заглавље колоне . Тако се матрица састоји од кружно повезаних листа које чине редове и колоне . Колоне Свака колона у DLX има своје заглавље која заједно чине први ред матрице . Свако заглавље колоне може да чува број елемената у својој колони тако да налажење колоне са најмање елемената буде сложености О( n ) уместо О( n*m ) где је n број колона , а m број редова матрице . У Алгоритму Икс , редови и колоне се стално уклањају и поново уписују у матрицу . Ако се изабере колона која нема редове у себи , проблем је нерешив и морамо бек-трековати . У елиминисаном реду , свака колона која је ималау том реду се брише заједно са свим редовима који имајуу тим колонама . Референце Спољашње везе -{ A distributed Dancing Links implementation as a Hadoop MapReduce example }- Алгоритми претраживања Судоку