def индексы():
global list4, list3, list1, list2
zz=list(map(tuple, np.argwhere(x==0).tolist()))
_2в=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0],i[1]-1),(i[0],i[1]+1),(i[0]+1,i[1]-1),(i[0]+1,i[1]+1),(i[0]+1,i[1]),(i[0]+2,i[1]-1),(i[0]+2,i[1]),(i[0]+2,i[1]+1)], "в", 2)
for i in zz if 1<=i[0]<=9 and i[1]>=1 and np.max(x[i[0]-1:i[0]+3,i[1]-1:i[1]+2])<=1 and np.max(x[i[0]:i[0]+2:1, i[1]])==0]
_2г=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0]-1,i[1]+2),(i[0],i[1]-1),(i[0],i[1]+1),(i[0],i[1]+2),(i[0]+1,i[1]-1),(i[0]+1,i[1]),(i[0]+1,i[1]+1),(i[0]+1,i[1]+2)], "г", 2)
for i in zz if i[0]>=1 and 1<=i[1]<=9 and np.max(x[i[0]-1:i[0]+2,i[1]-1:i[1]+3])<=1 and np.max(x[i[0]:i[0]+1, i[1]:i[1]+2])==0]
_3в=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0],i[1]-1),(i[0],i[1]+1),(i[0]+1,i[1]-1),(i[0]+1,i[1]+1),(i[0]+1,i[1]),(i[0]+2,i[1]-1),(i[0]+2,i[1]),(i[0]+2,i[1]+1),(i[0]+3,i[1]-1),(i[0]+3,i[1]),(i[0]+3,i[1]+1)], "в", 3)
for i in zz if 1<=i[0]<=8 and i[1]>=1 and np.max(x[i[0]-1:i[0]+4,i[1]-1:i[1]+2])<=1 and np.max(x[i[0]:i[0]+3:1, i[1]])==0]
_3г=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0]-1,i[1]+2),(i[0]-1,i[1]+3),(i[0],i[1]-1),(i[0],i[1]+1),(i[0],i[1]+2),(i[0],i[1]+3),(i[0]+1,i[1]-1),(i[0]+1,i[1]),(i[0]+1,i[1]+1),(i[0]+1,i[1]+2),(i[0]+1,i[1]+3)], "г", 3) for i in zz if i[0]>=1 and 1<=i[1]<=8 and np.max(x[i[0]-1:i[0]+2,i[1]-1:i[1]+4])<=1 and np.max(x[i[0]:i[0]+1, i[1]:i[1]+3])==0]
_4в=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0],i[1]-1),(i[0],i[1]+1),(i[0]+1,i[1]-1),(i[0]+1,i[1]+1),(i[0]+1,i[1]),(i[0]+2,i[1]-1),(i[0]+2,i[1]),(i[0]+2,i[1]+1),(i[0]+3,i[1]-1),(i[0]+3,i[1]),(i[0]+3,i[1]+1),(i[0]+4,i[1]-1),(i[0]+4,i[1]),(i[0]+4,i[1]+1)], "в", 4) for i in zz if 1<=i[0]<=7 and i[1]>=1 and np.max(x[i[0]-1:i[0]+5,i[1]-1:i[1]+2])<=1 and np.max(x[i[0]:i[0]+4:1, i[1]])==0]
_4г=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0]-1,i[1]+2),(i[0]-1,i[1]+3),(i[0]-1,i[1]+4),(i[0],i[1]-1),(i[0],i[1]+1),(i[0],i[1]+2),(i[0],i[1]+3),(i[0],i[1]+4),(i[0]+1,i[1]-1),(i[0]+1,i[1]),(i[0]+1,i[1]+1),(i[0]+1,i[1]+2),(i[0]+1,i[1]+3),(i[0]+1,i[1]+4)], "г", 4) for i in zz if i[0]>=1 and 1<=i[1]<=7 and np.max(x[i[0]-1:i[0]+2,i[1]-1:i[1]+5])<=1 and np.max(x[i[0]:i[0]+1, i[1]:i[1]+4])==0]
list1=[([i,(i[0]-1,i[1]-1),(i[0]-1,i[1]),(i[0]-1,i[1]+1),(i[0],i[1]-1),(i[0],i[1]+1),(i[0]+1,i[1]-1),(i[0]+1,i[1]),(i[0]+1,i[1]+1)],"", 1)
for i in zz if i[0]>=1 and i[1]>=1 and np.max(x[i[0]-1:i[0]+2,i[1]-1:i[1]+2])<=1]
list2=_2в+_2г
list3=_3в+_3г
list4=_4в+_4г
def product_with_skip(*iterables):
global ff
длина=len(iterables)
for prod in product(*iterables):
ff+=1
mm=set()
for z in prod: mm.update(z[0][1:])
if len(set([z[0][0] for z in prod if z[0][0] not in mm]))==длина:
yield prod
обстреленные([5,4],[2,2],[3,1],[1,3],[2,0],[2,6],[1,7],[0,5],[2,4],[7,9],[4,9],[5,6],[9,8],[6,8],[8,7],[9,6],[7,6],)
убитые({"one":[[8,1],[0,8],[8,4],[5,9],],"верт2":[[4,7],],"гор2":[[4,3],],
"верт3":[[0,1],],"гор3":[[],],"гор4":[[6,1],],
"верт4":[[]]})
индексы()
запись_дампа=True
счет=0
ff=0
with open('D:\\SSDTEMP\\download\\Python_work\\морской бой\\out.txt', "w") as зап:
for i in product_with_skip(list3,list2):
cop=np.copy(x)
flag=True
flag2=True
for z in i:
if z[2]==4:
kk=z[0][0][0]
kk2=z[0][0][1]
if z[1]=="в":
if flag2:
cop[kk:kk+4:1, kk2]=2
flag2=False
elif np.max(cop[kk-1:kk+5,kk2-1:kk2+2])<=1:
cop[kk:kk+4:1, kk2]=2
else: flag=False; break
elif z[1]=="г":
if flag2:
cop[kk:kk+1, kk2:kk2+4]=2
flag2=False
elif np.max(cop[kk-1:kk+2,kk2-1:kk2+5])<=1:
cop[kk:kk+1, kk2:kk2+4]=2
else: flag=False; break
elif z[2]==3:
kk=z[0][0][0]
kk2=z[0][0][1]
if z[1]=="в":
if flag2:
cop[kk:kk+3:1, kk2]=2
flag2=False
elif np.max(cop[kk-1:kk+4,kk2-1:kk2+2])<=1:
cop[kk:kk+3:1, kk2]=2
else: flag=False; break
elif z[1]=="г":
if flag2:
cop[kk:kk+1, kk2:kk2+3]=2
flag2=False
elif np.max(cop[kk-1:kk+2,kk2-1:kk2+4])<=1:
cop[kk:kk+1, kk2:kk2+3]=2
else: flag=False; break
elif z[2]==2:
kk=z[0][0][0]
kk2=z[0][0][1]
if z[1]=="в":
if flag2:
cop[kk:kk+2:1, kk2]=2
flag2=False
elif np.max(cop[kk-1:kk+3,kk2-1:kk2+2])<=1:
cop[kk:kk+2:1, kk2]=2
else: flag=False; break
elif z[1]=="г":
if flag2:
cop[kk:kk+1, kk2:kk2+2]=2
flag2=False
elif np.max(cop[kk-1:kk+2,kk2-1:kk2+3])<=1:
cop[kk:kk+1, kk2:kk2+2]=2
else: flag=False; break
elif z[2]==1:
kk=z[0][0][0]
kk2=z[0][0][1]
if flag2:
cop[kk, kk2]=3
flag2=False
elif np.max(cop[kk-1:kk+2,kk2-1:kk2+2])<=1:
cop[kk, kk2]=3
else: flag=False; break
if flag==False: continue
комб=str(cop[1:,1:].tolist())
if комб not in zz:
видимость(cop)
zz.add(комб)
if запись_дампа: зап.write(комб+"\n")
# hh_объем+=cop
счет+=1
#!/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")