0

Всем привет! Есть такое условие задачи "На горизонтальной доске состоящей из 7 ячеек расположены три белые и три черные пешки с одной свободной ячейкой между ними...":

введите сюда описание изображения

Хочу ее реализовать на языке программирования python. Есть решение этой задачи на prolog'e:

igra(Finish,[],Finish):-!.
igra(Poloj,[Novpoloj|Podspis],Finish):-dvinuti(Poloj,Novpoloj),igra(Novpoloj,Podspis,Finish).

dvinuti([w,p|Podspis],[p,w|Podspis]). %белая пешка может быть передвинута вправо на соседнюю ячейку, если она свободна
dvinuti([w,b,p|L],[p,b,w|L]). %белая пешка может перепрыгнуть вправо через черную, если там находится свободная ячейка
dvinuti([p,b|L],[b,p|L]). %черная пешка может быть передвинута влево на соседнюю ячейку, если она свободна
dvinuti([p,w,b|L],[b,w,p|L]).%черная пешка может перепрыгнуть влево через белую, если там находится свободная ячейка
dvinuti([A|L],[A|L1]):-dvinuti(L,L1).

Обязательно нужно использовать правила, которые описаны в задачи. Я изначально подумал, что можно сделать два списка, с белыми пешками и с черными, и в цикле использовать pop и так поменять местами их. Но это не правильно. Нужно выполнить те правила.

Подскажите решение этой задачи

7
  • белая не может перепрыгнуть белую (черная-черную)?
    – Jack_oS
    10 апр 2021 в 12:36
  • @Jack_oS да, такого не может быть 10 апр 2021 в 12:51
  • 3
    походит на эту задачку
    – TigerTV.ru
    10 апр 2021 в 13:34
  • Да, это она. Но я нигде не нашел полного решения для произвольных количеств белых и чёрных пешек и размера поля. 11 апр 2021 в 8:13
  • 2
    Пять пешек против тринадцати? Там алгоритм только для симметричных позиций. А он должен быть универсальный и без поиска с возвратом. 11 апр 2021 в 8:36

2 ответа 2

0

Решил для любого количества пешек с правой и левой стороны (пустое место - 1):

from random import randrange

class Solution:
    def __init__(self, n, m):
        self.s = list('1' * n + '_' + '0' * m)
        self.index = n
        self.go_left = randrange(2)
        self.count = (n + 1) * (m + 1) - 1

    def solve(self):
        res = []
        res.append(''.join(self.s))
        for _ in range(self.count):
            self.step()
            res.append(''.join(self.s))
        return res
        
    def step(self):
        i = self.index
        d = 1 - 2 * self.go_left
        j = i + d
        jj = j + d
        # check jump
        if jj >= 0 and jj < len(self.s) and self.s[jj] != self.s[j]:
            self.swap(2) # jump
            return
        if i-1 < 0 or i+1 >= len(self.s) or self.s[i-1] == self.s[i+1]:
            self.swap(-1) # shift
        else:
            self.swap(1) # shift
        self.go_left = not self.go_left
            
    def swap(self, d):
        i = self.index
        if self.go_left:
            j = i - d
        else:
            j = i + d
        self.s[i], self.s[j] = self.s[j], self.s[i]
        self.index = j


left = 3
right = 3
for i in Solution(left, right).solve():
    print(i)

Вывод:

111_000
11_1000
1101_00
11010_0
110_010
1_01010
_101010
01_1010
0101_10
010101_
01010_1
010_011
0_01011
00_1011
0001_11
000_111
-1
def main():
    a = [0, 0, 0, None, 1, 1, 1]

    print(a.reverse())

    print(a)

if __name__ == '__main__':
    main()
1
  • 4
    это не по правилам
    – Интик
    10 апр 2021 в 17:06

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.