#!/usr/bin/env python3
# ------------------------------------------------------------
# Полный перебор всех корректных расстановок флота в «Морской бой»
# с использованием битовых масок вместо numpy‑срезов.
#
# Ключевая идея: 10 × 10 = 100 клеток ► 100 бит ► один int.
# Побитовое «& | ^ << >>» работает в сотни раз быстрее,
# чем индексы и копирование массивов.
# ------------------------------------------------------------
from __future__ import annotations
from dataclasses import dataclass
from typing import List, Tuple
# -----------------------------
# 1. Константы и вспом. функции
# -----------------------------
BOARD_W = BOARD_H = 10 # размер поля
FLEET = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1] # классический набор кораблей
def bit(r: int, c: int) -> int:
"""Координаты (r, c) → соответствующий бит в 100‑битном числе."""
return 1 << (r * BOARD_W + c)
# -------------------------------------------------
# 2. Структура Placement: «корабль» + «ореол касаний»
# -------------------------------------------------
@dataclass(frozen=True, slots=True)
class Placement:
length: int # длина корабля
ship: int # биты занятых клеток
halo: int # ship | соседние клетки (касается/диагональ)
# Ускоренная проверка «касается ли другой корабль»
__slots__ = ("length", "ship", "halo")
# ------------------------------------
# 3. Предварительно генерируем позиции
# ------------------------------------
def generate_all_placements() -> dict[int, list[Placement]]:
"""Создаём словарь {длина: [Placement, …]} для всех 1×…×4."""
pl_dict: dict[int, list[Placement]] = {1: [], 2: [], 3: [], 4: []}
# Перебираем все клетки и два направления: вертикаль(1,0) и горизонт(0,1)
for r in range(BOARD_H):
for c in range(BOARD_W):
for length, dr, dc in (
(1, 0, 0),
(2, 1, 0), (2, 0, 1),
(3, 1, 0), (3, 0, 1),
(4, 1, 0), (4, 0, 1),
):
rr, cc = r + (length - 1) * dr, c + (length - 1) * dc
if not (0 <= rr < BOARD_H and 0 <= cc < BOARD_W):
continue # корабль целиком не помещается
ship_bits = 0
halo_bits = 0
for k in range(length):
sr, sc = r + k * dr, c + k * dc
ship_bits |= bit(sr, sc)
# «ореол»: сам корабль + 8 соседей
for nr in (-1, 0, 1):
for nc in (-1, 0, 1):
tr, tc = sr + nr, sc + nc
if 0 <= tr < BOARD_H and 0 <= tc < BOARD_W:
halo_bits |= bit(tr, tc)
pl_dict[length].append(Placement(length, ship_bits, halo_bits))
return pl_dict
PLACEMENTS: dict[int, list[Placement]] = generate_all_placements()
# ---------------------------------------
# 4. Фильтрация по известным «попаданиям»
# ---------------------------------------
def filter_by_shots(
hits: List[Tuple[int, int]],
misses: List[Tuple[int, int]],
placements: dict[int, list[Placement]] = PLACEMENTS,
) -> dict[int, list[Placement]]:
"""
Убираем варианты, которые:
• ставят корабль на «молоко» (misses)
• не закрывают все клетки из hits, если корабль их пересекает
"""
hits_mask = sum(bit(r, c) for r, c in hits)
misses_mask = sum(bit(r, c) for r, c in misses)
allowed: dict[int, list[Placement]] = {L: [] for L in placements}
for L, plist in placements.items():
for p in plist:
if p.ship & misses_mask:
continue # корабль не может стоять на промахе
# Если корабль пересекает hits, он обязан целиком закрыть их
if (p.ship & hits_mask) and ((p.ship & hits_mask) != (hits_mask & p.ship)):
continue
allowed[L].append(p)
return allowed
# ------------------------------------------
# 5. Рекурсивный backtracking «корабль за кораблём»
# ------------------------------------------
def backtrack(
todo: List[int],
allowed: dict[int, list[Placement]],
occupied: int = 0,
halo: int = 0,
results: List[int] | None = None,
) -> List[int]:
"""
Пытаемся поставить текущий список длин `todo` на поле.
* occupied — уже занятые биты кораблей
* halo — occupied ∪ ореолы (чтобы новые корабли не касались)
"""
if results is None:
results = []
if not todo:
# Все корабли стоят — сохраняем расстановку
results.append(occupied)
return results
length = todo[0]
for plc in allowed[length]:
if plc.halo & halo: # касается другого корабля
continue
backtrack(
todo[1:], allowed,
occupied | plc.ship,
halo | plc.halo,
results,
)
return results
# -------------------------------------------------
# 6. «Высокоуровневая» функция — то, что зовёт юзер
# -------------------------------------------------
def enumerate_boards(
hits: List[Tuple[int, int]] = (),
misses: List[Tuple[int, int]] = (),
fleet: List[int] = FLEET,
) -> List[int]:
"""
Вернёт список целых чисел — битовые маски всех допустимых досок
под известные hits / misses. Если «выстрелов» нет — получаем
полный перебор всех расстановок (но их очень много!).
"""
allowed = filter_by_shots(hits, misses)
return backtrack(sorted(fleet, reverse=True), allowed) # длинные корабли ставим раньше
# -----------------------------------
# 7. Утилиты для просмотра / сохранения
# -----------------------------------
def mask_to_board(mask: int) -> str:
"""Красивый текстовый вывод битовой маски."""
rows = []
for r in range(BOARD_H):
row = []
for c in range(BOARD_W):
row.append("■" if mask & bit(r, c) else "·")
rows.append(" ".join(row))
return "\n".join(rows)
def save_to_file(masks: List[int], filename: str) -> None:
"""Сохраняем список досок в сжатый LZMA‑файл (быстро и компактно)."""
import lzma, pickle
with lzma.open(filename, "wb", preset=9 | lzma.PRESET_EXTREME) as f:
pickle.dump(masks, f, protocol=pickle.HIGHEST_PROTOCOL)
# ------------------
# 8. Пример запуска
# ------------------
if __name__ == "__main__":
# Пример: у нас два промаха и одно попадание
example_hits = [(5, 4)]
example_misses = [(2, 2), (7, 6)]
boards = enumerate_boards(example_hits, example_misses)
print(f"Найдено {len(boards):,} допустимых расстановок")
# Печатаем первые две для проверки:
for i, m in enumerate(boards[:2], 1):
print(f"\n--- Доска #{i} ---")
print(mask_to_board(m))
# Если нужно, сохраняем:
# save_to_file(boards, "boards.xz")