โปรแกรมหาจำนวนการเคลื่อนไหวขั้นต่ำของตัวหมากรุกเพื่อเข้าถึงทุกตำแหน่งใน Python

สมมติว่า เรามีกระดานหมากรุกและชิ้นส่วนอัศวิน K ที่เคลื่อนที่เป็นรูปตัว L ภายในกระดาน หากชิ้นส่วนอยู่ในตำแหน่ง (x1, y1) และหากเลื่อนไปที่ (x2, y2) การเคลื่อนที่สามารถอธิบายได้เป็น x2 =x1 ± a; y2 =y1 ± b หรือ x2 =x1 ± b; y2 =y1 ± a; โดยที่ a และ b เป็นจำนวนเต็ม เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำสำหรับตัวหมากรุกนั้นที่จะไปถึงตำแหน่ง (n-1, n-1) บนกระดานหมากรุกจากตำแหน่ง (0, 0) หากตำแหน่งไม่สามารถเข้าถึงได้ จะถูกทำเครื่องหมาย -1 มิฉะนั้น จำนวนการเคลื่อนไหวจะถูกส่งคืน เราจะพิมพ์เอาต์พุต n – 1 บรรทัด โดยในแต่ละบรรทัด i จะมี n − 1 จำนวนเต็มที่อธิบายจำนวนการเคลื่อนไหวขั้นต่ำที่ชิ้นส่วนต้องทำสำหรับแต่ละ j

ดังนั้นหากอินพุตเท่ากับ n =6 เอาต์พุตจะเป็น

5  4  3  2  5
4 -1  2 -1 -1
3  2 -1 -1 -1
2 -1 -1 -1 -1
5 -1 -1 -1  1

การเคลื่อนไหวที่เป็นไปได้สำหรับอัศวินหากอยู่ในตำแหน่ง (3, 3) ในกระดานหมากรุกขนาด 5x5

บรรทัดแรกของเอาต์พุตมีจำนวนการเคลื่อนไหวขั้นต่ำที่ชิ้นส่วนต้องไปถึงตำแหน่ง (1,1) ถึง (1,5) บรรทัดที่ต่อเนื่องกันอธิบายจำนวนการเคลื่อนไหวขั้นต่ำสำหรับแต่ละค่า I และ j ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน path_search() นี่จะใช้เวลา i, j, n

  • temp_list :=แผนที่ใหม่เริ่มต้นด้วยคู่ (-1, -1)

  • queue_positional :=รายการใหม่ที่เริ่มต้นโดยคู่ (0, 0)

  • ver :=[(i, j) ,(-i, j) ,(i, -j) ,(-i, -j) ,(j, i) ,(j, -i) ,(-j, ผม ) ,(-j, -i) ]

  • ในขณะที่ขนาดของ queue_positional> 0 ทำ

    • current_element :=ลบองค์ประกอบแรกออกจาก queue_positional

    • สำหรับแต่ละองค์ประกอบใน ver ทำ

      • x :=องค์ประกอบ[0] + current_element[0]

      • y :=องค์ประกอบ[1] + องค์ประกอบปัจจุบัน[1]

      • ถ้า -1

        • temp_list[x, y] :=current_element

        • แทรกคู่ (x, y) ที่ส่วนท้ายของ queue_positional

        • ถ้า x เหมือนกับ n - 1 และ y เหมือนกับ n - 1 แล้ว

          • count_var :=1

          • ในขณะที่ temp_list[x,y] ไม่เหมือนกับ(0, 0) ทำ

            • count_var :=count_var + 1

            • x, y :=temp_list[x,y]

          • ส่งคืน count_var

  • กลับ -1

จากฟังก์ชัน/วิธีการหลัก ให้ทำดังนี้ −

• กระดาน :=แผนที่ใหม่เริ่มต้นด้วย -1

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • สำหรับ j ในช่วง 1 ถึง i ทำ

    • ถ้า board[i, j] เหมือนกับ -1 แล้ว

      • board[i, j] :=path_search(i, j, n)

      • บอร์ด[j, i] :=บอร์ด[i, j]

    • ถ้า (n - 1) mod i เท่ากับ 0 แล้ว

      • กระดาน[i, i] :=(n - 1) / i

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • สำหรับ j ในช่วง 1 ถึง n - 1 ทำ

    • พิมพ์(บอร์ด[i, j])

  • พิมพ์(บอร์ด[i, n - 1])

ซอร์สโค้ด (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from collections import defaultdict
def path_search(i, j, n):
   temp_list = defaultdict(lambda: (-1,-1))
   queue_positional = [(0, 0)]
   ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
   while len(queue_positional) > 0:
      current_element = queue_positional.pop(0)
      for element in ver:
         x = element[0] + current_element[0]
         y = element[1] + current_element[1]
         if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
            temp_list[x, y] = current_element
            queue_positional.append((x, y))
            if x == n - 1 and y == n - 1:
               count_var = 1
               while temp_list[x,y]!=(0,0):
                  count_var += 1
                  x, y = temp_list[x,y]
               return count_var
   return -1

def solve(n):
   board = defaultdict(lambda: -1)
   for i in range(1, n):
      for j in range(1, i):
         if board[i, j] == -1:
            board[i, j] = path_search(i, j, n)
            board[j, i] = board[i, j]
      if (n - 1) % i == 0:
         board[i, i] = (n - 1) / i

   for i in range(1, n):
      for j in range(1, n - 1):
         print(int(board[i, j]), end = ' ')
   print(int(board[i, n - 1]))

solve(6)

อินพุต

6

ผลลัพธ์

5  4  3  2  5
4 -1  2 -1 -1
3  2 -1 -1 -1
2 -1 -1 -1 -1
5 -1 -1 -1  1