flibs/backtracking(n) 1.1 "flibs"

NAME

flibs/backtracking - Backtracking

    TABLE OF CONTENTS
    SYNOPSIS
    DESCRIPTION
    ROUTINES
    TODO
    COPYRIGHT

SYNOPSIS

call runtests( testproc )

call test( proc, text )

call assert_true( cond, text )

exists = funit_file_exists( filename )

call funit_get_lun( lun )

call funit_remove_file( filename )

call funit_make_empty_file( filename )

The module Backtracking implements in a general way a well-known algorithm to solve certain combinatorial problems. The module actually consists of a single routine that forms the framework of the algorithm and is to be used in conjunction with a small set of user-defined routines that implement the specific problem.

The backtracking technique is especially useful if you can build a solution in stages. The classic example is the "eight queens" problem, where you must place eight queens on a chess board in such a way that none can get another in one move. A little thought shows that each queen must be placed in its own column (or row). Placing the first queen in the first column gives us eight possibilities. Placing the second is only possible if it is not within the range of the first one.

If it is, it makes no sense to continue so we can eliminate in the second step a whole subset of possible configurations, namely those with the second queeen within range of the first. We can continue building up a partial solution in this way until we finally have eight queens on the board.

The idea of the module is that all the data that describe a possible partial solution to the problem are contained in a derived type called SOLUTION_DATA. Then the user-defined routine generate generates a new set of partial solutions based on this.

The new set is examined to see if any is acceptable within the context of the problem, which is done via another user-defined routine.

Each acceptable solution within this new step may give rise to its own set of further solutions. This way the partial solutions are extended in each step until finally a complete solution is found.

ROUTINES

The module backtracking contains

call runtests( testproc )

Routine to start the unit tests. It checks if the file "funit.run" exists. If so, it will call the subroutine testproc that was passed. Otherwise it will simply return, so that the ordinary program execution may continue.

If the subroutine testproc returns, the program stops.

subroutine testproc: Subroutine that calls the individual test routines. It takes no arguments. It wil generally exist of a series of calls to the routine test - see below.

call test( proc, text )

Routine to run the individual unit test routine (emph proc). It decides if the test has not run yet and if so, the test routine is called. Otherwise it is skipped.

test takes care of all administrative details.

Note: to make it possible to use private unit test routines, the source code of this subroutine is kept in a separate file, funit_test.f90 that should be included in an appropriate place in the program's sources. This way, you can make it a private routine in each module. The only public access to the unit testing routines is then via the subroutine testproc that is passed to runtests.

subroutine proc: Subroutine that implements an individual unit test. It takes no arguments. Within each such subroutine the complete unit test is run.
character(len=*), intent(in) text: Text describing the particular unit test. It is printed in the log file.

call assert_true( cond, text )

Routine to check that a condition is true. If not, a message is printed in the log file and the number of failures is increased.

logical cond: The condition to be checked
character(len=*), intent(in) text: Text describing the condition

exists = funit_file_exists( filename )

Logical function to check that a particular file exists

character(len=*), intent(in) filename: Name of the file to be checked

call funit_get_lun( lun )

Subroutine to get a free LU-number

integer, intent(out) lun: Next free LU-number

call funit_remove_file( filename )

Subroutine to remove (delete) a file

character(len=*), intent(in) filename: Name of the file to be removed

call funit_make_empty_file( filename )

Subroutine to make a new, empty file

character(len=*), intent(in) filename: Name of the file to be created

TODO

The following things are still left to do:

Proper inclusion of the routine prolog and epilog
Extension of the set of assertion routines