AlgoVerse

کاشی‌کاری با ترومینو

صفحه‌ی 2^k × 2^k با یک خانه‌ی کم را با کاشی‌های L شکل سه‌خانه‌ای می‌پوشاند: صفحه را چهار تکه می‌کند، یک ترومینو در وسط می‌گذارد تا هر تکه دقیقاً یک خانه‌ی پر داشته باشد، و هر تکه را بازگشتی حل می‌کند. اثبات استقرایی به شکل الگوریتم.

صفحه‌ای 2^k × 2^k داریم که یک خانه‌اش کم است. آیا می‌شود بقیه را با ترومینو (کاشی L شکل سه‌خانه‌ای) پوشاند؟ تعداد خانه‌ها 4^k − 1 است که بر ۳ بخش‌پذیر است، ولی این کافی نیست؛ باید راهی ساخت.

ادامه‌ی توضیح ↓
ورودی:
k=3 · row=2 · col=5خروجی PDF

صفحه‌ی ۸ × ۸ (k = ۳) که خانه‌ی (۲، ۵) آن کم است؛ ۲۱ ترومینو.

  1. def tromino_tiling(k, row, col):
  2. # A 2^k × 2^k board with the cell (row, col) missing, tiled with L-shaped trominoes. Cells show the tile number.
  3. n = 2 ** k
  4. if row >= n or col >= n:
  5. return None
  6. board = [["·"] * n for _ in range(n)]
  7. board[row][col] = "■"
  8. count = [0]
  9. tile(board, n, 0, 0, row, col, count)
  10. tiles = count[0]
  11. return tiles
  14. def tile(board, size, top, left, mr, mc, count):
  15. # (mr, mc) is the one cell of this square that is already taken.
  16. if size == 1:
  17. return
  18. half = size // 2
  19. count[0] = count[0] + 1
  20. t = count[0]
  21. quads = []
  22. cells = []
  23. for dr in [0, 1]:
  24. for dc in [0, 1]:
  25. qt = top + dr * half
  26. ql = left + dc * half
  27. if qt <= mr < qt + half and ql <= mc < ql + half:
  28. quads.append([qt, ql, mr, mc])
  29. else:
  30. # The quadrant's cell next to the centre gets a piece of tromino t.
  31. cr = top + half - 1 + dr
  32. cc = left + half - 1 + dc
  33. cells.append([cr, cc])
  34. quads.append([qt, ql, cr, cc])
  35. place(board, cells, t)
  36. for qt, ql, r, c in quads:
  37. tile(board, half, qt, ql, r, c, count)
  40. def place(board, cells, t):
  41. for r, c in cells:
  42. board[r][c] = t

ناوردا: هر مربعی که TILE روی آن صدا زده می‌شود دقیقاً یک خانه‌ی پر دارد و بقیه‌اش خالی است.

شروع اجرا

جدول هنوز خالی است.

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

k3
row2
col5

نارنجی = در همین گام عوض شد

Call stack

  1. tromino_tiling()خط 1
گام ۱ از ۱٬۴۴۰
خط سیاه = centre · خط نارنجی = گام کلیدیcentre: 0/21 · done: 0/1
    توضیح

    مسئله

    صفحه‌ای 2^k × 2^k داریم که یک خانه‌اش کم است. آیا می‌شود بقیه را با ترومینو (کاشی L شکل سه‌خانه‌ای) پوشاند؟ تعداد خانه‌ها 4^k − 1 است که بر ۳ بخش‌پذیر است، ولی این کافی نیست؛ باید راهی ساخت.

    اثبات استقرایی = الگوریتم

    • پایه: صفحه‌ی ۲ × ۲ با یک خانه‌ی کم، خودش یک ترومینو است.
    • گام: صفحه را به چهار ربع 2^(k−1) × 2^(k−1) تقسیم کن. خانه‌ی کم در یکی از آن‌هاست. یک ترومینو در وسط بگذار که یک خانه از هر کدام از سه ربع دیگر را بپوشاند. حالا هر ربع دقیقاً یک خانه‌ی پر دارد و طبق فرض استقرا کاشی‌کاری می‌شود.

    این اثبات (Golomb، ۱۹۵۴) دقیقاً یک الگوریتم تقسیم و حل است: (4^k − 1)/3 ترومینو، هر کدام در یک گام.

    ورودی

    k اندازه‌ی صفحه را تعیین می‌کند (2^k)، و row و col خانه‌ی کم را (از ۰). عدد هر خانه شماره‌ی ترومینوی آن است و ■ خانه‌ی کم.