Das Springerproblem

Die hier angewandte Lösung des Problems basiert auf Backtracking und der Warnsdorff-Heuristik. Die Implementierung ist objektorientiert in PHP, die Animation des Lösungswegs in jQuery. Der komplette Source-Code kann am Ende der Seite eingesehen werden. Zunächst widme ich mich den Lösungsverfahren.

Backtracking

Es wird willkürlich ein möglicher Zug gewählt, bis der Springer sich in einer Sackgasse befindet. Dann wird der letzte Zug zurückgenommen und wenn möglich ein alternativer Zug gewählt. Sollte dies nicht mehr möglich sein, da auch bei diesem Zug schon alle acht Routen ausprobiert worden sind, so wird zusätzlich der vorletzte Zug zurückgenommen und so weiter. Dieser Ansatz findet zu 100% eine Lösung, ist allerdings sehr langsam. In meiner Animation wird nach maximal einer Million Schritten der Backtracking-Algorithmus beendet.

Warnsdorff-Heuristik

Die Heuristik von Warnsdorff besagt, dass der Springer immer zu dem Feld springt, von dem aus er am wenigsten Zugmöglichkeiten hat. Der Algorithmus prüft also bei jedem Zug die Anzahl der Zugmöglichkeiten r des Springers von seinem Zielfeld aus und wählt das Zielfeld mit dem kleinsten r. Der Ansatz erscheint logisch, wenn man bedenkt, dass somit erst Felder abgearbeitet werden, die kaum mehr erreichbar sind, z.B. die Ecken des Schachbretts. Die Heuristik trifft allerdings keine Aussage über den nächsten Zug, falls es mehrere Züge mit gleichem r gibt.

Kombination der beiden Verfahren

Das hier angewandte Lösungsverfahren ist eine Kombination aus Backtracking und der Warnsdorff-Heuristik. Die Warnsdorff-Heuristik kann in der GUI deaktiviert werden um eine Lösung durch reines Backtracking zu erzwingen. Dies gelingt allerdings auf Grund der Laufzeitkomplexität des Backtracking-Verfahrens nur für Felder bis zu einer maximalen Größe von 7 x 7.

Animation der Lösung

Spielfeldgröße X: Spielfeldgröße Y:

Startposition X: Startposition Y:

Animation:

Warnsdorff-Heuristik:

Der Source-Code

Die Klasse Field - field.php

Diese Klasse beschreibt das Feld, auf dem sich der Springer bewegen kann. Das Feld kann als HTML und als JSON-String (wird in der Animation verwendet, siehe unten) ausgegeben werden. Weitere Erläuterungen bieten die Attribut- und Methoden-Kommentare.

class Field {
    
    /**
     * Integer - width of the field
     */
    protected $width;

    /**
     * Integer - height of the field
     */
    protected $height;

    /**
     * Array - matrix, which contains the field values
     */
    protected $field;

    /**
     * Construct - sets width, height and default values of the field
     *
     * @param integer $width of the field
     * @param integer $height of the field
     */
    public function __construct($width, $height) {
        $this->setWidth($width);
        $this->setHeight($height);
        $this->setDefaultField();
    }

    /**
     * Sets the width of the field, minimum is 5
     *
     * @param integer $width of the field
     */
    public function setWidth($width) {
        if ($width < 5) {
            $this->width = 5;
        } else {
            $this->width = $width;
        }
    }

    /**
     * Sets the height of the field, minimum is 5
     *
     * @param integer $height of the field
     */
    public function setHeight($height) {
        if ($height < 1) {
            $this->height = 5;
        } else {
            $this->height = $height;
        }
    }

    /**
     * Returns the width of the field
     *
     * @return integer $width
     */
    public function getWidth() {
        return $this->width;
    }

    /**
     * Returns the height of the field
     *
     * @return integer $height
     */
    public function getHeight() {
        return $this->height;
    }

    /**
     * Sets all field values to zero
     *
     * @return void
     */
    public function setDefaultField() {
        for ($i = 0; $i < $this->height; $i++) {
            for ($j = 0; $j < $this->width; $j++) {
                $this->field[$i][$j] = 0;
            }    
        }
    }

    /**
     * Sets a field with coordinate x and y to the given value
     *
     * @param integer $x x-coordinate
     * @param integer $y y-coordinate
     * @param integer $value to be set
     *
     * @return void
     */
    public function setField($x, $y, $value) {
        $this->field[$y][$x] = $value;
    }

    /**
     * Returns a field value by the given coordinates
     *
     * @param integer $x x-coordinate
     * @param integer $y y-coordinate
     *
     * @return void
     */
    public function getField($x, $y) {
        return $this->field[$y][$x];
    }

    /**
     * Checks if the value of the field is zero (false) or not (true)
     *
     * @param integer $x x-coordinate
     * @param integer $y y-coordinate
     *
     * @return boolean false, if value of field is zero, else true
     */
    public function isVisited($x, $y) {
        return !($this->field[$y][$x] === 0);
    }

    /**
     * Returns the size of the field
     *
     * @return integer $size
     */
    public function getSize() {
        return $this->getHeight() * $this->getWidth();
    }

    /**
     * Returns the field as HTML
     *
     * @return string $output HTML output of the field
     */
    public function printField() {
        $output = '<p>';
        for ($i = 0; $i < $this->height; $i++) {
            for ($j = 0; $j < $this->width; $j++) {
                $output .= $this->field[$i][$j] . ' ';
            }   
            $output .= '<br />'; 
        }
        $output .= '</p>';
    }

    /**
     * Returns the field as JSON array
     *
     * @return string $output JSON array of the field
     */
    public function printFieldJSON() {
        return json_encode($this->field);
    }
}

Die Klasse Knight - knight.php

Diese Klasse beschreibt den Zustand des Springers und seine Methoden. Nach jedem erfolgreichen Zug wird das Attribut $counter um eins erhöht. Ist der Wert von $counter gleich der Anzahl der Felder, so hat der Algorithmus eine Lösung gefunden. Es können auch Züge rückgängig gemacht werden. Alle möglichen Züge des Springers sind im Array $directions gespeichert. Folgende acht Zugmöglichkeiten ergeben sich.

2 Felder nach oben, 1 Feld nach links
2 Felder nach oben, 1 Feld nach rechts
1 Feld nach oben, 2 Felder nach rechts
1 Feld nach unten, 2 Feld nach rechts
2 Felder nach unten, 1 Feld nach rechts
2 Felder nach unten, 1 Feld nach links
1 Feld nach oben, 2 Felder nach links
1 Feld nach unten, 2 Felder nach links

Die Methode canJump() prüft, ob ein Zug aus $directions möglich ist, d.h. ob das Zielfeld innerhalb des Spielfeldes ist und noch nicht besucht wurde. Ist die Warnsdorff-Heuristik aktiviert, so wird der nächste Zug mit der Methode warnsdorffRule() berechnet.

Damit schon versuchte, fehlgeschlagene Züge nach einer Zugrücknahme nicht nochmals probiert werden, werden diese Züge in einer Matrix $failedJumps mit dem aktuellen $counter gespeichert.

class Knight {
     
    /**
     * Array - matrix, which contains the field values
     */
    protected $field;

    /**
     * Integer - current x coordinate of the jumper
     */
    protected $x;

    /**
     * Integer - current y coordinate of the jumper
     */
    protected $y;

    /**
     * Array of jumping directions
     */
    protected $direction;

    /**
     * Integer - number of current jump
     */
    protected $counter;

    /**
     * Array - Log over all made jumps
     */
    protected $jumps;

    /**
     * Array - matrix, saves each failed jump for each counter
     */
    protected $failedJumps;

    /**
     * Construct - sets the jumper to his starting point, initializes the field and the other attributes
     *
     * @param array $field
     * @param integer $x the starting position x
     * @param integer $y the starting position y
     */
    public function __construct($field, $x, $y) {
        $this->field = $field;
        $this->counter = 1;
        $this->jumps = array();
        $this->initFailedJumps();
        $this->setDirections();
        $this->setStartX($x);
        $this->setStartY($y);
        $this->field->setField($this->x, $this->y, $this->counter);
    }

    /**
     * Sets all possible jumping directions to the attribute direction
     *
     * @return void
     */
    public function setDirections() {
        $this->direction = array(
                array('x' => -1, 'y' => -2),
                array('x' => 1,  'y' => -2),
                array('x' => 2,  'y' => -1),
                array('x' => 2,  'y' => 1),
                array('x' => 1,  'y' => 2),
                array('x' => -1, 'y' => 2),
                array('x' => -2, 'y' => 1),
                array('x' => -2, 'y' => -1),
            );
    }

    /**
     * Sets the x-coordinate of the starting point
     *
     * @return void
     */
    public function setStartX($x) {
        if ($x < 0) {
            $this->x = 0;
        } elseif ($x >= $this->field->getWidth()) {
            $this->x = $this->field->getWidth() - 1;
        } else {
            $this->x = $x;
        }
    }

    /**
     * Sets the y-coordinate of the starting point
     *
     * @return void
     */
    public function setStartY($y) {
        if ($y < 0) {
            $this->y = 0;
        } elseif ($y >= $this->field->getHeight()) {
            $this->y = $this->field->getHeight() - 1;
        } else {
            $this->y = $y;
        }
    }

    /**
     * Returns the x position of the jumper
     *
     * @return integer $x
     */
    public function getX() {
        return $this->x;
    }

    /**
     * Returns the y position of the jumper
     *
     * @return integer $y
     */
    public function getY() {
        return $this->y;
    }

    /**
     * The wrapper function of canJumpTo with the current x and y coordinate
     *
     * @param integer $turn the number of jump possibility of the direction array
     *
     * @return boolean true if the target field is not out of bounds and not on a visited field,
     *                 else false
     */
    protected function canJump($turn) {
        return $this->canJumpTo($this->x, $this->y, $turn);
    }

    /**
     * Checks if the target field is free and not out of bounds
     *
     * @return integer $x coordinate
     * @return integer $y coordinate
     * @param integer $turn the number of jump possibility of the direction array
     *
     * @return boolean true if the target field is not out of bounds and not on a visited field,
     *                 else false
     */
    protected function canJumpTo($x, $y, $turn) {
        if ($x + $this->direction[$turn]['x'] < 0 ||
            $y + $this->direction[$turn]['y'] < 0 ||
            $x + $this->direction[$turn]['x'] >= $this->field->getWidth() ||
            $y + $this->direction[$turn]['y'] >= $this->field->getHeight() ||
            $this->field->isVisited($x + $this->direction[$turn]['x'], $y + $this->direction[$turn]['y'])) {
            return FALSE;
        }

        return TRUE;
    }

    /**
     * Sets the jumper to the target field by the given $turn if possible.
     *
     * @param integer $turn the number of jump possibility of the direction array
     *
     * @return boolean true if the jump with this $turn was successful, else false
     */
    public function jump($turn) {
        if ($this->canJump($turn)) {
            $this->x += $this->direction[$turn]['x'];
            $this->y += $this->direction[$turn]['y'];
            $this->counter++;
            $this->field->setField($this->x, $this->y, $this->counter);
            array_push($this->jumps, $turn);
            return TRUE;
        }
        return FALSE;
    }

    /**
     * Undo a jump. Sets the jumper to his last position, decrements the counter
     * and saves the failed jump in the $failedJump array
     *
     * @return integer 0, if there is no solution
     *                -1, if no more jumps can be undone
     *                 1, if jump could be undone successfully
     */
    public function undoJump() {
        if ($this->checkDeadEnd() && $this->counter === 1) {
            return 0;
        }

        if (empty($this->jumps)) {
            return -1;
        }

        $lastTurn = array_pop($this->jumps);
        $this->field->setField($this->x, $this->y, 0);
        $this->x -= $this->direction[$lastTurn]['x'];
        $this->y -= $this->direction[$lastTurn]['y'];
        $this->counter--;
        $this->failedJumps[$this->counter - 1][] = $lastTurn;
        $this->failedJumps[$this->counter] = array();
        return 1;
    }
    
    /**
     * Returns the number of visited fields (equal to the current counter)
     *
     * @return integer $counter
     */
    public function numberOfVisitedFields() {
        return $this->counter;
    }

    /**
     * Add a failed jump to the array with the current counter
     *
     * @param integer $turn the number of jump possibility of the direction array
     *
     * @return void
     */
    public function saveFailedJump($turn) {
        $this->failedJumps[$this->counter - 1][] = $turn;
    }

    /**
     * Returns the last failed turn of the current counter
     *
     * @return integer $turn
     */
    public function getLastFailedJump() {
        $last = count($this->failedJumps[$this->counter - 1]) - 1;

        if ($last === -1) {
            return -1;
        }

        return $this->failedJumps[$this->counter - 1][$last];
    }

    /**
     * Sets the $failedJumps with index greater than the current counter
     * to an empty array. All attempts of undo jumps will be deleted.
     *
     * @return void
     */
    protected function initFailedJumps() {
        $this->failedJumps = array();
        for ($i = 0; $i < $this->field->getSize(); $i++) {
            $this->failedJumps[$i] = array();
        }
    }

    /**
     * Check if jumper has tried all 8 possibilities to jump
     *
     * @return boolean true if all 8 possibilities has been tried and all failed, else false
     */
    public function checkDeadEnd() {
        return count($this->failedJumps[$this->counter - 1]) === 8;
    }

    /**
     * Warnsdorff's heuristic 
     *
     * @return array $turns the next possible turns sorted by Warnsdorff's rule
     */
    protected function warnsdorffRule() {
        $turns = array();
        $sort = array();
        for ($turn = 0; $turn < 8; $turn++) {
            if ($this->canJump($turn)) {
                $x = $this->x + $this->direction[$turn]['x'];
                $y = $this->y + $this->direction[$turn]['y'];
                $possibilities = 0;
                for ($turn2 = 0; $turn2 < 8; $turn2++) {
                    if ($this->canJumpTo($x, $y, $turn2)) {
                        $possibilities++;
                    }
                }
                $turns[] = array('turn' => $turn, 'count' => $possibilities);
                $sort[] = $possibilities;
            } else {
                $turns[] = array('turn' => $turn, 'count' => 9);
                $sort[] = 9;
            }
        }

        array_multisort($sort, SORT_ASC, $turns);

        return $turns;
    }

    /**
     * Returns the next turn by Warnsdorff's heuristic 
     *
     * @return integer $turns the next turn calculated by the Warnsdorff's heuristic
     */
    public function getTurn($turn) {
        $turns = $this->warnsdorffRule();
        return $turns[$turn]['turn'];
    }
}

Die Ausführung - backtracking.php

Als Erstes werden die beiden Implementierungen der Klassen eingebunden und das Feld und der Springer mit den Formulareingaben initialisiert. Die maximale Anzahl der Iterationsschritte wird abhängig von der Aktivierung der Warnsdorff-Heuristik gesetzt. Da die Berechnung mit aktivierter Heuristik laufzeitintensiver ist, und somit ein Server-Timeout bei der Berechnung droht, ist dieser Wert auf 100.000 festgelegt. In der Schleife wird nun der Backtracking-Algorithus ggf. mit Heuristik ausgeführt. Am Ende des Skripts wird entweder das Feld oder ein Status-Flag (siehe Beschreibung der Methode undoJump() ) ausgegeben.

require_once('class.field.php');
require_once('class.knight.php');

// Init field and jumper
$field = new Field(intval($_POST['sx']), intval($_POST['sy']));
$knight = new Knight($field, intval($_POST['x']), intval($_POST['y']));

$heuristic = intval($_POST['heuristic']) ? 1 : 0;

if ($heuristic) {
    $maxIterations = 100000;
} else {
    $maxIterations = 1000000;
}

$turn = 0;
$i = 0;
$solved = 1;
// while not all fields are visited
while ($knight->numberOfVisitedFields() < $field->getSize()) {
    // try to jump
    if ($heuristic) {
        // get next jump by Warnsdorff-Rule
        $nextTurn = $knight->getTurn($turn);
    } else {
        // get next jump without any heuristic
        $nextTurn = $turn;
    }
    if (!$knight->jump($nextTurn)) {
        // jump fails, save it and try next one
        $knight->saveFailedJump($turn);
        $turn = ($turn + 1) % 8;
    }
    // while jumper is in a dead end
    while ($knight->checkDeadEnd()) {
        // undo last jump
        $state = $knight->undoJump();
        // if all possibilities are checked, break all loops and return with the no solution flag
        if ($state === 0) {
            $solved = 0;
            break(2);
        // no more jumps can be undone, try another jump from starting position
        } elseif ($state === -1) {
            break;
        }
    }
    // try next jump of the last jump, if not all possibilities were tried 
    $turn = ($knight->getLastFailedJump() + 1) % 8;
    // break after $maxIterations are reached
    if ($i > $maxIterations) {
        $solved = -1;
        break;
    }
    $i++;
}

// print the field as JSON array or a state flag
if ($solved === 1) {
    echo $field->printFieldJSON();
} else {
    echo $solved;
}

Die Animation mit jQuery

Die onchange-Handler garantieren im Formular konsistente Eingabebereiche. Per AJAX wird das Skript backtracking.php mit den Formulareingaben aufgerufen. Falls eine Lösung gefunden wurde, wird der zurückgegebene JSON-String in eine HTML-Tabelle umgewandelt, auf der nun die Animation ausgeführt wird. Bei keiner gufundenen Lösung wird das Status-Flag in einen aussagekräftigen Text verwandelt und ausgegeben.

var INT = null;

$('body').on('change', '#size-x', function () {
    setMaxStart($(this), $('#coord-x'));
});
$('body').on('change', '#size-y', function () {
    setMaxStart($(this), $('#coord-y'));
});

$('body').on('click', '#solve', function () {
    var result = $('#springer-problem');
    result.empty();
    clearInterval(INT);

    var width = $('#size-x').val() * 41 + 1;
    var height = $('#size-y').val() * 41 + 1;

    result.css({
        width: width,
        height: height
    });
    var loader = $('<div id="springer-problem-loading"></div>');
    loader.css({
        position: 'absolute',
        top: 0,
        left: 0,
        width: width - 2,
        height: height - 2,
        background: '#fff',
        zIndex: 10,
        border: '1px solid #111'
    });
    loader.prepend($('<img src="/'+$('#config-theme-path').val()+'/images/lehre/springer-problem-loader.gif" />'));
    loader.find('img').css({
        position: 'absolute',
        top: '50%',
        left: '50%',
        width: 66,
        height: 66,
        marginTop: -33,
        marginLeft: -33
    });
    result.prepend(loader);

    $.ajax({
        url: '/'+$('#config-theme-path').val()+'/sources/lehre/springer-problem/backtracking.php',
        type: 'post',
        data: {
            sx: $('#size-x').val(),
            sy: $('#size-y').val(),
            x: $('#coord-x').val(),
            y: $('#coord-y').val(),
            heuristic: $('#heuristic').prop('checked') ? 1 : 0
        },
        async: true,
        cache: true
    }).success(function (html) {

        if ($('#heuristic').prop('checked')) {
            maxIterations = '100.000';
        } else {
            maxIterations = '1.000.000';
        }

        result.empty();
        if (html == 0) {
            result.html('Keine Lösung gefunden.');
            return;
        } else if (html == -1) {
            result.html('Es kann eine Lösung geben, aber nach '+maxIterations+' Schritten konnte kein Ergebnis ermittelt werden.');
            return;
        }
        var sizeX = $('#size-x').val();
        var sizeY = $('#size-y').val();

        result.append(buildTable(sizeX, sizeY));
        var turns = JSON.parse(html);
        var number = 1;

        INT = setInterval(function () {
            output(turns, sizeX, sizeY, number);
            number++;
            if (number === sizeX * sizeY + 1) {
                clearInterval(INT);
            }
        }, $('#speed').val() * 1.5);
    });
});

function output(turns, sizeX, sizeY, number) {
    for (var i = 0; i < sizeY; i++) {
        for (var j = 0; j < sizeX; j++) {
            if (turns[i][j] == number) {
                $('#springer-problem > table td').eq(j + sizeX * i).stop().animate({ backgroundColor: '#000' }, $('#speed').val(), function () {
                    $(this).html(number);
                    $(this).css({ backgroundColor: '#b00', color: '#fff' });
                });
            }
        }
    }
}

function buildTable(x, y) {
    var html = '';
    var row = '<tr>';
    for (var i = 0; i < x; i++) {
        row += '<td></td>';
    }
    row += '</tr>';

    for (var i = 0; i < y; i++) {
        html += row;
    }

    return $('<table>' + html + '</table>');
}

function setMaxStart(sizeField, coord) {
    var max = sizeField.val() - 1;
    coord.attr('max', max);
    if (coord.val() > max) {
        coord.val(max);
    }
}

Lehre

Patrick Saar