Основы программирования на языке Visual Prolog

Поиск в пространстве состояний

Разбить на страницы
Показывать лекцию целиком

Настоящая глава посвящена решению задач при помощи графа пространства состояний. Пространство состояний описывается в виде множества состояний — вершин графа, множества переходов от состояния к состоянию — дуг графа, множества начальных состояний и множества конечных состояний. Решение задачи представляется в виде пути на графе пространства состояний, соединяющего начальное состояние с конечным.

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

К задачам применяются универсальные решатели. Состояния в разных задачах могут принадлежать различным доменам. Для запоминания наилучших среди найденных решений используется "изменяемая переменная" varM. Компилятор сам находит нужные типы.

13.1. Поиск в глубину в пространстве состояний

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

Задача о волке, козе и капусте заключается в следующем (Алкуин, XIII в.). Хозяин с волком, козой и грудой кочанов капусты должен перебраться через реку с левого берега на правый, имея в распоряжении маленькую лодку. В эту лодку, кроме хозяина, может поместиться только что-то одно — либо волк, либо коза, либо капуста. Нельзя оставлять без присмотра волка с козой, а козу с капустой. Как следует организовать переправу?

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

Для решения задач, как и ранее, создается консольный проект. В этом проекте создается модуль depth. В этот модуль следует поместить универсальный решатель, который использует поиск в глубину (листинги 13.1–13.2)В листинге 13.2 строку из версии Visual Prolog 7.5 V = varM::new([]), в версии Visual Prolog 7.4 нужно заменить строкой V = varM{tuple{State*, string*}*}::new([]),. 

domains
    move{State} = (State, string [out]) -> State nondeterm.

predicates
    depthSearch: (move{State}, State, State, positive [out])
        -> tuple{State*, string*} nondeterm.

    open core, list

class facts
    minweight : positive := 2^30.

class predicates
    depthSearch: (move{State}, State, State, tuple{State*, string*},
        positive, positive [out]) -> tuple{State*, string*} nondeterm.
clauses
    depthSearch(Move, Start, Goal, minweight) = 
            tuple(reverse(Path), reverse(Moves)):-
        minweight := 2^30,
        V = varM::new([]),
        foreach tuple(P, Ms) = 
            depthSearch(Move, Start, Goal, tuple([Start], []), 0, N) 
        do
            if N > minweight then succeed()
            elseif N < minweight then 
                V:value := [tuple(P, Ms)], minweight := N
            else V:value := [tuple(P, Ms) | V:value]
            end if
        end foreach,
        tuple(Path, Moves) = getMember_nd(V:value).

    depthSearch(_, Goal, Goal, Path, N, N) = Path:- !.
    depthSearch(Move, State, Goal, tuple(Path, Moves), C, N) =
        depthSearch(Move, NextState, Goal, tuple([NextState | Path],
            [Str | Moves]), C + 1, N):-
        C < minweight,
        NextState = Move(State, Str),
        not(isMember(NextState, Path)).

Далее, как обычно, создаются модули для примеров.

    open core, console, list, depth

class facts
    n : positive := 0.

domains
    wstate = tuple(loc BoatLoc, string* LeftSide, string* RightSide).
    loc = left; right.

class predicates
    wmove : move{wstate}.
    unsafestate : (string*) determ.
    wmoveFromTo: (positive, string*, string*, string* [out],
        string* [out], string* [out]) nondeterm.
    subset : (positive, A*, A* [out], A* [out]) nondeterm.
    f: (string*) -> string.
clauses
    wmoveFromTo(K, FromBef, ToBefore, FromAfter, ToAfter, Boat):-
        subset(K, FromBef, Boat, FromAfter),
        not(unsafestate(FromAfter)),
        ToAfter = sort(append(Boat, ToBefore)).

    wmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        wmoveFromTo(1, L, R, L1, R1, B),
        Str = string::format("farmer% moves from left to right", f(B)).
    wmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(0, 1),
        wmoveFromTo(K, R, L, R1, L1, B),
        Str = string::format("farmer% moves from right to left", f(B)).

    f([S]) = string::format(" with %", S):- !.
    f(_) = "".

    unsafestate(L):-
        L = [_, _ | _],
        isMember("goat", L).

    subset(0, L, [], L):- !.
    subset(K, [A | L], [A | L1], L2):-
        subset(K - 1, L, L1, L2).
    subset(K, [A | L], L1, [A | L2]):-
        subset(K, L, L1, L2).

    run():-
        L = sort(["wolf", "goat", "cabbage"]),
        Start = tuple(left, L, []),
        Goal = tuple(right, [], L),
        tuple([S0 | P], Moves) = depthSearch(wmove, Start, Goal, _W),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

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

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

Для того чтобы можно было использовать предикат subset в другом модуле, его объявление нужно перенести в декларацию класса ex1 (листинг 13.4).

predicates
    subset : (positive, A*, A* [out], A* [out]) nondeterm.

open core, console, list, string, depth, ex1

class facts
    n : positive := 0.
    capacity : positive := 2.      % вместимость лодки

domains
    knightOrSquire = k(integer); s(integer).
    kstate = tuple(loc, knightOrSquire*, knightOrSquire*).
    loc = left; right.

class predicates
    kmove : move{kstate}.
    moveFromTo : (positive, knightOrSquire*, knightOrSquire*,
        knightOrSquire* [out], knightOrSquire* [out], 
        knightOrSquire* [out]) nondeterm.
    unsafe: (knightOrSquire*) determ.
    f: (knightOrSquire*) -> string.
    g: (knightOrSquire) -> string.
clauses
    kmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        K = std::downTo(capacity, 2),
        moveFromTo(K, L, R, L1, R1, B),
        Str = format("% from left to right", f(B)).
    kmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(1, capacity),
        moveFromTo(K, R, L, R1, L1, B),
        Str = format("% from right to left", f(B)).

    moveFromTo(N, FromBef, ToBefore, FromAfter, ToAfter, Boat):-
        subset(N, FromBef, Boat, FromAfter),
        not(unsafe(Boat)),
        not(unsafe(FromAfter)),
        ToAfter = sort(append(Boat, ToBefore)),
        not(unsafe(ToAfter)).

    unsafe(L):-
        s(N) = getMember_nd(L),
        not(k(N) = getMember_nd(L)),
        k(_) = getMember_nd(L),
        !.

    f([S]) = format("% moves", g(S)):- !.
    f(L) = format("% move", 
        concatWithDelimiter(map(L, {(X) = g(X)}), ", ")).

    g(k(N)) = concat("knight ", toString(N)).
    g(s(N)) = concat("squire ", toString(N)).

    run():-
        L = sort([s(1), k(1), s(2), k(2), s(3), k(3)]),
        N = list::length(L) div 2,
        capacity := if N < 4 then 2 elseif N < 6 then 3 else 4 end if,
        Start = tuple(left, L, []),
        Goal = tuple(right, [], L),
        tuple([S0 | P], Moves) = depthSearch(kmove, Start, Goal, _W),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

Предикат downTo недетерминированно возвращает целые числа в указанных пределах в порядке убывания. Предикат list::length/1 возвращает количество элементов списка.

Для трех рыцарей задача имеет 486 оптимальных решений, которые содержат по 11 переходов. Для четырех рыцарей и трехместной лодки существует 15600 различных оптимальных решений, они содержат по 9 переходов.

Следующая программа посвящена решению задачи о миссионерах и каннибалах (XIX в.). Три миссионера и три каннибала хотят переправиться через реку с левого берега на правый. В их распоряжении имеется двухместная лодка. Если где-либо каннибалов будет больше, чем миссионеров, то они их съедят. Как они могут переправиться на другой берег?

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

open core, console, list, string, depth

class facts
    n : positive := 0.
    capacity : positive := 2.      % вместимость лодки

domains
    mstate = tuple(loc, positive*, positive*).
    loc = left; right.

class predicates
    mcmove : move{mstate}.
    mcmoveFromTo: (positive, positive, positive*, positive*,
        positive* [out], positive* [out]) determ.
    f: (positive, positive) -> string.
    g: (positive) -> string.
    b: (positive, positive) determ.
clauses
    mcmoveFromTo(Mb, Cb, [MFromBefore, CFromBefore], 
        [MToBefore, CToBefore], [MFromAfter, CFromAfter],
            [MToAfter, CToAfter]):-
        Cb <= CFromBefore,
        Mb <= MFromBefore,
        b(Mb, Cb),
        MFromAfter = MFromBefore - Mb,
        CFromAfter = CFromBefore - Cb,
        b(MFromAfter, CFromAfter),
        MToAfter = MToBefore + Mb,
        CToAfter = CToBefore + Cb,
        b(MToAfter, CToAfter).

    mcmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        K = std::downTo(capacity, 2),
        Cb = std::downTo(K, 0),
        Mb = K - Cb,
        mcmoveFromTo(Mb, Cb, L, R, L1, R1),
        Str = format("% % from left to right", f(Mb, Cb), g(Mb + Cb)).
    mcmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(1, capacity),
        Cb = std::fromTo(0, K),
        Mb = K - Cb,
        mcmoveFromTo(Mb, Cb, R, L, R1, L1),
        Str = format("% % from right to left", f(Mb, Cb), g(Mb + Cb)).

    f(0, 1) = "1 cannibal":- !.
    f(0, C) = format("% cannibals", C):- !.
    f(1, 0) = "1 missionary":- !.
    f(M, 0) = format("% missionaries", M):- !.
    f(M, C) = format("%, %", f(M, 0), f(0, C)).

    g(1) = "moves":- !.
    g(_) = "move".

    b(M, C):-
        if M > 0 then M >= C end if.

    run():-
        Start = tuple(left, [3, 3], [0, 0]),
        Goal = tuple(right, [0, 0], [3, 3]),
        capacity := 2,
        tuple([S0 | P], Moves) = depthSearch(mcmove, Start, Goal, _),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

Предикат zip/2 для двух списков одинаковой длины возвращает список, составленный из пар элементов из этих списков с одинаковыми индексами.

Имеется четыре оптимальных решения для задачи о трех миссионерах, 32 оптимальных решения для задачи о четырех миссионерах и 25 оптимальных решений для задачи с пятью миссионерами.

13.2. Поиск в ширину в пространстве состояний

В настоящем параграфе для решения задач применяется поиск в ширину в пространстве состояний. Для ограничения пространства поиска решения не продлеваются в ранее достигнутые состояния. Ведется поиск только одного оптимального решения.

Ниже приводится универсальный решатель задач методом поиска в ширину в пространстве состояний. Он реализуется в модуле breadth (листинги 13.7–13.8)В листинге 13.8 строку из версии Visual Prolog 7.5 V = varM::new([]), в версии Visual Prolog 7.4 нужно заменить строкой V = varM{State*}::new([]).. 

predicates
    breadthSearch: (depth::move{State}, State, State, positive [out])
        -> tuple{State*, string*} determ.

    open core, list, depth

domains
    t{State} = t(State*, string*, positive).

class predicates
    breadthPath: (move{State}, t{State}*, State*, State) 
        ->  t{State} nondeterm.
clauses
    breadthSearch(Move, Start, Goal, N) = 
            tuple(reverse(Path), reverse(Moves)):-
        t(Path, Moves, N) = 
            breadthPath(Move, [t([Start], [], 0)], [Start], Goal),
        !.

    breadthPath(_, [t([Goal | Path], Ms, N) | _], _, Goal) = 
        t([Goal | Path], Ms, N):- !.
    breadthPath(Move, [t([State|Path], Ms, N) | PL], StateList, Goal)=
        breadthPath(Move, append(PL, PL1), 
            append(V:value, StateList), Goal):-
       V = varM::new([]),
       PL1 = [t([NextState, State | Path], [Str | Ms], N + 1) ||
            NextState = Move(State, Str),
            not(isMember(NextState, StateList)),
            V:value := [NextState | V:value]].

Применим решатель к задаче о переливаниях. Имеется несколько сосудов, вмещающих целое количество литров воды, и источник воды (река). Требуется отмерить в первом сосуде заданное целое количество литров воды. Можно наливать воду в сосуды из источника, переливать воду из одного сосуда в другой, так чтобы либо первый сосуд становился пустым, либо второй сосуд полным, а также опорожнять сосуды. Обычно считается, что сосуды упорядочены по убыванию вместимости. В этом случае в первом сосуде можно отмерить любое целое количество литров, которое делится на наибольший общий делитель объемов всех сосудов. Потребуем, чтобы нужное количество литров отмерялось в первом, наибольшем сосуде, а остальные сосуды оказывались бы пустыми. Если сосудов два, то можно показать, что задача в этом случае имеет единственное оптимальное решение. Если сосудов более двух, то оптимальных решений более одного. Пространство состояний в этом случае велико, поэтому мы будем искать только одно оптимальное решение с помощью поиска в ширину.

open core, console, list, string, breadth

class facts
    volums: (positive*) determ.
clauses
     volums([17, 11, 8]).   % volums([27, 17, 11, 8, 3]).

class predicates
    jmove : depth::move{positive*}.
clauses
    jmove(L, Str) = L1:-
        memberIndex_nd(A, I, L),
        A > 0,
        setNth(I, L, 0, L1),
        Str = format("Вылить % л из %-го сосуда", A, I + 1).
    jmove(L, Str) = L2:-
        volums(VL),
        memberIndex_nd(A, I, L),
        A > 0,
        memberIndex_nd(B, J, L), J <> I,
        V = nth(J, VL),
        B < V,
        Vol = math::min(V - B, A),
        setNth(I, L, A - Vol, L1),
        setNth(J, L1, B + Vol, L2),
        Str = format("Перелить % л из %-го сосуда в %-й", 
            Vol, I + 1, J + 1).
    jmove(L, Str) = L1:-
        volums(VL),
        memberIndex_nd(A, I, L),
        V = nth(I, VL),
        A < V,
        setNth(I, L, V, L1),
        Str = format("Налить % л в %-й сосуд", V - A, I + 1).

    run():-
         Start = [0, 0, 0],
         Goal = [4, 0, 0],
         tuple([S0 | P], Moves) = breadthSearch(jmove, Start, Goal, _),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

Предикат memberIndex_nd/3 недетерминированно возвращает из списка элементы вместе с их индексами. Предикат setNth/4 заменяет элемент списка, стоящий в заданной позиции, заданным элементом. Предикат nth/2 возвращает элемент списка по его индексу. Предикат min/2 возвращает минимум двух чисел.

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

Следует перенести указанные ниже объявления в декларацию класса ex2 из его имплементации (листинг 13.10).

domains
    knightOrSquire = k(integer); s(integer).

predicates
    moveFromTo: (positive, knightOrSquire*, knightOrSquire*,
        knightOrSquire* [out],  knightOrSquire* [out], 
        knightOrSquire* [out]) nondeterm.
    f: (knightOrSquire*) -> string.

open core, console, list, string, breadth, ex2

domains
    kistate = tuple(loc, knightOrSquire*, knightOrSquire*,
        knightOrSquire*).
    loc = left; right; island.

class predicates
    kimove : depth::move{kistate}.
clauses
    kimove(tuple(left, L, Isl, R), Str) = tuple(right, L1, Isl, R1):-
        moveFromTo(2, L, R, L1, R1, B),
        Str = format("% from left to right", f(B)).
    kimove(tuple(island, L, Isl, R), Str) = tuple(right, L, Isl1, R1):-
        moveFromTo(2, Isl, R, Isl1, R1, B),
        Str = format("% from island to right", f(B)).
    kimove(tuple(left, L, Isl, R), Str) = tuple(island, L1, Isl1, R):-
        moveFromTo(2, L, Isl, L1, Isl1, B),
        Str = format("% from left to island", f(B)).
    kimove(tuple(right, L, Isl, R), Str) = tuple(left, L1, Isl, R1):-
        moveFromTo(1, R, L, R1, L1, B),
        Str = format("% from right to left", f(B)).
    kimove(tuple(island, L, Isl, R), Str) = tuple(left, L1, Isl1, R):-
        moveFromTo(1, Isl, L, Isl1, L1, B),
        Str = format("% from island to left", f(B)).
    kimove(tuple(right, L, Isl, R), Str) = tuple(island, L, Isl1, R1):-
        moveFromTo(1, R, Isl, R1, Isl1, B),
        Str = format("% from right to island", f(B)).

    run():-
        L = sort([s(1), k(1), s(2), k(2), s(3), k(3), s(4), k(4)]),
        Start = tuple(left, L, [], []),
        Goal = tuple(right, [], [], L),
        tuple([S0 | P], Moves) = breadthSearch(kimove, Start, Goal,_),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

Наконец, используем поиск в ширину для решения задачи о переправе мисиионеров и каннибалов через реку с островом (конец XIX в.). Если на реке имеется остров, на который можно высаживаться, то переправу можно организовать также для любого количества миссионеров и такого же количества каннибалов и двухместной лодки.

Указанные ниже объявления следует перенести в декларацию класса ex3 из имплементации этого класса (см. листинг 13.12).

predicates
    mcmoveFromTo: (positive, positive, positive*, positive*,
        positive* [out], positive* [out]) determ.
    f: (positive, positive) -> string.

open core, console, list, string, breadth, ex3

domains
    mistate = tuple(loc, positive*, positive*, positive*).
    loc = left; right; island.

class predicates
    mimove : depth::move{mistate}.
clauses
    mimove(tuple(left, L, Isl, R), Str) = tuple(right, L1, Isl, R1):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, L, R, L1, R1),
        Str = format("% move from left to right", f(Mb, Cb)).
    mimove(tuple(left, L, Isl, R), Str) = tuple(island, L1, Isl1, R):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, L, Isl, L1, Isl1),
        Str = format("% move from left to island", f(Mb, Cb)).
    mimove(tuple(island, L, Isl, R), Str) = tuple(right, L, Isl1, R1):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, Isl, R, Isl1, R1),
        Str = format("% move from island to right", f(Mb, Cb)).
    mimove(tuple(right, L, Isl, R), Str) = tuple(left, L1, Isl, R1):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, R, L, R1, L1),
        Str = format("% moves from right to left", f(Mb, Cb)).
    mimove(tuple(right, L, Isl, R), Str) = tuple(island, L, Isl1, R1):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, R, Isl, R1, Isl1),
        Str = format("% moves from right to island", f(Mb, Cb)).
    mimove(tuple(island, L, Isl, R), Str) = tuple(left, L1, Isl1, R):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, Isl, L, Isl1, L1),
        Str = format("% moves from island to left", f(Mb, Cb)).

    run():-
        N = 4,
        Start = tuple(left, [N, N], [0, 0], [0, 0]),
        Goal = tuple(right, [0, 0], [0, 0], [N, N]),
        tuple([S0| P], Moves) = breadthSearch(mimove, Start, Goal,_),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

Упражнения

  • Задача о шатком мосте. Бабушка, дедушка, мать, отец, дочь и сын должны перейти ночью через шаткий мост. У них имеется лишь один фонарь, находиться на мосту без фонаря нельзя. Идти по мосту одновременно могут не более двух человек. Найдите способ семье переправиться через мост за минимальное время, если бабушка может перейти мост за шесть минут, дедушка за пять, мать за четыре, отец за три, дочь за две и сын за одну минуту.
  • Переправа семьи через реку (Алкуин, VIII в.). Мать и отец, каждый весом с воз, и два их сына, которые вместе весят воз, хотят переправиться через реку. В их распоряжении имеется лодка, которая выдерживает вес, равный одному возу. Как им переправиться через реку?
  • Переправа группы людей через реку. Семья — родители, два сына и две дочери — и полицейский с заключенным должны переправиться через реку с помощью плота, который вмещает не более двух человек. Управлять плотом может только взрослый. Нельзя оставлять мать наедине с сыновьями, отца наедине с дочерьми и заключенного в присутствии других людей без полицейского.
  • Задача о бочке. Бочка стоит у реки. С помощью двух кувшинов, вмещающих 8 и 5 литров воды, требуется получить в бочке 41 литр воды, не переливая воду из кувшина в кувшин.
  • Задача о песочных часах. Имеются песочные часы на 8 и 3 минуты. Требуется отмерить 4 минуты.
  • Задача о ферзях. Требуется расставить n ферзей на шахматной доске n x n так, чтобы они не били друг друга.
  • Задача о раскраске. Требуется найти такую раскраску плоской карты, используя не более четырех цветов, чтобы никакие две соседние страны не были раскрашены в один и тот же цвет.
  • Игра в 8. Требуется расставить по порядку восемь перепутанных фишек, на которых написаны номера от единицы до восьми, на поле 3 x 3. Одна из клеток поля пустая, в остальных находится по фишке. За один ход фишку можно передвинуть на соседнее пустое место.
    •
    Страницы:

    Настоящая глава посвящена решению задач при помощи графа пространства состояний. Пространство состояний описывается в виде множества состояний — вершин графа, множества переходов от состояния к состоянию — дуг графа, множества начальных состояний и множества конечных состояний. Решение задачи представляется в виде пути на графе пространства состояний, соединяющего начальное состояние с конечным.

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

    К задачам применяются универсальные решатели. Состояния в разных задачах могут принадлежать различным доменам. Для запоминания наилучших среди найденных решений используется "изменяемая переменная" varM. Компилятор сам находит нужные типы.

    13.1. Поиск в глубину в пространстве состояний

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

    Задача о волке, козе и капусте заключается в следующем (Алкуин, XIII в.). Хозяин с волком, козой и грудой кочанов капусты должен перебраться через реку с левого берега на правый, имея в распоряжении маленькую лодку. В эту лодку, кроме хозяина, может поместиться только что-то одно — либо волк, либо коза, либо капуста. Нельзя оставлять без присмотра волка с козой, а козу с капустой. Как следует организовать переправу?

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

    Для решения задач, как и ранее, создается консольный проект. В этом проекте создается модуль depth. В этот модуль следует поместить универсальный решатель, который использует поиск в глубину (листинги 13.1–13.2)В листинге 13.2 строку из версии Visual Prolog 7.5 V = varM::new([]), в версии Visual Prolog 7.4 нужно заменить строкой V = varM{tuple{State*, string*}*}::new([]),. 

    domains
    move{State} = (State, string [out]) -> State nondeterm.

predicates
    depthSearch: (move{State}, State, State, positive [out])
        -> tuple{State*, string*} nondeterm.

        open core, list

class facts
    minweight : positive := 2^30.

class predicates
    depthSearch: (move{State}, State, State, tuple{State*, string*},
        positive, positive [out]) -> tuple{State*, string*} nondeterm.
clauses
    depthSearch(Move, Start, Goal, minweight) = 
            tuple(reverse(Path), reverse(Moves)):-
        minweight := 2^30,
        V = varM::new([]),
        foreach tuple(P, Ms) = 
            depthSearch(Move, Start, Goal, tuple([Start], []), 0, N) 
        do
            if N > minweight then succeed()
            elseif N < minweight then 
                V:value := [tuple(P, Ms)], minweight := N
            else V:value := [tuple(P, Ms) | V:value]
            end if
        end foreach,
        tuple(Path, Moves) = getMember_nd(V:value).

    depthSearch(_, Goal, Goal, Path, N, N) = Path:- !.
    depthSearch(Move, State, Goal, tuple(Path, Moves), C, N) =
        depthSearch(Move, NextState, Goal, tuple([NextState | Path],
            [Str | Moves]), C + 1, N):-
        C < minweight,
        NextState = Move(State, Str),
        not(isMember(NextState, Path)).

    Далее, как обычно, создаются модули для примеров.

        open core, console, list, depth

class facts
    n : positive := 0.

domains
    wstate = tuple(loc BoatLoc, string* LeftSide, string* RightSide).
    loc = left; right.

class predicates
    wmove : move{wstate}.
    unsafestate : (string*) determ.
    wmoveFromTo: (positive, string*, string*, string* [out],
        string* [out], string* [out]) nondeterm.
    subset : (positive, A*, A* [out], A* [out]) nondeterm.
    f: (string*) -> string.
clauses
    wmoveFromTo(K, FromBef, ToBefore, FromAfter, ToAfter, Boat):-
        subset(K, FromBef, Boat, FromAfter),
        not(unsafestate(FromAfter)),
        ToAfter = sort(append(Boat, ToBefore)).

    wmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        wmoveFromTo(1, L, R, L1, R1, B),
        Str = string::format("farmer% moves from left to right", f(B)).
    wmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(0, 1),
        wmoveFromTo(K, R, L, R1, L1, B),
        Str = string::format("farmer% moves from right to left", f(B)).

    f([S]) = string::format(" with %", S):- !.
    f(_) = "".

    unsafestate(L):-
        L = [_, _ | _],
        isMember("goat", L).

    subset(0, L, [], L):- !.
    subset(K, [A | L], [A | L1], L2):-
        subset(K - 1, L, L1, L2).
    subset(K, [A | L], L1, [A | L2]):-
        subset(K, L, L1, L2).

    run():-
        L = sort(["wolf", "goat", "cabbage"]),
        Start = tuple(left, L, []),
        Goal = tuple(right, [], L),
        tuple([S0 | P], Moves) = depthSearch(wmove, Start, Goal, _W),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

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

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

    Для того чтобы можно было использовать предикат subset в другом модуле, его объявление нужно перенести в декларацию класса ex1 (листинг 13.4).

    predicates
    subset : (positive, A*, A* [out], A* [out]) nondeterm.

    open core, console, list, string, depth, ex1

class facts
    n : positive := 0.
    capacity : positive := 2.      % вместимость лодки

domains
    knightOrSquire = k(integer); s(integer).
    kstate = tuple(loc, knightOrSquire*, knightOrSquire*).
    loc = left; right.

class predicates
    kmove : move{kstate}.
    moveFromTo : (positive, knightOrSquire*, knightOrSquire*,
        knightOrSquire* [out], knightOrSquire* [out], 
        knightOrSquire* [out]) nondeterm.
    unsafe: (knightOrSquire*) determ.
    f: (knightOrSquire*) -> string.
    g: (knightOrSquire) -> string.
clauses
    kmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        K = std::downTo(capacity, 2),
        moveFromTo(K, L, R, L1, R1, B),
        Str = format("% from left to right", f(B)).
    kmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(1, capacity),
        moveFromTo(K, R, L, R1, L1, B),
        Str = format("% from right to left", f(B)).

    moveFromTo(N, FromBef, ToBefore, FromAfter, ToAfter, Boat):-
        subset(N, FromBef, Boat, FromAfter),
        not(unsafe(Boat)),
        not(unsafe(FromAfter)),
        ToAfter = sort(append(Boat, ToBefore)),
        not(unsafe(ToAfter)).

    unsafe(L):-
        s(N) = getMember_nd(L),
        not(k(N) = getMember_nd(L)),
        k(_) = getMember_nd(L),
        !.

    f([S]) = format("% moves", g(S)):- !.
    f(L) = format("% move", 
        concatWithDelimiter(map(L, {(X) = g(X)}), ", ")).

    g(k(N)) = concat("knight ", toString(N)).
    g(s(N)) = concat("squire ", toString(N)).

    run():-
        L = sort([s(1), k(1), s(2), k(2), s(3), k(3)]),
        N = list::length(L) div 2,
        capacity := if N < 4 then 2 elseif N < 6 then 3 else 4 end if,
        Start = tuple(left, L, []),
        Goal = tuple(right, [], L),
        tuple([S0 | P], Moves) = depthSearch(kmove, Start, Goal, _W),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

    Предикат downTo недетерминированно возвращает целые числа в указанных пределах в порядке убывания. Предикат list::length/1 возвращает количество элементов списка.

    Для трех рыцарей задача имеет 486 оптимальных решений, которые содержат по 11 переходов. Для четырех рыцарей и трехместной лодки существует 15600 различных оптимальных решений, они содержат по 9 переходов.

    Следующая программа посвящена решению задачи о миссионерах и каннибалах (XIX в.). Три миссионера и три каннибала хотят переправиться через реку с левого берега на правый. В их распоряжении имеется двухместная лодка. Если где-либо каннибалов будет больше, чем миссионеров, то они их съедят. Как они могут переправиться на другой берег?

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

    open core, console, list, string, depth

class facts
    n : positive := 0.
    capacity : positive := 2.      % вместимость лодки

domains
    mstate = tuple(loc, positive*, positive*).
    loc = left; right.

class predicates
    mcmove : move{mstate}.
    mcmoveFromTo: (positive, positive, positive*, positive*,
        positive* [out], positive* [out]) determ.
    f: (positive, positive) -> string.
    g: (positive) -> string.
    b: (positive, positive) determ.
clauses
    mcmoveFromTo(Mb, Cb, [MFromBefore, CFromBefore], 
        [MToBefore, CToBefore], [MFromAfter, CFromAfter],
            [MToAfter, CToAfter]):-
        Cb <= CFromBefore,
        Mb <= MFromBefore,
        b(Mb, Cb),
        MFromAfter = MFromBefore - Mb,
        CFromAfter = CFromBefore - Cb,
        b(MFromAfter, CFromAfter),
        MToAfter = MToBefore + Mb,
        CToAfter = CToBefore + Cb,
        b(MToAfter, CToAfter).

    mcmove(tuple(left, L, R), Str) = tuple(right, L1, R1):-
        K = std::downTo(capacity, 2),
        Cb = std::downTo(K, 0),
        Mb = K - Cb,
        mcmoveFromTo(Mb, Cb, L, R, L1, R1),
        Str = format("% % from left to right", f(Mb, Cb), g(Mb + Cb)).
    mcmove(tuple(right, L, R), Str) = tuple(left, L1, R1):-
        K = std::fromTo(1, capacity),
        Cb = std::fromTo(0, K),
        Mb = K - Cb,
        mcmoveFromTo(Mb, Cb, R, L, R1, L1),
        Str = format("% % from right to left", f(Mb, Cb), g(Mb + Cb)).

    f(0, 1) = "1 cannibal":- !.
    f(0, C) = format("% cannibals", C):- !.
    f(1, 0) = "1 missionary":- !.
    f(M, 0) = format("% missionaries", M):- !.
    f(M, C) = format("%, %", f(M, 0), f(0, C)).

    g(1) = "moves":- !.
    g(_) = "move".

    b(M, C):-
        if M > 0 then M >= C end if.

    run():-
        Start = tuple(left, [3, 3], [0, 0]),
        Goal = tuple(right, [0, 0], [3, 3]),
        capacity := 2,
        tuple([S0 | P], Moves) = depthSearch(mcmove, Start, Goal, _),
            V = varM::new(1),
            n := n + 1,
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
         write("\nвсего - ", n),
        _ = readLine().

    Предикат zip/2 для двух списков одинаковой длины возвращает список, составленный из пар элементов из этих списков с одинаковыми индексами.

    Имеется четыре оптимальных решения для задачи о трех миссионерах, 32 оптимальных решения для задачи о четырех миссионерах и 25 оптимальных решений для задачи с пятью миссионерами.

    13.2. Поиск в ширину в пространстве состояний

    В настоящем параграфе для решения задач применяется поиск в ширину в пространстве состояний. Для ограничения пространства поиска решения не продлеваются в ранее достигнутые состояния. Ведется поиск только одного оптимального решения.

    Ниже приводится универсальный решатель задач методом поиска в ширину в пространстве состояний. Он реализуется в модуле breadth (листинги 13.7–13.8)В листинге 13.8 строку из версии Visual Prolog 7.5 V = varM::new([]), в версии Visual Prolog 7.4 нужно заменить строкой V = varM{State*}::new([]).. 

    predicates
    breadthSearch: (depth::move{State}, State, State, positive [out])
        -> tuple{State*, string*} determ.

        open core, list, depth

domains
    t{State} = t(State*, string*, positive).

class predicates
    breadthPath: (move{State}, t{State}*, State*, State) 
        ->  t{State} nondeterm.
clauses
    breadthSearch(Move, Start, Goal, N) = 
            tuple(reverse(Path), reverse(Moves)):-
        t(Path, Moves, N) = 
            breadthPath(Move, [t([Start], [], 0)], [Start], Goal),
        !.

    breadthPath(_, [t([Goal | Path], Ms, N) | _], _, Goal) = 
        t([Goal | Path], Ms, N):- !.
    breadthPath(Move, [t([State|Path], Ms, N) | PL], StateList, Goal)=
        breadthPath(Move, append(PL, PL1), 
            append(V:value, StateList), Goal):-
       V = varM::new([]),
       PL1 = [t([NextState, State | Path], [Str | Ms], N + 1) ||
            NextState = Move(State, Str),
            not(isMember(NextState, StateList)),
            V:value := [NextState | V:value]].

    Применим решатель к задаче о переливаниях. Имеется несколько сосудов, вмещающих целое количество литров воды, и источник воды (река). Требуется отмерить в первом сосуде заданное целое количество литров воды. Можно наливать воду в сосуды из источника, переливать воду из одного сосуда в другой, так чтобы либо первый сосуд становился пустым, либо второй сосуд полным, а также опорожнять сосуды. Обычно считается, что сосуды упорядочены по убыванию вместимости. В этом случае в первом сосуде можно отмерить любое целое количество литров, которое делится на наибольший общий делитель объемов всех сосудов. Потребуем, чтобы нужное количество литров отмерялось в первом, наибольшем сосуде, а остальные сосуды оказывались бы пустыми. Если сосудов два, то можно показать, что задача в этом случае имеет единственное оптимальное решение. Если сосудов более двух, то оптимальных решений более одного. Пространство состояний в этом случае велико, поэтому мы будем искать только одно оптимальное решение с помощью поиска в ширину.

    open core, console, list, string, breadth

class facts
    volums: (positive*) determ.
clauses
     volums([17, 11, 8]).   % volums([27, 17, 11, 8, 3]).

class predicates
    jmove : depth::move{positive*}.
clauses
    jmove(L, Str) = L1:-
        memberIndex_nd(A, I, L),
        A > 0,
        setNth(I, L, 0, L1),
        Str = format("Вылить % л из %-го сосуда", A, I + 1).
    jmove(L, Str) = L2:-
        volums(VL),
        memberIndex_nd(A, I, L),
        A > 0,
        memberIndex_nd(B, J, L), J <> I,
        V = nth(J, VL),
        B < V,
        Vol = math::min(V - B, A),
        setNth(I, L, A - Vol, L1),
        setNth(J, L1, B + Vol, L2),
        Str = format("Перелить % л из %-го сосуда в %-й", 
            Vol, I + 1, J + 1).
    jmove(L, Str) = L1:-
        volums(VL),
        memberIndex_nd(A, I, L),
        V = nth(I, VL),
        A < V,
        setNth(I, L, V, L1),
        Str = format("Налить % л в %-й сосуд", V - A, I + 1).

    run():-
         Start = [0, 0, 0],
         Goal = [4, 0, 0],
         tuple([S0 | P], Moves) = breadthSearch(jmove, Start, Goal, _),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

    Предикат memberIndex_nd/3 недетерминированно возвращает из списка элементы вместе с их индексами. Предикат setNth/4 заменяет элемент списка, стоящий в заданной позиции, заданным элементом. Предикат nth/2 возвращает элемент списка по его индексу. Предикат min/2 возвращает минимум двух чисел.

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

    Следует перенести указанные ниже объявления в декларацию класса ex2 из его имплементации (листинг 13.10).

    domains
    knightOrSquire = k(integer); s(integer).

predicates
    moveFromTo: (positive, knightOrSquire*, knightOrSquire*,
        knightOrSquire* [out],  knightOrSquire* [out], 
        knightOrSquire* [out]) nondeterm.
    f: (knightOrSquire*) -> string.

    open core, console, list, string, breadth, ex2

domains
    kistate = tuple(loc, knightOrSquire*, knightOrSquire*,
        knightOrSquire*).
    loc = left; right; island.

class predicates
    kimove : depth::move{kistate}.
clauses
    kimove(tuple(left, L, Isl, R), Str) = tuple(right, L1, Isl, R1):-
        moveFromTo(2, L, R, L1, R1, B),
        Str = format("% from left to right", f(B)).
    kimove(tuple(island, L, Isl, R), Str) = tuple(right, L, Isl1, R1):-
        moveFromTo(2, Isl, R, Isl1, R1, B),
        Str = format("% from island to right", f(B)).
    kimove(tuple(left, L, Isl, R), Str) = tuple(island, L1, Isl1, R):-
        moveFromTo(2, L, Isl, L1, Isl1, B),
        Str = format("% from left to island", f(B)).
    kimove(tuple(right, L, Isl, R), Str) = tuple(left, L1, Isl, R1):-
        moveFromTo(1, R, L, R1, L1, B),
        Str = format("% from right to left", f(B)).
    kimove(tuple(island, L, Isl, R), Str) = tuple(left, L1, Isl1, R):-
        moveFromTo(1, Isl, L, Isl1, L1, B),
        Str = format("% from island to left", f(B)).
    kimove(tuple(right, L, Isl, R), Str) = tuple(island, L, Isl1, R1):-
        moveFromTo(1, R, Isl, R1, Isl1, B),
        Str = format("% from right to island", f(B)).

    run():-
        L = sort([s(1), k(1), s(2), k(2), s(3), k(3), s(4), k(4)]),
        Start = tuple(left, L, [], []),
        Goal = tuple(right, [], [], L),
        tuple([S0 | P], Moves) = breadthSearch(kimove, Start, Goal,_),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

    Наконец, используем поиск в ширину для решения задачи о переправе мисиионеров и каннибалов через реку с островом (конец XIX в.). Если на реке имеется остров, на который можно высаживаться, то переправу можно организовать также для любого количества миссионеров и такого же количества каннибалов и двухместной лодки.

    Указанные ниже объявления следует перенести в декларацию класса ex3 из имплементации этого класса (см. листинг 13.12).

    predicates
    mcmoveFromTo: (positive, positive, positive*, positive*,
        positive* [out], positive* [out]) determ.
    f: (positive, positive) -> string.

    open core, console, list, string, breadth, ex3

domains
    mistate = tuple(loc, positive*, positive*, positive*).
    loc = left; right; island.

class predicates
    mimove : depth::move{mistate}.
clauses
    mimove(tuple(left, L, Isl, R), Str) = tuple(right, L1, Isl, R1):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, L, R, L1, R1),
        Str = format("% move from left to right", f(Mb, Cb)).
    mimove(tuple(left, L, Isl, R), Str) = tuple(island, L1, Isl1, R):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, L, Isl, L1, Isl1),
        Str = format("% move from left to island", f(Mb, Cb)).
    mimove(tuple(island, L, Isl, R), Str) = tuple(right, L, Isl1, R1):-
        Cb = std::downTo(2, 0),
        Mb = 2 - Cb,
        mcmoveFromTo(Mb, Cb, Isl, R, Isl1, R1),
        Str = format("% move from island to right", f(Mb, Cb)).
    mimove(tuple(right, L, Isl, R), Str) = tuple(left, L1, Isl, R1):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, R, L, R1, L1),
        Str = format("% moves from right to left", f(Mb, Cb)).
    mimove(tuple(right, L, Isl, R), Str) = tuple(island, L, Isl1, R1):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, R, Isl, R1, Isl1),
        Str = format("% moves from right to island", f(Mb, Cb)).
    mimove(tuple(island, L, Isl, R), Str) = tuple(left, L1, Isl1, R):-
        Cb = std::fromTo(0, 1),
        Mb = 1 - Cb,
        mcmoveFromTo(Mb, Cb, Isl, L, Isl1, L1),
        Str = format("% moves from island to left", f(Mb, Cb)).

    run():-
        N = 4,
        Start = tuple(left, [N, N], [0, 0], [0, 0]),
        Goal = tuple(right, [0, 0], [0, 0], [N, N]),
        tuple([S0| P], Moves) = breadthSearch(mimove, Start, Goal,_),
            V = varM::new(1),
            write("\t", S0), nl,
            forAll(zip(P, Moves), {(tuple(X, S)):-
                writef("%. %\n\t%\n", V:value, S, X), 
                V:value := V:value + 1}), nl,
         fail;
        _ = readLine().

    Упражнения

  • Задача о шатком мосте. Бабушка, дедушка, мать, отец, дочь и сын должны перейти ночью через шаткий мост. У них имеется лишь один фонарь, находиться на мосту без фонаря нельзя. Идти по мосту одновременно могут не более двух человек. Найдите способ семье переправиться через мост за минимальное время, если бабушка может перейти мост за шесть минут, дедушка за пять, мать за четыре, отец за три, дочь за две и сын за одну минуту.
  • Переправа семьи через реку (Алкуин, VIII в.). Мать и отец, каждый весом с воз, и два их сына, которые вместе весят воз, хотят переправиться через реку. В их распоряжении имеется лодка, которая выдерживает вес, равный одному возу. Как им переправиться через реку?
  • Переправа группы людей через реку. Семья — родители, два сына и две дочери — и полицейский с заключенным должны переправиться через реку с помощью плота, который вмещает не более двух человек. Управлять плотом может только взрослый. Нельзя оставлять мать наедине с сыновьями, отца наедине с дочерьми и заключенного в присутствии других людей без полицейского.
  • Задача о бочке. Бочка стоит у реки. С помощью двух кувшинов, вмещающих 8 и 5 литров воды, требуется получить в бочке 41 литр воды, не переливая воду из кувшина в кувшин.
  • Задача о песочных часах. Имеются песочные часы на 8 и 3 минуты. Требуется отмерить 4 минуты.
  • Задача о ферзях. Требуется расставить n ферзей на шахматной доске n x n так, чтобы они не били друг друга.
  • Задача о раскраске. Требуется найти такую раскраску плоской карты, используя не более четырех цветов, чтобы никакие две соседние страны не были раскрашены в один и тот же цвет.
  • Игра в 8. Требуется расставить по порядку восемь перепутанных фишек, на которых написаны номера от единицы до восьми, на поле 3 x 3. Одна из клеток поля пустая, в остальных находится по фишке. За один ход фишку можно передвинуть на соседнее пустое место.
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^