Шахматы, ходы коня

Question

Условия задачи: Имеется шахматная доска, нам даны координаты коня (от 1 до 8) Нам нужно найти все координаты после 2 ходов конем.

Пример:

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

idi=int(input())
idj=int(input())
moves=[[1,2],[1,-2],[-1,2],[-1,-2],
[2,1],[2,-1],[-2,1],[-2,-1]]
a=[]
q=0
for di,dj in moves:
    for ci,cj in moves:
        i=idi+di+ci
        j=idj+dj+cj
        if 0<i<=8 and 0<j<=8 and [i,j] not in a:
            a.append([i,j])
            q+=1 
for i in range(len(a)):
    print(*a[i])
print(q)

Answer 1

Не вижу лишних вариантов. У меня те же 21 вариант получается вашим кодом. И если напечатать доску с вариантами всё выглядит нормально:

print(' ',end=' ')
for j in range(1,9):
  print(j, end=' ')
print()
for i in range(1,9):
  print(i,end=' ')
  for j in range(1,9):
    if [i,j] in a:
      c = 'K'
    else:
      c = '~'
    if i == idi and j == idj:
      c = '#'
    print(c, end=' ')
  print()

  1 2 3 4 5 6 7 8 
1 ~ ~ ~ ~ K ~ K ~ 
2 ~ ~ ~ K ~ K ~ K 
3 ~ ~ K ~ ~ ~ K ~ 
4 ~ ~ ~ K ~ K ~ K 
5 ~ ~ K ~ K ~ # ~ 
6 ~ ~ ~ K ~ K ~ K 
7 ~ ~ K ~ ~ ~ K ~ 
8 ~ ~ ~ K ~ K ~ K

P.S. Отсортировать как в примере можно вот так:

print('\n'.join(['{} {}'.format(x,y) for x,y in sorted(a, key=lambda x: (x[1],x[0]))]))

Вывод:

Но там скорее всего сортировка такая, потому что само решение было немного другое - перебирались все клетки доски и делалась проверка, дойдёт ли туда конь в два хода, т.е. в обратную сторону логика шла.

Answer 2

Вроде у вас всё с кодом хорошо.

В любом случае, если бы, например, вам сказали просчитать ходы вплоть до четвёртого хода, вы бы использовали 4 вложенных цикла?

Я бы использовал рекурсию.

У меня переменная depth отвечает как раз за то, насколько глубоко нужно просчитать ходы.

Есть функция GetNextMoves. Она на вход принимает координаты коня, а возвращает лист возможных позиций коня спустя ход.

Также есть рекурсивная функция CalculateMoves, которая как раз "ходит" по древу всех вариантов.

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

moves=[[1,2],[1,-2],[-1,2],[-1,-2], [2,1],[2,-1],[-2,1],[-2,-1]]
globalArr = []

def CalculateMoves(depth, i, j): 

    arr = GetNextMoves(i, j)

    if depth > 1:

        for move in arr:
            CalculateMoves(depth - 1, move[0], move[1])

    else:

        globalArr.extend(arr)
        #на этом шаге наверное стоит почистить от повторений лист globalArr


def GetNextMoves(i, j):
    arr = []

    for dx, dy in moves:
        x = i + dx
        y = j + dy

        if 0 < x < 9 and 0 < y < 9 and [x, y] not in arr:
            arr.append([x, y])

    return arr

i = int(input())
j = int(input())

CalculateMoves(7, i, j) # глубина хода конём. в вашем случае 2, а не 7

print(globalArr)

БЛОГ НА HUSL

Шахматы, ходы коня

Ответы (2 шт):