Час пик - решение игры

Ответ 1

Для классического Часа пик эта проблема очень удобна с простым поиском ширины. Заявленная самая сложная изначально первоначальная конфигурация требует 93 ходов для решения, и всего лишь 24132 достижимых конфигураций. Даже наивный внедренный алгоритм поиска по ширине может исследовать все пространство поиска менее чем за 1 секунду даже на скромной машине.

Ссылки

• Википедия/Час пик (настольная игра)
• Начальные настройки часового часа - утверждают, что это "самые трудные" проблемы.
• Исправить источник на ideone.com - с выходом для "самого жесткого" ввода

Решатель Java

Здесь полный исходный код расширенного решателя поиска ширины, написанного в стиле C.

import java.util.*;

public class RushHour {
    // classic Rush Hour parameters
    static final int N = 6;
    static final int M = 6;
    static final int GOAL_R = 2;
    static final int GOAL_C = 5;

    // the transcription of the 93 moves, total 24132 configurations problem
    // from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
    static final String INITIAL =   "333BCC" +
                                    "B22BCC" +
                                    "B.XXCC" +
                                    "22B..." +
                                    ".BB.22" +
                                    ".B2222";

    static final String HORZS = "23X";  // horizontal-sliding cars
    static final String VERTS = "BC";   // vertical-sliding cars
    static final String LONGS = "3C";   // length 3 cars
    static final String SHORTS = "2BX"; // length 2 cars
    static final char GOAL_CAR = 'X';
    static final char EMPTY = '.';      // empty space, movable into
    static final char VOID = '@';       // represents everything out of bound

    // breaks a string into lines of length N using regex
    static String prettify(String state) {
        String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N));
        return state.replaceAll(EVERY_NTH, "\n");
    }

    // conventional row major 2D-1D index transformation
    static int rc2i(int r, int c) {
        return r * N + c;
    }

    // checks if an entity is of a given type
    static boolean isType(char entity, String type) {
        return type.indexOf(entity) != -1;
    }

    // finds the length of a car
    static int length(char car) {
        return
            isType(car, LONGS) ? 3 :
            isType(car, SHORTS) ? 2 :
            0/0; // a nasty shortcut for throwing IllegalArgumentException
    }

    // in given state, returns the entity at a given coordinate, possibly out of bound
    static char at(String state, int r, int c) {
        return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID;
    }
    static boolean inBound(int v, int max) {
        return (v >= 0) && (v < max);
    }

    // checks if a given state is a goal state
    static boolean isGoal(String state) {
        return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
    }

    // in a given state, starting from given coordinate, toward the given direction,
    // counts how many empty spaces there are (origin inclusive)
    static int countSpaces(String state, int r, int c, int dr, int dc) {
        int k = 0;
        while (at(state, r + k * dr, c + k * dc) == EMPTY) {
            k++;
        }
        return k;
    }

    // the predecessor map, maps currentState => previousState
    static Map<String,String> pred = new HashMap<String,String>();
    // the breadth first search queue
    static Queue<String> queue = new LinkedList<String>();
    // the breadth first search proposal method: if we haven't reached it yet,
    // (i.e. it has no predecessor), we map the given state and add to queue
    static void propose(String next, String prev) {
        if (!pred.containsKey(next)) {
            pred.put(next, prev);
            queue.add(next);
        }
    }

    // the predecessor tracing method, implemented using recursion for brevity;
    // guaranteed no infinite recursion, but may throw StackOverflowError on
    // really long shortest-path trace (which is infeasible in standard Rush Hour)
    static int trace(String current) {
        String prev = pred.get(current);
        int step = (prev == null) ? 0 : trace(prev) + 1;
        System.out.println(step);
        System.out.println(prettify(current));
        return step;
    }

    // in a given state, from a given origin coordinate, attempts to find a car of a given type
    // at a given distance in a given direction; if found, slide it in the opposite direction
    // one spot at a time, exactly n times, proposing those states to the breadth first search
    //
    // e.g.
    //    direction = -->
    //    __n__
    //   /     \
    //   ..o....c
    //      \___/
    //      distance
    //
    static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) {
        r += distance * dr;
        c += distance * dc;
        char car = at(current, r, c);
        if (!isType(car, type)) return;
        final int L = length(car);
        StringBuilder sb = new StringBuilder(current);
        for (int i = 0; i < n; i++) {
            r -= dr;
            c -= dc;
            sb.setCharAt(rc2i(r, c), car);
            sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY);
            propose(sb.toString(), current);
            current = sb.toString(); // comment to combo as one step
        }
    }

    // explores a given state; searches for next level states in the breadth first search
    //
    // Let (r,c) be the intersection point of this cross:
    //
    //     @       nU = 3     '@' is not a car, 'B' and 'X' are of the wrong type;
    //     .       nD = 1     only '2' can slide to the right up to 5 spaces
    //   2.....B   nL = 2
    //     X       nR = 4
    //
    // The n? counts how many spaces are there in a given direction, origin inclusive.
    // Cars matching the type will then slide on these "alleys".
    //
    static void explore(String current) {
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (at(current, r, c) != EMPTY) continue;
                int nU = countSpaces(current, r, c, -1, 0);
                int nD = countSpaces(current, r, c, +1, 0);
                int nL = countSpaces(current, r, c, 0, -1);
                int nR = countSpaces(current, r, c, 0, +1);
                slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
                slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1);
                slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
                slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1);
            }
        }
    }
    public static void main(String[] args) {
        // typical queue-based breadth first search implementation
        propose(INITIAL, null);
        boolean solved = false;
        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (isGoal(current) && !solved) {
                solved = true;
                trace(current);
                //break; // comment to continue exploring entire space
            }
            explore(current);
        }
        System.out.println(pred.size() + " explored");
    }
}

В исходном коде есть две заметные строки:

• break;, когда найдено решение
  • Теперь это комментарий, так что поиск по ширине сначала исследует все пространство поиска, чтобы подтвердить цифры, указанные на связанном веб-сайте выше.
• current = sb.toString(); в slide
  • По сути, это означает, что каждое движение любого автомобиля является одним движением. Если автомобиль перемещается на 3 пробела влево, то 3 хода. Чтобы объединить это как один шаг (поскольку он включает в себя тот же автомобиль, движущийся в одном направлении), просто прокомментируйте эту строку. Связанный веб-сайт не признает комбо, поэтому теперь эта строка не соответствует минимальному количеству приведенных ходов. При комбинированном подсчете проблема 93-ходов требует только 49 комбинированных ходов. То есть, если в салоне есть парковочный ассистент, который перемещает эти автомобили, ему нужно будет всего лишь входить и выходить из машины 49 раз.

Обзор алгоритма

Алгоритм представляет собой, по существу, широкий поиск по ширине, реализованный с очередью, как это обычно бывает. Карта предшественника поддерживается так, что любое состояние можно проследить до исходного состояния. Ключ никогда не будет переназначен, и поскольку записи вставляются в порядок поиска по ширине, гарантируется самый короткий путь.

Состояние представлено как NxM -length String. Каждый char представляет собой объект на плате, хранящийся в строчном порядке.

Соседние состояния обнаруживаются путем сканирования всех 4 направлений из пустого пространства, ища подходящий тип автомобиля, сдвигающий его по мере того, как вмещается комната.

Здесь много избыточной работы (например, длинные "переулки" сканируются несколько раз), но, как упоминалось ранее, хотя обобщенная версия PSPACE-complete, классический вариант "Час пик" очень удобен с помощью грубой силы.

Ссылки на Википедию

• Быстрый поиск по ширине
• Строчный порядок

Ответ 2

Вот мой ответ. Он решает головоломку грандиозного мастера всего за 6 секунд.

Он использует первый поиск ширины (BFS). Хитрость заключается в том, чтобы искать макет платы, который вы видели ранее в предыдущих поисках, и прервать эту последовательность. Из-за BFS, если вы видели этот макет, прежде чем у вас уже есть более короткий путь, пусть этот сквот продолжает пытаться его решить, а не более длинный.

#!perl

# Program by Rodos rodos at haywood dot org

use Storable qw(dclone);
use Data::Dumper;

print "Lets play Rush Hour! \n";


# Lets define our current game state as a grid where each car is a different letter.
# Our special car is a marked with the specific letter T
# The boarder is a * and the gloal point on the edge is an @.
# The grid must be the same witdh and height 
# You can use a . to mark an empty space

# Grand Master
@startingGrid = (
 ['*','*','*','*','*','*','*','*'],
 ['*','.','.','A','O','O','O','*'],
 ['*','.','.','A','.','B','.','*'],
 ['*','.','T','T','C','B','.','@'],
 ['*','D','D','E','C','.','P','*'],
 ['*','.','F','E','G','G','P','*'],
 ['*','.','F','Q','Q','Q','P','*'],
 ['*','*','*','*','*','*','*','*']
);

# Now lets print out our grid board so we can see what it looks like.
# We will go through each row and then each column.
# As we do this we will record the list of cars (letters) we see into a hash

print "Here is your board.\n";

&printGrid(\@startingGrid);

# Lets find the cars on the board and the direction they are sitting

for $row (0 .. $#startingGrid) {
    for $col (0 .. $#{$startingGrid[$row]} ) {

        # Make spot the value of the bit on the grid we are looking at
        $spot = $startingGrid[$row][$col];

        # Lets record any cars we see into a "hash" of valid cars.
        # If the splot is a non-character we will ignore it cars are only characters
        unless ($spot =~ /\W/) {

            # We will record the direction of the car as the value of the hash key.
            # If the location above or below our spot is the same then the car must be vertical.
            # If its not vertical we mark as it as horizonal as it can't be anything else!

            if ($startingGrid[$row-1][$col] eq $spot || $startingGrid[$row+1] eq $spot) {
                $cars{$spot} = '|';
            } else {
                $cars{$spot} = '-';
            }
        }
    }
}

# Okay we should have printed our grid and worked out the unique cars
# Lets print out our list of cars in order

print "\nI have determined that you have used the following cars on your grid board.\n";
foreach $car (sort keys %cars) {
    print " $car$cars{$car}";
}
print "\n\n";

end;

&tryMoves();

end;

# Here are our subroutines for things that we want to do over and over again or things we might do once but for 
# clatiry we want to keep the main line of logic clear

sub tryMoves {

    # Okay, this is the hard work. Take the grid we have been given. For each car see what moves are possible
    # and try each in turn on a new grid. We will do a shallow breadth first search (BFS) rather than depth first. 
    # The BFS is achieved by throwing new sequences onto the end of a stack. You then keep pulling sequnces
    # from the front of the stack. Each time you get a new item of the stack you have to rebuild the grid to what
    # it looks like at that point based on the previous moves, this takes more CPU but does not consume as much
    # memory as saving all of the grid representations.

    my (@moveQueue);
    my (@thisMove);
    push @moveQueue, \@thisMove;

    # Whlst there are moves on the queue process them                
    while ($sequence = shift @moveQueue) { 

        # We have to make a current view of the grid based on the moves that got us here

        $currentGrid = dclone(\@startingGrid);
        foreach $step (@{ $sequence }) {
            $step =~ /(\w)-(\w)(\d)/;
            $car = $1; $dir = $2; $repeat = $3;

            foreach (1 .. $repeat) {
                &moveCarRight($car, $currentGrid) if $dir eq 'R';
                &moveCarLeft($car,  $currentGrid) if $dir eq 'L';
                &moveCarUp($car,    $currentGrid) if $dir eq 'U';
                &moveCarDown($car,  $currentGrid) if $dir eq 'D';
            }
        }

        # Lets see what are the moves that we can do from here.

        my (@moves);

        foreach $car (sort keys %cars) {
            if ($cars{$car} eq "-") {
                $l = &canGoLeft($car,$currentGrid);
                push @moves, "$car-L$l" if ($l);
                $l = &canGoRight($car,$currentGrid);
                push @moves, "$car-R$l" if ($l);
            } else {
                $l = &canGoUp($car,$currentGrid);
                push @moves, "$car-U$l" if ($l);
                $l = &canGoDown($car,$currentGrid);
                push @moves, "$car-D$l" if ($l);
            }
        }

        # Try each of the moves, if it solves the puzzle we are done. Otherwise take the new 
        # list of moves and throw it on the stack

        foreach $step (@moves) {

            $step =~ /(\w)-(\w)(\d)/;
            $car = $1; $dir = $2; $repeat = $3;

            my $newGrid = dclone($currentGrid);

            foreach (1 .. $repeat) {
                &moveCarRight($car, $newGrid) if $dir eq 'R';
                &moveCarLeft($car, $newGrid) if $dir eq 'L';
                &moveCarUp($car, $newGrid) if $dir eq 'U';
                &moveCarDown($car, $newGrid) if $dir eq 'D';
            }

            if (&isItSolved($newGrid)) {
                print sprintf("Solution in %d moves :\n", (scalar @{ $sequence }) + 1);
                print join ",", @{ $sequence };
                print ",$car-$dir$repeat\n";
                return;
            } else {

                # That did not create a solution, before we push this for further sequencing we want to see if this
                # pattern has been encountered before. If it has there is no point trying more variations as we already
                # have a sequence that gets here and it might have been shorter, thanks to our BFS

                if (!&seen($newGrid)) {
                    # Um, looks like it was not solved, lets throw this grid on the queue for another attempt
                    my (@thisSteps) = @{ $sequence };
                    push @thisSteps, "$car-$dir$repeat";
                    push @moveQueue, \@thisSteps;
                }
            }            
        }
    }
}    

sub isItSolved {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # We know we have solve the grid lock when the T is next to the @, because that means the taxi is at the door
    if ($stringVersion =~ /\T\@/) {
        return 1;
    }
    return 0;
}    

sub seen {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # Have we seen this before?
    if ($seen{$stringVersion}) {
        return 1;
    }
    $seen{$stringVersion} = 1;
    return 0;
}    

sub canGoDown {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);


    for ($row = $#{$grid}; $row >= 0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[++$row][$col] eq ".") {
                    ++$l;
                }
                return $l;
            }
        }
    }
    return 0;
}

sub canGoUp {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[--$row][$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoRight {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][++$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoLeft {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][--$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub moveCarLeft {

    # Move the named car to the left of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving left requires sweeping left to right.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move left
    die "Opps, tried to move a vertical car $car left" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car left into an occupied spot\n" if $grid->[$row][$col-1] ne ".";
                $grid->[$row][$col-1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarRight {

    # Move the named car to the right of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping right to left (backwards).

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move right
    die "Opps, tried to move a vertical car $car right" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car right into an occupied spot\n" if $grid->[$row][$col+1] ne ".";
                $grid->[$row][$col+1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}


sub moveCarUp {

    # Move the named car up in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping top down.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car up" if $cars{$car} eq "-";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car up into an occupied spot\n" if $grid->[$row-1][$col] ne ".";
                $grid->[$row-1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarDown {

    # Move the named car down in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping upwards from the bottom.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car down" if $cars{$car} eq "-";

    my ($row, $col);    

    for ($row = $#{$grid}; $row >=0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car down into an occupied spot\n" if $grid->[$row+1][$col] ne ".";
                $grid->[$row+1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub printGrid {

    # Print out a representation of a grid

    my ($grid) = shift; # This is a reference to an array of arrays whch is passed as the argument

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
                print $grid->[$row][$col], " ";
        }
        print "\n";
    }
}

Ответ 3

На самом деле есть статья из MIT, в которой конкретно упоминается "Час пик" (я использовал поисковый термин "головоломки со скользящими блоками")

Ответ 4

Вы должны реорганизовать (ваше решение "обратного отслеживания" ). Вероятно, это единственный способ решить такие головоломки: вопрос в том, как это сделать быстро.

Как вы отметили, пространство поиска будет большим - но не слишком большим, если у вас есть плата разумного размера. Например, вы нарисовали сетку 6x6 с 12 автомобилями на ней. Предполагая, что каждый автомобиль размером 2, который дает 5 пробелов/на, поэтому не более 5 ^ 12 = 244 140 625 потенциальных позиций. Это даже подходит для 32-разрядного целого числа. Таким образом, одна из возможностей - выделить огромный массив, один слот на потенциальную позицию и использовать memoization, чтобы убедиться, что вы не повторяете позицию.

Следующее, что нужно отметить, это то, что большинство из этих "потенциальных" позиций фактически не возможны (они будут перекрывать перекрытие автомобилей). Вместо этого используйте хеш-таблицу для отслеживания каждой позиции, которую вы посетили. Это будет иметь небольшую накладную память для каждой записи, но она, вероятно, будет более экономичной по площади, чем решение "большого массива". Тем не менее, это займет немного больше времени для каждого доступа к записи.

Как пишет газета MIT в @Daniel answer, проблема PSPACE-полная, то есть многие из трюков, используемых для снижения сложности проблем NP, возможно, t.

Тем не менее, любое из двух вышеперечисленных решений проблемы с повторной позицией должно работать на небольших сетках. Все это будет определяться тем, насколько велика проблема, и сколько памяти у вашего компьютера; но приведенный вами пример не должен быть вообще проблемой, даже для обычного настольного компьютера.

Ответ 5

Только что закончил писать свою реализацию и экспериментировал с ней. Я согласен с полигенными смазочными материалами, что пространство состояний действительно мало для классической игры (плата 6x6). Тем не менее, я попробовал умную реализацию поиска (A * search). Мне было любопытно относиться к сокращению исследуемого пространства состояний по сравнению с простой BFS.

Алгоритм A * можно рассматривать как обобщение поиска BFS. Решение о том, какой путь исследовать дальше, определяется оценкой, которая объединяет как длину пути (т.е. Количество ходов), так и нижнюю границу оставшегося количества ходов. То, как я решил вычислить последнее, - это получить расстояние от красной машины от выхода, а затем добавить 1 для каждого транспортного средства на пути, так как его нужно перемещать хотя бы один раз, чтобы очистить путь. Когда я заменяю вычисление нижней границы константой 0, я получаю регулярное поведение BFS.

После проверки четырех головоломок этот список, я обнаружил, что поиск A * исследуется в среднем 16% меньше чем обычный BFS.

Ответ 6

Я думаю, что рекурсия - плохая идея, если вы не отслеживаете, что вы уже посетили; вы можете бесконечно рекурсивно перемещаться по машине назад и вперед.

Возможно, это хороший старт. Представьте и сохраните каждое состояние платы как неориентированный граф. Затем для каждого возможного перемещения проверьте прошлые состояния, чтобы убедиться, что вы снова не попадаете в одно и то же состояние.

Теперь сделайте еще один неориентированный граф, где узлы представляют состояния и ребра, представляющие возможность перехода из одного состояния в другое посредством перемещения автомобиля. Исследуйте состояния, пока один из них не станет решением. Затем следуйте по краям до начала, чтобы узнать путь перемещения.

Ответ 7

Я написал судоку. Хотя детали совершенно разные, я думаю, что общая проблема схожа. Во-первых, попытка интеллектуальных эвристик в решении sudoku намного медленнее, чем решение грубой силы. Попытка каждого шага, с несколькими простыми эвристиками и без дубликатов - это путь. Немного сложнее проверить наличие дублированных состояний платы в час пик, но не так много.

Если вы посмотрите на доску в своем примере, есть только 4 действительных шага. В любой момент времени будет только несколько действительных ходов.

На каждом уровне рекурсии скопируйте состояние платы и попробуйте все допустимые перемещения на доске. Для каждого пустого квадрата переместите каждый автомобиль, который может на этот квадрат. Если новое состояние платы отсутствует в списке истории, повторите еще один уровень. По списку истории я имею в виду дать каждому уровню рекурсивного доступа к каждой доске, которая привела к этому состоянию, возможно, в связанном списке. Используйте хеши, чтобы быстро отказаться от неравных состояний.

Ключом к этому является простое состояние платы, которое можно легко скопировать и изменить. Вероятно, массив с одним int на квадрат, говорящий, что автомобиль покрывает этот квадрат, если таковой имеется. Тогда вам просто нужно пройти через квадраты и выяснить законные шаги. Законный ход означает пустые квадраты между тестовым квадратом и ориентированным на него автомобилем.

Как и в случае судоку, самым худшим вариантом будет генетический алгоритм.