XDLX: A Memory-Efficient Solution for Backtracking Applications in Big Data Environment using XOR-based Dancing Links

Abstract

Interactive and Backtracking applications often require undoing certain recent operations and updates made to the underlying data structures. The concept of dancing links has made such reverting operations easier and efficient by repeatedly performing unlinking and re-linking of pointers in complex data structures involving circular multiply linked lists. This paper extends the idea of dancing links to XOR linked lists, the memory efficient counterpart of doubly linked lists to develop XDLX, a more space efficient algorithm than DLX to solve exact cover problems without compromising the timing efficiency. Owing to the NP-Complete nature of the exact cover problem, any NP-complete problem can be reduced to it and solved using the proposed memory-efficient dancing links based algorithm, XDLX. The algorithm can be effectively used to solve any backtracking application and will prove to be a significant contribution towards the programming of memory-constrained environments such as embedded systems.