八皇后座位安排

import random
from collections import defaultdict

class Classroom:
def init(self, cid, rows, cols):
self.id = cid
self.rows = rows
self.cols = cols
self.grid = [[None for _ in range(cols)] for _ in range(rows)]

def get_available_positions(self):
return [(i,j) for i in range(self.rows)
for j in range(self.cols) if self.grid[i][j] is None]

def print_layout(self):
print(f"\n教室 {self.id} 座位分布（{self.rows}行×{self.cols}列）：")
for row_idx, row in enumerate(self.grid):
print("|", end="")
for seat in row:
display = seat if seat else '---'
print(f" {display:^8} |", end="")
print("\n" + "-"*(11*(self.cols)+1))

class Team:
def init(self, tid, size):
self.id = tid
self.size = size
self.allocations = defaultdict(list) # {教室ID: [(座位坐标, 选手号)]}
self.next_member = 1 # 下一个要分配的成员编号

def get_next_identifier(self):
identifier = f"T{self.id}-P{self.next_member}"
self.next_member += 1
return identifier

def find_valid_positions(available, k):
n = len(available)
if n < k: return None

result = []
def backtrack(start, path):
if len(path) == k:
result.extend(path)
return True
for i in range(start, n):
pos = available[i]
conflict = any(pos[0]==p[0] or pos[1]==p[1] or
abs(pos[0]-p[0]) == abs(pos[1]-p[1])
for p in path)
if not conflict:
if backtrack(i+1, path + [pos]):
return True
return False

if backtrack(0, []):
return result
return None

def allocate_seats(teams, classrooms):
random.shuffle(teams)
random.shuffle(classrooms)

for team in teams:
remaining = team.size
for classroom in classrooms:
if remaining <= 0: break

available = classroom.get_available_positions()
if not available: continue

for k in range(min(remaining, len(available)), 0, -1):
random.shuffle(available)
selected = find_valid_positions(available, k)
if selected:
for (i,j) in selected:
identifier = team.get_next_identifier()
classroom.grid[i][j] = identifier
team.allocations[classroom.id].append( ((i,j), identifier) )
remaining -= k
break
if remaining > 0:
raise RuntimeError(f"队伍{team.id}分配失败，剩余{remaining}人")

def input_parameters():
team_count = int(input("请输入参赛队伍数量: "))
uniform_team_size = input("所有队伍人数是否相同？(y/n): ").lower() == 'y'

if uniform_team_size:
team_size = int(input("请输入统一的队伍人数: "))
teams = [Team(i+1, team_size) for i in range(team_count)]
else:
teams = []
for i in range(team_count):
size = int(input(f"请输入队伍{i+1}的人数: "))
teams.append(Team(i+1, size))

classroom_count = int(input("\n请输入教室数量: "))
uniform_classroom = input("所有教室规格是否相同？(y/n): ").lower() == 'y'

if uniform_classroom:
rows = int(input("请输入教室行数: "))
cols = int(input("请输入教室列数: "))
classrooms = [Classroom(i+1, rows, cols) for i in range(classroom_count)]
else:
classrooms = []
for i in range(classroom_count):
r = int(input(f"请输入教室{i+1}的行数: "))
c = int(input(f"请输入教室{i+1}的列数: "))
classrooms.append(Classroom(i+1, r, c))

return teams, classrooms