Find shortest path for swapping Hisha and Kaku from the initial position (Puzzle from Shogi Focus 2022.4.10)

hisha-kaku-swap.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
from collections import namedtuple, deque
from datetime import datetime

# We express a "state" as the locations of the seven pieces
# in the order of: ou, hi, kaku, kin1, kin2, gin1, gin2
# with we make sure kin1 < kin2 and gin1 < gin2 to avoid duplicates
#
# Locations are indexed as:
#  0  1  2  3  4  5  6  7  8
#       11 12 13 14 15
#
# So the start state is
#   State(ou=13, hi=7, kaku=1, kin1=12, kin2=14, gin1=11, gin2=15) 
# and the goal state is
#   State(ou=13, hi=1, kaku=7, kin1=12, kin2=14, gin1=11, gin2=15) 
State = namedtuple("State", "ou hi kaku kin1 kin2 gin1 gin2")
START = State(ou=13, hi=7, kaku=1, kin1=12, kin2=14, gin1=11, gin2=15)
GOAL  = State(ou=13, hi=1, kaku=7, kin1=12, kin2=14, gin1=11, gin2=15)


def display(s: State):
  out = ["　"] * 18
  out[s.ou] = "王"
  out[s.hi] = "飛"
  out[s.kaku] = "角"
  out[s.kin1] = "金"
  out[s.kin2] = "金"
  out[s.gin1] = "銀"
  out[s.gin2] = "銀"
  out[9] = "香"
  out[10] = "桂"
  out[16] = "桂"
  out[17] = "香"

  out = ["--"* 9, "歩" * 9, "".join(out[:9]), "".join(out[9:]), "--"* 9]

  print("\n".join(out))
  
  

# We now define the function that returns all next possible states
def next_states(s: State)-> set:
  out = set()
  # move ou
  p = s.ou
  candidates = [p-10, p-9, p-1, p+1, p+9, p+10]
  if p != 0:
    candidates.append(p+8)
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=p, hi=s.hi, kaku=s.kaku, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2) for p in positions])
  
  # move kin1
  p = s.kin1
  candidates = [p-10, p-9, p-1, p+1, p+9]
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin1=min(p, s.kin2), kin2=max(p, s.kin2), gin1=s.gin1, gin2=s.gin2) for p in positions])

  # move kin2
  p = s.kin2
  candidates = [p-10, p-9, p-1, p+1, p+9]
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin1=min(p, s.kin1), kin2=max(p, s.kin1), gin1=s.gin1, gin2=s.gin2) for p in positions])

  # move gin1
  p = s.gin1
  candidates = [p-10, p-9, p+10]
  if p != 0:
    candidates.append(p+8)
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin1=s.kin1, kin2=s.kin2, gin1=min(p, s.gin2), gin2=max(p, s.gin2)) for p in positions])

  # move gin2
  p = s.gin2
  candidates = [p-10, p-9, p+10]
  if p != 0:
    candidates.append(p+8)
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin1=s.kin1, kin2=s.kin2, gin1=min(p, s.gin1), gin2=max(p, s.gin1)) for p in positions])

  # move kaku
  p = s.kaku
  candidates = [p-10, p+10]
  if p != 0:
    candidates.append(p+8)
  if p != 8:
    candidates.append(p-8)
  positions = [c for c in candidates
               if not (c < 0 or c > 15 or c in (9, 10) or c in s)]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=p, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2) for p in positions])

  # move hi
  p = s.hi
  positions = []
  if p > 8:
    if p-9 not in s:
      positions.append(p-9)
  elif p >= 2 and p <= 6:
    if p+9 not in s:
      positions.append(p+9)
  # right
  for j in range(1, 9):
    q = p + j
    if q == 9 or q == 16 or q in s:
      break
    positions.append(q)
  # left
  for j in range(1, 9):
    q = p - j
    if q == -1 or q == 10 or q in s:
      break
    positions.append(q)
  out |= set([State(ou=s.ou, hi=p, kaku=s.kaku, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2) for p in positions])

  return out

def bfs(s0, s1):
  q = deque()   # states to check next
  reached = set()  # stores states already reached
  prev = {}    # maps state -> previous state in a shortest path 
  q.append((s0, 0))
  reached.add(s0)

  curstep = 0  # show the current step to give a hint of the progress
  it = 0        # current iteration count
  t0 = datetime.now()  # start time
  while len(q) > 0:
    s,x = q.popleft()

    it += 1
    curstep = x
    if it % 50000 == 0:
      t1 = datetime.now()
      elapsed = (t1 - t0).total_seconds()
      it_per_sec = it / elapsed if elapsed > 0 else None
      print("\rIter %d | Current Step %d | %.2fit/s" % (it, curstep, it_per_sec), file=sys.stderr, end="")

    for s_next in next_states(s):
      if s_next in reached:  # already reached, skip
        continue
      reached.add(s_next)
      q.append((s_next, x+1))
      prev[s_next] = s
      if s_next == s1:
        t1 = datetime.now()
        print("\nGoal in {} steps! (Iter {}, Elapsed: {})".format(x+1, it, t1-t0))
        return make_path(s0, s1, prev)

def make_path(s0, s1, prev):
  # find a shortest path
  out = [s1]
  s = s1
  while s != s0:
    s = prev[s]
    out.append(s)
    if s == s0:
      break
  #print(out)
  return out[::-1]

def test():
  print("Start:")
  display(START)
  print("Goal:")
  display(GOAL)
  print("First steps:")
  for s in next_states(START):
    display(s)


def main():
  ans = bfs(START, GOAL)
  #ans = bfs(START, State(ou=13, hi=7, kaku=1, kin1=11, kin2=14, gin1=12, gin2=15))
  #ans = bfs(START, State(ou=13, hi=7, kaku=1, kin1=14, kin2=15, gin1=11, gin2=12))
  for i, s in enumerate(ans):
    print("* Step {} *".format(i))
    display(s)

if __name__ == "__main__":
  main()

# A shortest path found
"""
* Step 0 *
------------------
歩歩歩歩歩歩歩歩歩
　角　　　　　飛　
香桂銀金王金銀桂香
------------------
* Step 1 *
------------------
歩歩歩歩歩歩歩歩歩
　角銀　　　　飛　
香桂　金王金銀桂香
------------------
* Step 2 *
------------------
歩歩歩歩歩歩歩歩歩
　角銀　王　　飛　
香桂　金　金銀桂香
------------------
* Step 3 *
------------------
歩歩歩歩歩歩歩歩歩
　　銀　王　　飛　
香桂角金　金銀桂香
------------------
* Step 4 *
------------------
歩歩歩歩歩歩歩歩歩
　　銀角王　　飛　
香桂　金　金銀桂香
------------------
* Step 5 *
------------------
歩歩歩歩歩歩歩歩歩
　　銀角王　　飛　
香桂金　　金銀桂香
------------------
* Step 6 *
------------------
歩歩歩歩歩歩歩歩歩
　　銀角王　銀飛　
香桂金　　金　桂香
------------------
* Step 7 *
------------------
歩歩歩歩歩歩歩歩歩
　　銀　王　銀飛　
香桂金　角金　桂香
------------------
* Step 8 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　王　銀飛　
香桂金銀角金　桂香
------------------
* Step 9 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　銀飛　
香桂金　角金　桂香
------------------
* Step 10 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王角銀飛　
香桂金　　金　桂香
------------------
* Step 11 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　銀飛　
香桂金　　金角桂香
------------------
* Step 12 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　銀飛　
香桂金　金　角桂香
------------------
* Step 13 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　銀飛　
香桂　金金　角桂香
------------------
* Step 14 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　　飛　
香桂　金金銀角桂香
------------------
* Step 15 *
------------------
歩歩歩歩歩歩歩歩歩
　　　銀王　飛　　
香桂　金金銀角桂香
------------------
* Step 16 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　王　飛　　
香桂銀金金銀角桂香
------------------
* Step 17 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　王銀飛　　
香桂銀金金　角桂香
------------------
* Step 18 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　王銀飛　　
香桂銀金　金角桂香
------------------
* Step 19 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　王銀飛角　
香桂銀金　金　桂香
------------------
* Step 20 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　　銀飛角　
香桂銀金王金　桂香
------------------
* Step 21 *
------------------
歩歩歩歩歩歩歩歩歩
　　　　　　飛角　
香桂銀金王金銀桂香
------------------
* Step 22 *
------------------
歩歩歩歩歩歩歩歩歩
　飛　　　　　角　
香桂銀金王金銀桂香
------------------
"""