A Backtracking Algorithm

By Wolfgang Laun
Date: Thursday, 14 August 2008 13:30
Duration: 30 minutes
Language:

You can find more information on the speaker's site:

Talk: http://members.inode.at/w.laun/backtrack/backtrack.html

A paper by Donald E. Knuth investigates a number of NP-complete problems that can be treated jointly as "exact cover problems". This paper discusses options for implementing Knuth's algorithm in Perl. An alternative way of representing the boolean matrix that represents the search space in its stepwise reduced form is proposed and compared by running various tests.

One application of this algorithm deals with pentominoes where the classic problems is defined by the 12 pentominos in all distinct transformations being placed on all possible squares of the area to be covered. (Typical areas are the rectangles: 6x10, 5x12, 4x15 and 3+20, and 8x8 squares reduced by 4 unit squares.) A simple Perl/Tk canvas produces nice images.

As the algorithm does not make any assumptions the covering pieces, also three (or more) dimensional covering problems may be attacked. The Soma cube (invented by Piet Hein) is the other problem used for illustrating the algorithms.

It has to be admitted that this class of problems is hard on Perl, which is, after all, an interpreted language. Nevertheless, it pays to investigate an algorithm like this with Perl, where both procedural and object oriented paradigms can be applied to investigate algorithmic variants.

Attended by: Henrik Tougaard (‎htoug‎), Paul-Christophe Varoutas, Jacob Bunk Nielsen, Maciej Misiak (‎grizzley‎), Martin Schipany (‎ElCondor‎), David Leadbeater (‎dg‎),