ในวิทยาการคอมพิวเตอร์ลิงก์เต้นรำ ( DLX ) เป็นเทคนิคสำหรับการเพิ่มและลบโหนดจากรายการเชื่อมโยงสองทางแบบ วงกลม มีประโยชน์อย่างยิ่งในการใช้งาน อัลกอริ ทึมแบบย้อนกลับ อย่างมีประสิทธิภาพ เช่นอัลกอริทึม X ของ Knuthสำหรับ ปัญหาการครอบคลุม ที่แน่นอน^{[ 1 ]} อัลก อริทึม X เป็นอัลกอริ ทึมแบบ ย้อน กลับ แบบ เรียกซ้ำ ไม่แน่นอนแบบค้นหาเชิงลึก ที่ค้นหา คำตอบทั้งหมดของ ปัญหา การครอบคลุมที่แน่นอนปัญหาการครอบคลุมที่แน่นอนที่รู้จักกันดีบางส่วน ได้แก่การปูกระเบื้องปัญหา n ราชินีและซูโดกุ

ชื่อ " dancing links " ซึ่งเสนอโดยDonald Knuthมาจากวิธีการทำงานของอัลกอริทึม โดยการวนซ้ำของอัลกอริทึมทำให้ลิงก์ "เต้นรำ" กับลิงก์คู่เพื่อให้ดูเหมือน "การเต้นรำที่ออกแบบท่าเต้นอย่างประณีต" Knuth ให้เครดิต Hiroshi Hitotsumatsu และ Kōhei Noshita ว่าเป็นผู้คิดค้นแนวคิดนี้ในปี 1979 ^{[ 2 ]}แต่เป็นบทความของเขาที่ทำให้แนวคิดนี้เป็นที่นิยม

แนวคิดของ DLX มาจากการสังเกตว่า ในรายการเชื่อมโยงสองทาง แบบวงกลม ของโหนดต่างๆ นั้น

x.ซ้าย.ขวา ← x.ขวา; x.ขวา.ซ้าย ← x.ซ้าย; 

จะลบโหนดx ออก จากรายการ ในขณะที่

x.ซ้าย.ขวา ← x; x.ขวา.ซ้าย ← x; 

ฟังก์ชันนี้ จะคืน ค่าตำแหน่ง ของ xในรายการ โดยสมมติว่า x.right และ x.left ยังคงไม่เปลี่ยนแปลง ฟังก์ชันนี้ใช้งานได้ไม่ว่ารายการจะมีจำนวนองค์ประกอบกี่ตัว แม้ว่าจะมีเพียง 1 ตัวก็ตาม

Knuth สังเกตว่าการใช้งานอัลกอริทึม X ของเขาแบบพื้นฐานจะใช้เวลานานมากเกินไปในการค้นหาเลข 1 เมื่อเลือกคอลัมน์ จะต้องค้นหาเลข 1 ทั่วทั้งเมทริกซ์ เมื่อเลือกแถว จะต้องค้นหาเลข 1 ทั่วทั้งคอลัมน์ หลังจากเลือกแถวแล้ว จะต้องค้นหาเลข 1 ทั้งในแถวนั้นและอีกหลายคอลัมน์ เพื่อปรับปรุงเวลาในการค้นหาจากความซับซ้อน O(n) เป็น O(1) Knuth จึงได้สร้างเมทริกซ์แบบสปาร์สขึ้น มา โดยเก็บเฉพาะเลข 1 ไว้เท่านั้น

ตลอดเวลา โหนดแต่ละโหนดในเมทริกซ์จะชี้ไปยังโหนดที่อยู่ติดกันทางซ้ายและขวา (เลข 1 ในแถวเดียวกัน) ด้านบนและด้านล่าง (เลข 1 ในคอลัมน์เดียวกัน) และส่วนหัวของคอลัมน์นั้น (อธิบายไว้ด้านล่าง) แต่ละแถวและคอลัมน์ในเมทริกซ์จะประกอบด้วยรายการโหนดแบบเชื่อมโยงสองทางแบบวงกลม

แต่ละคอลัมน์จะมีโหนดพิเศษที่เรียกว่า "ส่วนหัวของคอลัมน์" ซึ่งจะรวมอยู่ในรายการคอลัมน์ และจะสร้างแถวพิเศษ ("แถวควบคุม") ซึ่งประกอบด้วยคอลัมน์ทั้งหมดที่ยังคงมีอยู่ในเมทริกซ์

สุดท้ายนี้ ส่วนหัวของแต่ละคอลัมน์อาจติดตามจำนวนโหนดในคอลัมน์นั้นได้ (หรือไม่ก็ได้) ดังนั้น การค้นหาคอลัมน์ที่มีจำนวนโหนดน้อยที่สุดจึงมีความซับซ้อน O( n ) แทนที่จะเป็น O( n × m ) โดยที่nคือจำนวนคอลัมน์และmคือจำนวนแถว การเลือกคอลัมน์ที่มีจำนวนโหนดน้อยเป็นวิธีการเชิงอนุมานที่ช่วยปรับปรุงประสิทธิภาพในบางกรณี แต่ไม่ใช่สิ่งจำเป็นสำหรับอัลกอริทึม

ในอัลกอริธึม X แถวและคอลัมน์จะถูกลบออกและนำกลับมาใส่ในเมทริกซ์อย่างสม่ำเสมอ การลบจะพิจารณาจากการเลือกคอลัมน์และแถวในคอลัมน์นั้น หากคอลัมน์ที่เลือกไม่มีแถวใดๆ เมทริกซ์ปัจจุบันจะไม่สามารถแก้ไขได้และต้องย้อนกลับ เมื่อเกิดการลบ คอลัมน์ทั้งหมดที่แถวที่เลือกมีค่าเป็น 1 จะถูกลบออก พร้อมกับแถวทั้งหมด (รวมถึงแถวที่เลือก) ที่มีค่าเป็น 1 ในคอลัมน์ใดๆ ที่ถูกลบออก คอลัมน์ถูกลบออกเนื่องจากมีข้อมูลเต็มแล้ว และแถวถูกลบออกเนื่องจากขัดแย้งกับแถวที่เลือก ในการลบคอลัมน์เดียว ขั้นแรกให้ลบส่วนหัวของคอลัมน์ที่เลือกออก จากนั้น สำหรับแต่ละแถวที่คอลัมน์ที่เลือกมีค่าเป็น 1 ให้วนลูปผ่านแถวนั้นและลบออกจากคอลัมน์อื่นๆ (ซึ่งจะทำให้แถวเหล่านั้นไม่สามารถเข้าถึงได้และเป็นวิธีป้องกันความขัดแย้ง) ทำซ้ำการลบคอลัมน์นี้สำหรับแต่ละคอลัมน์ที่แถวที่เลือกมีค่าเป็น 1 ลำดับนี้ทำให้มั่นใจได้ว่าโหนดที่ถูกลบออกจะถูกลบออกเพียงครั้งเดียวและในลำดับที่คาดเดาได้ เพื่อให้สามารถย้อนกลับได้อย่างเหมาะสม หากเมทริกซ์ที่ได้ไม่มีคอลัมน์ แสดงว่าคอลัมน์ทั้งหมดถูกเติมแล้ว และแถวที่เลือกไว้จะเป็นคำตอบ

ในการย้อนกลับ กระบวนการข้างต้นจะต้องถูกย้อนกลับโดยใช้อัลกอริทึมที่สองที่กล่าวไว้ข้างต้น ข้อกำหนดประการหนึ่งของการใช้อัลกอริทึมนั้นคือ การย้อนกลับจะต้องทำในลักษณะที่ตรงกันข้ามกับการกำจัดอย่างแม่นยำ บทความของ Knuth ให้ภาพที่ชัดเจนเกี่ยวกับความสัมพันธ์เหล่านี้และวิธีการทำงานของการลบและการแทรกโหนดใหม่ และให้การผ่อนปรนข้อจำกัดนี้เล็กน้อย

นอกจากนี้ยังสามารถแก้ปัญหา one-cover ได้ โดยที่ข้อจำกัดบางอย่างเป็นทางเลือก แต่สามารถเป็นจริงได้เพียงครั้งเดียวเท่านั้น Dancing links รองรับข้อจำกัดเหล่านี้ด้วยคอลัมน์หลักที่ต้องเติม และคอลัมน์รองที่เป็นทางเลือก ซึ่งจะเปลี่ยนการทดสอบคำตอบของอัลกอริทึมจากเมทริกซ์ที่ไม่มีคอลัมน์ ไปเป็นเมทริกซ์ที่ไม่มีคอลัมน์หลัก และหากใช้ฮิวริสติกของการหาค่าต่ำสุดของหนึ่งในคอลัมน์ ก็จะต้องตรวจสอบเฉพาะภายในคอลัมน์หลักเท่านั้น Knuth ได้กล่าวถึงข้อจำกัดที่เป็นทางเลือกที่นำมาใช้กับ ปัญหา n queensเส้นทแยงมุมของกระดานหมากรุกแสดงถึงข้อจำกัดที่เป็นทางเลือก เนื่องจากเส้นทแยงมุมบางเส้นอาจไม่ได้ครอบครอง หากเส้นทแยงมุมใดถูกครอบครอง ก็สามารถครอบครองได้เพียงครั้งเดียวเท่านั้น

• อัลกอริทึมการแก้ซูโดกุ

• การใช้งานDancing Links แบบกระจายศูนย์ ในรูป แบบตัวอย่างHadoop MapReduce
• โปรแกรมโอเพนซอร์สที่เขียนด้วยภาษาซี สำหรับแก้ปริศนา Exact Cover โดยใช้ Algorithm X และ Dancing Links มีตัวอย่างสำหรับซูโดกุและปริศนาตารางตรรกะ
• แพ็คเกจ NuGet DlxLib - ไลบรารีคลาส C# ที่ใช้งาน DLX
• แพ็กเกจ npm dlxlib - ไลบรารี JavaScript ที่ใช้งาน DLX
• dancing-links-c++ - ไลบรารี C++ ที่ใช้งาน DLX
• go-dancing-links - ไลบรารี GoLang ที่ใช้งาน DLX
• DLXPy - ไลบรารี Python ที่ใช้งาน DLX
• นี่คือการใช้งานลิงก์เต้นรำแบบดั้งเดิมของ Donald Knuthที่เขียนด้วยภาษา CWEB (ดูส่วนหน้าสำหรับแก้ปริศนาซูโดกุ ของเขาด้วย )
• การบรรยายคริสต์มาสประจำปีครั้งที่ 24 ของโดนัลด์ คนูธ: การเชื่อมโยงผ่านการเต้นรำ