Shogi Puzzle from Shogi Focus 2025.1.12

shogi-puzzle_20250112.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, 2025.1.12)
#
# Start:
#   ------
#   金飛　
#   歩角と
#   王香銀
#   ------
#
# Goal:
#   ------
#   歩金角
#   銀香と
#   飛　王
#   ------
#
# We express a "state" as the locations of the eight pieces
# in the order of: ou, hi, kaku, kin, gin, kyo, TO, FU
#
# Locations are indexed as:
#  0  1  2
#  3  4  5
#  6  7  8
#
# So the start state is
#   State(ou=6, hi=1, kaku=4, kin=0, gin=8, kyo=7, to=5, fu=3) 
# and the goal state is
#   State(ou=8, hi=6, kaku=2, kin=1, gin=3, kyo=4, to=5, fu=0)
State = namedtuple("State", "ou hi kaku kin gin kyo to fu")
START = State(ou=6, hi=1, kaku=4, kin=0, gin=8, kyo=7, to=5, fu=3) 
GOAL  = State(ou=8, hi=6, kaku=2, kin=1, gin=3, kyo=4, to=5, fu=0)


def display(s: State):
  out = ["　"] * 9
  out[s.ou] = "王"
  out[s.hi] = "飛"
  out[s.kaku] = "角"
  out[s.kin] = "金"
  out[s.gin] = "銀"
  out[s.kyo] = "香"
  out[s.to] = "と"
  out[s.fu] = "歩"

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

  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 = []
  if p >= 3:
    candidates.append(p-3)
  if p >= 3 and p % 3 != 0:
    candidates.append(p-4)
  if p >= 3 and p % 3 != 2:
    candidates.append(p-2)
  if p % 3 != 0:
    candidates.append(p-1)
  if p % 3 != 2:
    candidates.append(p+1)
  if p < 6:
    candidates.append(p+3)
  if p < 6 and p % 3 != 0:
    candidates.append(p+2)
  if p < 6 and p % 3 != 2:
    candidates.append(p+4)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=p, hi=s.hi, kaku=s.kaku, kin=s.kin, gin=s.gin, kyo=s.kyo, to=s.to, fu=s.fu) for p in positions])
  
  # move hi
  # note. in this game, hi can at most one step from the current position
  p = s.hi
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  if p < 6:
    candidates.append(p+3)
  if p % 3 != 0:
    candidates.append(p-1)
  if p % 3 != 2:
    candidates.append(p+1)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=p, kaku=s.kaku, kin=s.kin, gin=s.gin, kyo=s.kyo, to=s.to, fu=s.fu) for p in positions])

  # move kaku
  # note. in this game, hi can at most one step from the current position
  p = s.kaku
  candidates = []
  if p >= 3 and p % 3 != 0:
    candidates.append(p-4)
  if p >= 3 and p % 3 != 2:
    candidates.append(p-2)
  if p < 6 and p % 3 != 0:
    candidates.append(p+2)
  if p < 6 and p % 3 != 2:
    candidates.append(p+4)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=p, kin=s.kin, gin=s.gin, kyo=s.kyo, to=s.to, fu=s.fu) for p in positions])


  # move kin
  p = s.kin
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  if p >= 3 and p % 3 != 0:
    candidates.append(p-4)
  if p >= 3 and p % 3 != 2:
    candidates.append(p-2)
  if p % 3 != 0:
    candidates.append(p-1)
  if p % 3 != 2:
    candidates.append(p+1)
  if p < 6:
    candidates.append(p+3)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin=p, gin=s.gin, kyo=s.kyo, to=s.to, fu=s.fu) for p in positions])

  # move gin
  p = s.gin
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  if p >= 3 and p % 3 != 0:
    candidates.append(p-4)
  if p >= 3 and p % 3 != 2:
    candidates.append(p-2)
  if p < 6 and p % 3 != 0:
    candidates.append(p+2)
  if p < 6 and p % 3 != 2:
    candidates.append(p+4)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin=s.kin, gin=p, kyo=s.kyo, to=s.to, fu=s.fu) for p in positions])
  
  # move kyo
  # note. in this game, hi can at most one step from the current position
  p = s.kyo
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin=s.kin, gin=s.gin, kyo=p, to=s.to, fu=s.fu) for p in positions])

  # move to
  p = s.to
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  if p >= 3 and p % 3 != 0:
    candidates.append(p-4)
  if p >= 3 and p % 3 != 2:
    candidates.append(p-2)
  if p % 3 != 0:
    candidates.append(p-1)
  if p % 3 != 2:
    candidates.append(p+1)
  if p < 6:
    candidates.append(p+3)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin=s.kin, gin=s.gin, kyo=s.kyo, to=p, fu=s.fu) for p in positions])

  # move fu
  p = s.fu
  candidates = []
  if p >= 3:
    candidates.append(p-3)
  positions = [c for c in candidates if c not in s]
  out |= set([State(ou=s.ou, hi=s.hi, kaku=s.kaku, kin=s.kin, gin=s.gin, kyo=s.kyo, to=s.to, fu=p) 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()


# 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 *
------
歩金角
銀　と
飛香王
------
* Step 20 *
------
歩金角
銀香と
飛　王
------
"""