すえ爆の解を探索するやつ

output.txt

SOLVED!

  1 2 3 4 5
A ○ ○ ○ ○ ○
B ○ ○ ○ ○ ○
C ○ ○ ○ ○ ○
D ○ ○ ○ ○ ○
E ○ ○ ○ ○ ○

step 1: E5

  1 2 3 4 5
A ○ ○ ○ ○ ○
B ○ ○ ○ ○ ○
C ○ ○ ○ ○ ○
D ○ ○ ○ ○ ●
E ○ ○ ○ ● ●

step 2: B3

  1 2 3 4 5
A ○ ○ ● ○ ○
B ○ ● ● ● ○
C ○ ○ ● ○ ○
D ○ ○ ○ ○ ●
E ○ ○ ○ ● ●

step 3: D4

  1 2 3 4 5
A ○ ○ ● ○ ○
B ○ ● ● ● ○
C ○ ○ ● ● ○
D ○ ○ ● ● ○
E ○ ○ ○ ○ ●

step 4: E4

  1 2 3 4 5
A ○ ○ ● ○ ○
B ○ ● ● ● ○
C ○ ○ ● ● ○
D ○ ○ ● ○ ○
E ○ ○ ● ● ○

step 5: A1

  1 2 3 4 5
A ● ● ● ○ ○
B ● ● ● ● ○
C ○ ○ ● ● ○
D ○ ○ ● ○ ○
E ○ ○ ● ● ○

step 6: A4

  1 2 3 4 5
A ● ● ○ ● ●
B ● ● ● ○ ○
C ○ ○ ● ● ○
D ○ ○ ● ○ ○
E ○ ○ ● ● ○

step 7: C3

  1 2 3 4 5
A ● ● ○ ● ●
B ● ● ○ ○ ○
C ○ ● ○ ○ ○
D ○ ○ ○ ○ ○
E ○ ○ ● ● ○

step 8: B2

  1 2 3 4 5
A ● ○ ○ ● ●
B ○ ○ ● ○ ○
C ○ ○ ○ ○ ○
D ○ ○ ○ ○ ○
E ○ ○ ● ● ○

step 9: A3

  1 2 3 4 5
A ● ● ● ○ ●
B ○ ○ ○ ○ ○
C ○ ○ ○ ○ ○
D ○ ○ ○ ○ ○
E ○ ○ ● ● ○

step 10: D5

  1 2 3 4 5
A ● ● ● ○ ●
B ○ ○ ○ ○ ○
C ○ ○ ○ ○ ●
D ○ ○ ○ ● ●
E ○ ○ ● ● ●

step 11: B4

  1 2 3 4 5
A ● ● ● ● ●
B ○ ○ ● ● ●
C ○ ○ ○ ● ●
D ○ ○ ○ ● ●
E ○ ○ ● ● ●

step 12: C1

  1 2 3 4 5
A ● ● ● ● ●
B ● ○ ● ● ●
C ● ● ○ ● ●
D ● ○ ○ ● ●
E ○ ○ ● ● ●

step 13: C2

  1 2 3 4 5
A ● ● ● ● ●
B ● ● ● ● ●
C ○ ○ ● ● ●
D ● ● ○ ● ●
E ○ ○ ● ● ●

step 14: D2

  1 2 3 4 5
A ● ● ● ● ●
B ● ● ● ● ●
C ○ ● ● ● ●
D ○ ○ ● ● ●
E ○ ● ● ● ●

step 15: D1

  1 2 3 4 5
A ● ● ● ● ●
B ● ● ● ● ●
C ● ● ● ● ●
D ● ● ● ● ●
E ● ● ● ● ●

suebaku.py

bits = [
	0b11000_10000_00000_00000_00000,
	0b11100_01000_00000_00000_00000,
	0b01110_00100_00000_00000_00000,
	0b00111_00010_00000_00000_00000,
	0b00011_00001_00000_00000_00000,
	0b10000_11000_10000_00000_00000,
	0b01000_11100_01000_00000_00000,
	0b00100_01110_00100_00000_00000,
	0b00010_00111_00010_00000_00000,
	0b00001_00011_00001_00000_00000,
	0b00000_10000_11000_10000_00000,
	0b00000_01000_11100_01000_00000,
	0b00000_00100_01110_00100_00000,
	0b00000_00010_00111_00010_00000,
	0b00000_00001_00011_00001_00000,
	0b00000_00000_10000_11000_10000,
	0b00000_00000_01000_11100_01000,
	0b00000_00000_00100_01110_00100,
	0b00000_00000_00010_00111_00010,
	0b00000_00000_00001_00011_00001,
	0b00000_00000_00000_10000_11000,
	0b00000_00000_00000_01000_11100,
	0b00000_00000_00000_00100_01110,
	0b00000_00000_00000_00010_00111,
	0b00000_00000_00000_00001_00011
]

cellnames = { bits[i]: "ABCDE"[i // 5] + "12345"[i % 5] for i in range(25)}

all_alive = 0b00000_00000_00000_00000_00000
all_dead = 0b11111_11111_11111_11111_11111

def print_matrix(val):
	"""
	盤面の値を適当なフォーマット(下みたいなの)で出力する
	>   1 2 3 4 5
	> A ● ● ● ● ●
	> B ● ○ ● ● ●
	> C ● ● ○ ● ●
	> D ● ○ ○ ● ●
	> E ○ ○ ● ● ●
	"""
	ox = "○●"
	print("  1 2 3 4 5")
	for i in range(5):
		print(f"{'ABCDE'[i]} {' '.join(ox[val >> (24 - i * 5 - j) & 1] for j in range(5))}")

def solve():
	"""
	すえ爆の解を探索する
	"""
 	# current: N手目で初めて到達した盤面
	current = set([all_alive])
	# visited： N手目までで到達しうるすべての盤面と、バックトラック用の情報を辞書にしたもの
	visited = { all_alive: (0, 0) }
	# inverted： N手目までに到達しうるすべての盤面のビットを反転したもの
	#            これは全死の状態から逆向きに探索した時にN手目までに到達しうる盤面の集合になるはず
	inverted = set(all_dead ^ c for c in visited.keys())

	def walk(current, visited):
		"""探索を一手進める"""
		nexts = { c ^ b: (c, b) for c in current for b in bits if c ^ b not in visited }
		next_keys = set(nexts.keys())
		nexts.update(visited)
		return next_keys, nexts

	while True:
		print("walking ...")
		current, visited = walk(current, visited)
		if len(current) == 0:
			raise Exception("no answer")

		inverted.update(all_dead ^ c for c in current)
		if current.intersection(inverted):
			# solved !
			m = current.intersection(inverted).pop()
			return [*reversed(get_steps(visited, m)), *get_steps(visited, all_dead ^ m)]

def get_steps(visited, start):
	"""
	startで指定された盤面からall_aliveの状態に至るまでの手をリストで返す
	"""
	s, b = visited[start]
	steps = [b]
	while s != all_alive:
		s, b = visited[s]
		steps.append(b)
	return steps

if __name__ == "__main__":
	steps = solve()
	current = all_alive
	print(f"\nSOLVED!\n")
	print_matrix(current)
	for i, s in enumerate(steps):
		print(f"\nstep {i + 1}: {cellnames[s]}\n")
		current ^= s
		print_matrix(current)