shogi-puzzle_20241006.py

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

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

# Q. Find the sortest steps from the start and goal positions below. 
#    (Source: Shogi Focus, 2024.10.6)
#
# Start:
#   --------
#   　香　銀
#   金飛金桂
#   歩　歩　
#   桂歩銀　
#   --------
#
# Goal:
#   --------
#   　香銀飛
#   歩桂歩桂
#   金　金　
#   　歩　銀
#   --------
#
# We express a "state" as the locations of the eleven pieces
# in the order of: hi, kin1, kin2, gin1, gin2, kei1, kei2, kyo, fu1, fu2, fu3
#
# Locations are indexed as:
#  0  1  2  3
#  4  5  6  7
#  8  9 10 11
# 12 13 14 15
#
# So the start state is
#   State(hi=5, kin1=4, kin2=6, gin1=3, gin2=14, kei1=7, kei2=12, kyo=1, fu1=8, fu2=10, fu3=13) 
# and the goal state is
#   State(hi=3, kin1=8, kin2=10, gin1=2, gin2=15, kei1=5, kei2=7, kyo=1, fu1=4, fu2=6, fu3=13) 
State = namedtuple("State", "hi kin1 kin2 gin1 gin2 kei1 kei2 kyo fu1 fu2 fu3")
START = State(hi=5, kin1=4, kin2=6, gin1=3, gin2=14, kei1=7, kei2=12, kyo=1, fu1=8, fu2=10, fu3=13)
GOAL  = State(hi=3, kin1=8, kin2=10, gin1=2, gin2=15, kei1=5, kei2=7, kyo=1, fu1=4, fu2=6, fu3=13) 


def display(s: State):
  out = ["　"] * 16
  out[s.hi] = "飛"
  out[s.kin1] = "金"
  out[s.kin2] = "金"
  out[s.gin1] = "銀"
  out[s.gin2] = "銀"
  out[s.kei1] = "桂"
  out[s.kei2] = "桂"
  out[s.kyo] = "香"
  out[s.fu1] = "歩"
  out[s.fu2] = "歩"
  out[s.fu3] = "歩"

  out = ["--"* 4, "".join(out[:4]), "".join(out[4:8]), "".join(out[8:12]), "".join(out[12:]), "--"* 4]

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

# We now define the function that returns all next possible states
def next_states(s: State)-> set:
  out = set()
  # move hi
  p = s.hi
  candidates = []
  ## up
  q = p
  while q >= 4:
    q -= 4
    if q in s:
      break
    candidates.append(q)
  ## down
  q = p
  while q < 12:
    q += 4
    if q in s:
      break
    candidates.append(q)
  ## left
  q = p
  while q % 4 != 0:
    q -= 1
    if q in s:
      break
    candidates.append(q)
  ## right
  q = p
  while q % 4 != 3:
    q += 1
    if q in s:
      break
    candidates.append(q)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=p, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])

  # move kin1
  p = s.kin1
  candidates = []
  if p >= 4:
    candidates.append(p-4)
  if p >= 4 and p % 4 != 0:
    candidates.append(p-5)
  if p >= 4 and p % 4 != 2:
    candidates.append(p-3)
  if p % 4 != 0:
    candidates.append(p-1)
  if p % 4 != 3:
    candidates.append(p+1)
  if p < 12:
    candidates.append(p+4)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=s.hi, kin1=min(p, s.kin2), kin2=max(p, s.kin2), gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])

  # move kin2
  p = s.kin2
  candidates = []
  if p >= 4:
    candidates.append(p-4)
  if p >= 4 and p % 4 != 0:
    candidates.append(p-5)
  if p >= 4 and p % 4 != 2:
    candidates.append(p-3)
  if p % 4 != 0:
    candidates.append(p-1)
  if p % 4 != 3:
    candidates.append(p+1)
  if p < 12:
    candidates.append(p+4)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=s.hi, kin1=min(p, s.kin1), kin2=max(p, s.kin1), gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])

  # move gin1
  p = s.gin1
  candidates = []
  if p >= 4:
    candidates.append(p-4)
  if p >= 4 and p % 4 != 0:
    candidates.append(p-5)
  if p >= 4 and p % 4 != 2:
    candidates.append(p-3)
  if p < 12 and p % 4 != 0:
    candidates.append(p+3)
  if p < 12 and p % 4 != 3:
    candidates.append(p+5)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=min(p, s.gin2), gin2=max(p, s.gin2), kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])

  # move gin1
  p = s.gin2
  candidates = []
  if p >= 4:
    candidates.append(p-4)
  if p >= 4 and p % 4 != 0:
    candidates.append(p-5)
  if p >= 4 and p % 4 != 2:
    candidates.append(p-3)
  if p < 12 and p % 4 != 0:
    candidates.append(p+3)
  if p < 12 and p % 4 != 3:
    candidates.append(p+5)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=min(p, s.gin1), gin2=max(p, s.gin1), kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])

  # move kei1
  # ... cannot move!

  # move kei2
  p = s.kei2
  candidates = []
  if p == 12:
    candidates.append(5)
  positions = [c for c in candidates if c not in s]
  out |= set([State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2, kei1=min(p, s.kei2), kei2=max(p, s.kei1), kyo=s.kyo, fu1=s.fu1, fu2=s.fu2, fu3=s.fu3) for p in positions])
  
  # move kyo
  # ...cannot move!

  # move fu1
  p = s.fu1
  candidates = []
  if p in (8, 10, 13):
    candidates.append(p-4)
  positions = [c for c in candidates if c not in s]
  for p in positions:
    fus = sorted([p, s.fu2, s.fu3])
    out.add(State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=fus[0], fu2=fus[1], fu3=fus[2]))

  # move fu2
  p = s.fu2
  candidates = []
  if p in (8, 10, 13):
    candidates.append(p-4)
  positions = [c for c in candidates if c not in s]
  for p in positions:
    fus = sorted([p, s.fu1, s.fu3])
    out.add(State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=fus[0], fu2=fus[1], fu3=fus[2]))

  # move fu3
  p = s.fu3
  candidates = []
  if p in (8, 10, 13):
    candidates.append(p-4)
  positions = [c for c in candidates if c not in s]
  for p in positions:
    fus = sorted([p, s.fu1, s.fu2])
    out.add(State(hi=s.hi, kin1=s.kin1, kin2=s.kin2, gin1=s.gin1, gin2=s.gin2, kei1=s.kei1, kei2=s.kei2, kyo=s.kyo, fu1=fus[0], fu2=fus[1], fu3=fus[2]))

  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()


"""
Result:

* 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 *
--------
　香銀飛
歩桂歩桂
金　金　
　歩　銀
--------
"""