Кнутов алгоритам Икс
<s>Доналд Кнутов Алгоритам Икс је рекурзиван, недетерминистички, дубински, бек-трекинг алгоритам који налази сва решења проблема тачног омотача који се представља помоћу матрице А, која се састоји из нула и јединица.</s><s>Алгоритам ради тако што се одабире подскуп редова у матрици А тако да се број 1 појави у свакој колони подскупа тачно једном.</s>

<s>Перформансе 
Најмања граница перформансе овог алгоритма је зависно од максималног броја тачних омотача неке инстанце.</s><s>На пример, случај тачног омотача формираног од коцке 2x2 са k чворних копија даје 7k различитих решења, формираних од n=8k скупова, па као функција f(n), где је n број подскупова у почетној фамилији, број тачних омотача је 7n/8, што је приближно 1.275n .</s>

<s>Горње границе перформанси се достижу када имамо три рекурзивна позива величине n-3 што је O(3n/3).</s>

<s>Опис алгоритма 
1. корак:</s>

<s>Ако је матрица А празна, то је уједно и крај проблема и алгоритам се завршава успешно.</s><s>Ако није, прелазимо на корак 2.</s>

<s>2. корак:</s>

<s>Бирамо колону c.</s>

<s>3. корак:</s>

<s>Бирамо ред r тако да је Аr,c=1.</s>

<s>4. корак:</s>

<s>Ред r уносимо у парцијално решење.</s>

<s>5. корак:</s>

<s>За сваку колону ј такву да је Аr, ј=1 гледамо да ли постоји ред i такав да је Аr, ј=1. Ако је одговор потврдан, бришемо тај ред и прелазимо на следећи ред колико их има.</s><s>Пошто смо прошли кроз све редове, бришемо колону ј и понављамо корак 5 све док не исцрпимо све колоне матрице А.</s>

<s>6. корак:</s>

<s>Рекурзивно понављамо ове кораке на новој, смањеној матрици А.</s>

<s>Подалгоритми 
Одабир реда r у трећем кораку је недетерминистички проблем, што значи да ће бити позван подалгоритам одабира реда који као аргумент добија прослеђену матрицу А из које издваја један ред r. Проблем налажења колоне c је детерминистички, али ако је нађена колона c попуњена цела нулама, алгоритам ће се неуспешно завршити.</s>

<s>Ови подалгоритми формирају бинарно стабло претраге са првобитним проблемом као кореном, а где к-ти ниво стабла одговара к изабраних редова.</s><s>Бектрекујемо кроз алгоритам тако што обилазимо стабло дубински у preorder-у.</s>

<s>Имплементација 
Играјуће везе, познатије као DLX су техника имплементирања Алгоритма Икс коју је Кнут сам развио.</s><s>Том техником се креира матрица уз помоћ двоструко повезане листе свих поља која садрже 1. Постоји одвојена листа за јединице у сваком реду и колони, а свака јединица у матрици је повезана са следећом јединицом горе, лево, десно и доле од ње.</s>

<s>Algoritmi pretraživanja</s>

