1. Артур играет с другом в морской бой. Один игрок расставляет на поле 10 × 10 десять кораблей: четыре 1 × 1, три 1 × 2, два 1 × 3 и один 1 × 4. Корабли не должны касаться друг друга даже вершинами. По рисунку: попадания — A1, B1, J1, E2, E3, J3, J4, J5, A5, F5, C6, D6, J7, B9; промахи — G5, A6, F6, A9, C9, B10. Сколько существует допустимых расстановок кораблей?

Попадания должны приходиться на клетки кораблей, а клетки с промахами не должны быть заняты. Между любыми двумя кораблями должна оставаться хотя бы одна клетка по горизонтали, вертикали и диагонали.

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

H = {(0,0),(1,0),(9,0),(4,1),(4,2),(9,2),(9,3),
     (9,4),(0,4),(5,4),(2,5),(3,5),(9,6),(1,8)}
M = {(6,4),(0,5),(5,5),(0,8),(2,8),(1,9)}

# Координата клетки — (столбец, строка); оба значения от 0 до 9.
def placements(length):
    result = set()
    for dr, dc in {(0, 1), (1, 0)}:
        for r in range(10):
            for c in range(10):
                cells = frozenset((r + i*dr, c + i*dc)
                                  for i in range(length))
                if all(0 <= x < 10 and 0 <= y < 10
                       for x, y in cells) and not (cells & M):
                    result.add(cells)
    return sorted(result, key=lambda p: tuple(sorted(p)))

P = {n: placements(n) for n in (1, 2, 3, 4)}
lengths = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1]
answer = 0

def search(k, blocked, covered, last):
    global answer
    if k == len(lengths):
        if H <= covered:
            answer += 1
        return
    n = lengths[k]
    start = last + 1 if k > 0 and lengths[k-1] == n else 0
    for i in range(start, len(P[n])):
        cells = P[n][i]
        if cells & blocked:
            continue
        halo = {(r+dr, c+dc) for r, c in cells
                for dr in (-1, 0, 1) for dc in (-1, 0, 1)
                if 0 <= r+dr < 10 and 0 <= c+dc < 10}
        search(k+1, blocked | halo, covered | cells, i)

search(0, set(), set(), -1)
print(answer)

Я не могу надёжно сообщить числовой результат, не исполнив перебор; приведённый код вычисляет его по всем расстановкам и выводит на экран.