{}
from itertools import product
"""
지뢰찾기 해답 시각화 + 모호할 때 최대 N개 해답 나열
- 입력: '0'은 미공개 칸, '1'~'8'은 공개된 숫자 힌트
- 출력: X(지뢰), 숫자, .(안전하지만 미공개)로 시각화
- 해답이 확정되지 않으면, 숫자 힌트를 만족하는 가능한 배치를 최대 max_solutions개까지 나열
핵심 수정(버그 픽스):
이전 버전은 미지 칸이 많을 때 논리 추론만 수행해 지뢰가 하나도 안 찍힐 수 있었습니다.
이제는 "프론티어(숫자에 인접한 미지 칸)"만을 변수로 잡아 백트래킹+가지치기를 수행하여
미지 칸이 많아도 현실적으로 해답을 찾고 표시합니다.
"""
def neighbors(r, c, rows, cols):
for dr in [-1,0,1]:
for dc in [-1,0,1]:
if dr == 0 and dc == 0:
continue
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc
def simple_deduction(hints):
"""기본 논리(확정) 추론: 반드시 지뢰/안전인 칸을 반복적으로 확정"""
rows, cols = len(hints), len(hints[0])
board = [[hints[r][c] for c in range(cols)] for r in range(rows)]
mines=set()
changed=True
while changed:
changed=False
for r in range(rows):
for c in range(cols):
if hints[r][c] in "12345678":
needed=int(hints[r][c])
neighs=list(neighbors(r,c,rows,cols))
unknown_neighs=[(nr,nc) for nr,nc in neighs if board[nr][nc]=='0']
mine_count=sum((nr,nc) in mines for nr,nc in neighs)
if needed - mine_count == len(unknown_neighs) and unknown_neighs:
# 인접 미지칸 전부 지뢰
for pos in unknown_neighs:
if pos not in mines:
mines.add(pos)
changed=True
elif needed == mine_count and unknown_neighs:
# 나머지 인접 미지칸 전부 안전
for nr,nc in unknown_neighs:
if board[nr][nc]=='0':
board[nr][nc]='.'
changed=True
return mines, board
def solve_minesweeper(hints, max_solutions=3):
"""
프론티어만 대상으로 백트래킹+가지치기 수행하여 최대 max_solutions개의 해답을 찾는다.
반환값: [ mines_set1, mines_set2, ... ] (각 원소는 (r,c) 0-index 좌표의 집합)
"""
rows, cols = len(hints), len(hints[0])
# 1) 확정 추론으로 일부 칸 정리
fixed_mines, board = simple_deduction(hints)
# 2) 미지 칸 분류: 숫자에 인접한 미지칸만 프론티어로 두고 탐색
unknowns = [(r,c) for r in range(rows) for c in range(cols) if board[r][c]=='0']
num_cells=[(r,c,int(hints[r][c])) for r in range(rows) for c in range(cols) if hints[r][c] in "12345678"]
frontier=[]; deep=[]
for (r,c) in unknowns:
if any(hints[nr][nc] in "12345678" for nr,nc in neighbors(r,c,rows,cols)):
frontier.append((r,c))
else:
deep.append((r,c)) # 숫자에 인접하지 않은 미지칸(제약 없음) → 기본은 안전 취급
# 3) 숫자 제약을 고정 지뢰 반영 후로 업데이트
m=len(num_cells)
needed=[0]*m
for i,(r,c,val) in enumerate(num_cells):
count_fixed=sum((nr,nc) in fixed_mines for nr,nc in neighbors(r,c,rows,cols))
need = val - count_fixed
if need < 0:
return [] # 모순 → 해답 없음
needed[i]=need
# 4) 인접성 행렬(숫자 ↔ 프론티어 변수)
N=len(frontier)
num_to_vars=[[] for _ in range(m)]
var_to_nums=[[] for _ in range(N)]
idx_of_var={frontier[i]:i for i in range(N)}
for i,(r,c,_) in enumerate(num_cells):
for nr,nc in neighbors(r,c,rows,cols):
if (nr,nc) in idx_of_var:
v = idx_of_var[(nr,nc)]
num_to_vars[i].append(v)
var_to_nums[v].append(i)
# 빠른 불가능 체크(필요 지뢰 수 > 해당 숫자가 잡는 프론티어 변수 수)
for i in range(m):
if needed[i] > len(num_to_vars[i]):
return []
# 5) 백트래킹 + 가지치기
assigned_count=[0]*m
unassigned_count=[len(num_to_vars[i]) for i in range(m)]
order=sorted(range(N), key=lambda v: -len(var_to_nums[v])) # 제약 많이 받는 변수부터
assign=[None]*N
solutions=[]
def recurse(k:int):
if len(solutions)>=max_solutions:
return
if k==N:
if all(assigned_count[i]==needed[i] for i in range(m)):
mines=set(fixed_mines)
for v in range(N):
if assign[v]==1:
mines.add(frontier[v])
solutions.append(mines)
return
v=order[k]
for val in (0,1): # 0=안전, 1=지뢰
ok=True
updates=[]
for i in var_to_nums[v]:
new_a = assigned_count[i] + (1 if val==1 else 0)
new_u = unassigned_count[i] - 1
# 가지치기: 과잉/과소 지뢰 금지
if new_a > needed[i] or new_a + new_u < needed[i]:
ok=False
break
updates.append((i, assigned_count[i], unassigned_count[i]))
assigned_count[i]=new_a
unassigned_count[i]=new_u
if ok:
assign[v]=val
recurse(k+1)
assign[v]=None
for i,old_a,old_u in reversed(updates):
assigned_count[i]=old_a
unassigned_count[i]=old_u
if len(solutions)>=max_solutions:
return
recurse(0)
return solutions
def print_board(hints, mines):
rows, cols = len(hints), len(hints[0])
for r in range(rows):
line = []
for c in range(cols):
if (r,c) in mines:
line.append('X')
else:
line.append('.' if hints[r][c]=='0' else hints[r][c])
print(''.join(line))
print()
if __name__ == "__main__":
# 예시: 사용자가 준 보드로 동작 확인
hints = [
"002030",
"200000",
"002403",
"103400",
"000003",
"030300",
]
sols = solve_minesweeper(hints, max_solutions=3)
print(f"Found {len(sols)} solution(s).\n")
for i, sol in enumerate(sols, 1):
print(f"Solution {i} — mines: {len(sol)}")
print_board(hints, sol)