حل مکعب روبیک با پایتون و Cryptographic Attack

خب بیایین توی این روز کسل کننده یه کار جالب بکنیم؛ خواهر کوچیکم یک مکعب روبیک بهم ریخته داره و قراره شده که من حلش کنم!

روبیک حل کردن بلدم؟! معلومه که نه ?
قراره یاد بگیرم و حلش کنم؟! شاید یه روز یادش بگیرم ولی فعلا نه!

بله! یه برنامه می‌نویسیم که راه حل رو بهمون بده؛ توی قدم اول سعی می‌کنیم ایده‌‌های مختلفی که می‌تونند جواب درست داشته داشته باشند رو بررسی کنیم.

اولین چیزی که به ذهنم می‌رسه اینه که:
می‌تونیم شیوه ای که یک روبیک باز، روبیک حل میکنه رو از اینجا بخونیم و کدش کنیم؛البته که راه درست و معقولش هم همینه اما اگه حوصله خوندنش رو داشتم که یاد می‌گرفتمش و این پست ویرگول رو نمی‌نوشتم ?

ایده بعدی:
اینکه مثلا تمام جایگشت های روبیک رو پیدا کنیم و درنهایت مجموعه حرکاتی که می‌تونیم از حالت فعلی به حالت حل شده برسیم رو انتخاب کنیم؛ (درست یا غلط بودنش فعلا مهم نیست، بیایین تعداد حالاتش رو بررسی کنیم)

ویکی‌پدیا می‌گه:

اصل مکعب 3×3×3 روبیک هشت کنج و دوازده لبه دارد. !8 برای جایگشت کنج ها وجود دارد. هر وجه سه پیشامد ممکن برای آرایش دارد. گرچه تنها هفت تا (از هشت تا) می توانند به صورت مستقل آرایش یابند؛ آرایش کنج هشتم وابسته به کنج هفتم ماقبل خود است که37 حالت برای آن وجود دارد. 2/!12 روش برای آرایش لبه های کنج وجود دارد. !12 به این دلیل است که لبه ها باید در یک جایگشت زوج باشند. 11 لبه می توانند به صورت مستقل چرخش داشته باشند و همراه گردش دوازدهمین لبه که به گردش لبه های ماقبل وابسته است،211 حالت به ما می دهد.

یعنی 43,252,003,274,489,856,000 حالت مختلف داریم! ?
واسه درک بهتر بزرگ بودن این عدد اینکه: اگه برای هر جایگشت مکعب‌های روبیک با سایز استاندارد داشته باشیم و اونها رو کنار همدیگه بچینیم، میشه باهاش کره زمین رو ۲۷۵ بار فَرش کرد!

هووووووففففف!
بریم سراغ نطریه گراف؛ مکعب روبیک رو خیلی خوب می‌شه با گراف مدل کرد؛ گره‌ها حالت مکعب رو نشون می‌دند و یالها هم اتصالشون و اینکه با چه حرکتی از یک state به state دیگه می‌رسیم.

بذارین چندتا از الگوریتم‌هایی که می‌تونیم اینجا استفاده کنیم رو بررسی کنیم:

۱- جست و جوی DFS:

جست و جوی اول عمق (DFS) از ریشه شروع می‌کنه و هر مرحله همسایه‌های رأس فعلی رو به ترتیب بررسی می‌کنه؛ در صورتی که همه همسایه‌ها قبلاً دیده شده باشند، الگوریتم عقب‌گرد می‌کنه و دوباره می‌ره سراغ رأسی که از اون به رأس فعلی رسیدیم.
به عبارتی الگوریتم تا اونجا که می‌شه به عمق می‌ره و وقتی به بن‌بست برسه عقب‌گرد می‌کنه و این فرایند هم تا وقتی که همه رأس‌هایی که از ریشه قابل دسترسی اند بررسی بشند ادامه داره.

معلومه که توی مساله ما، DFS غیر خلاقانه کار می‌کنه؛ هر بار به اولین همسایه یک رأس می‌ره و در نتیجه هر دفعه به عمق بیشتری می‌ره تا به رأسی برسه که همه همسایه‌هاش بررسی شدند و آخر کار هم به اولین رأسی بر می‌گرده که همسایه‌ای داشته باشه که هنوز بررسی نشده؛

توی این مساله، DFS می‌تونه توی یک حلقه بی نهایت گیر کنه؛ اینجوری که برای هر وضعیت پنج تا همسایه داریم (حرکات L, R, U, D, F توی روبیک).
DFS هر دفعه همسایه اول گره فعلی (مثلا حرکت L) رو انتخاب می‌کنه و با این انتخاب به گره هدف نمی‌رسه؛ طبیعیه از اونجایی که فضای جست و جوی مسأله نامحدوده، این الگوریتممون هیچوقت به جواب نرسه. (البته که می‌شه اصلاحش کرد؛ مثلا با یک عمق خاص محدودش کنیم و اگه تا بیست سطح پایین رفت و به جواب نرسید، عقبگرد کنه)

۲- جست و جوی BFS:

جست و جوی اول سطح (BFS) از ریشه شروع می‌کنه (سطح ۰) و هر مرحله همسایه‌های رأس فعلی رو کامل بررسی می‌کنه (سطح ۱)؛ یعنی هر دفعه گره‌های یک سطح رو کامل بررسی می‌کنیم و بعد به سطح بعدی می‌ریم.

می‌دونیم که توی این مساله (حل روبیک) حتما یک جواب رو داریم؛ بعبارت دیگه همیشه از هر state می‌شه به حالت حل شده رسید پس BFS در نهایت یک جا تموم می‌شه و به جواب می‌رسیم.

خصوصیت بد BFS حافظه بیش از حدی هست که واسه نگهداشتن گره‌های این مساله مصرف می‌کنه (خییییلی زیاااااااد)

البته که الگوریتم‌های بهتری واسه این کار وجود دارند (که واسه من دردسرهایی داشتند). مثلا روش کورف دقیقا همون DFS عمیق کننده تکراری هست که با یک تابع هیوریستیک و پترن دیتابیس که درواقع یک lookup table خیلی خیلی بزرگ هست که قبلا محاسبه شده سعی می‌کنه مسیرهای بهتری انتخاب کنه! یعنی یک کامپیوتر دیگه (به هر روشی) واسه همه state ها Manhattan Distance رو به دست آورده و توی یک دیتابیس ذخیره کرده تا توی این الگوریتم ازش استفاده کنیم.

بعد از کلی گوگل و سرچِ بی‌ربط، ایده بامزه‌ای رو پیدا کردم:

حمله های کریپتوگرافیک (رمزگشایی):

حمله‌های کریپتوگرافیک برای دیکد کردن اطلاعات رمز شده استفاده می‌شند.
روشی که اینجا خودنمایی می‌کنه، meet-in-the-middle هست؛ خلاصه کارش اینه که:

فرض کنیم یه بلاک اطلاعاتی با دو تا کلید رمز شده باشه (که مثلا امنیت بالاتری داشته باشه)؛

P = AAA
C = ZZZ
AAA -> XXX -> ZZZ

متن اصلی AAA بوده و توی دو مرحله تبدیل شده به ZZZ. اگه کلیدها رو k1 و k2 درنظر بگیریم،‌ روش بدیهی اینه که با ۲ به توان k1 ضربدر ۲ به توان k2 حالت مختلف بروت فورس کنیمش.

روش meet-in-the-middle می‌گه نه! به جای این کار بیا و یه بار P رو برای تمام مقادیر k1 رمزنگاری کن (Encrypt) و یه بار هم C رو برای تمام مقادیر k2 رمزگشایی کن (Decrypt). محل تلاقی این دو تا می‌شه جواب؛ در واقع با ۲ به توان k1 به اضافه ۲ به توان k2 عمل مختلف تونستیم از متن رمز شده به متن اصلی برسیم.

مثل روش بالا، از حالت کامل یک روبیک شروع می‌کنیم و با الگوریتم BFS حالت های مختلفی که میشه بهشون رسید رو می‌سازیم؛ وسط این درخت کجاست؟! مگه فضای حالت نامتناهی نیست؟!
خب بذارین یه چیزی رو بگم؛ عمق این درخت رو حداکثر ۲۰ می‌ذاریم. سال ۲۰۱۰ آقای Tomas Rokicki و رفقاش کشف کردن که از هر حالت یک مکعب روبیک، میشه با کمتر از ۲۰ حرکت به حالت حل شده رسید. (عددِ الهی)

پس کافیه این درخت رو تا مثلا ۱۰ یا ۱۲ سطح بسازیم و یه جا ذخیره کنیم؛ بعد شروع کنیم و یه درخت مشابه بسازیم با این تفاوت که ریشه، حالت فعلی مکعبی هست که میخواییم حلش کنیم و اون رو هم تا حداکثر ۱۰ سطح ادامه می‌دیم. جایی که این دو تا با هم تلاقی داشته باشند (یعنی توی این درخت به گرهی برسیم که قبلا توی درخت بالایی بهش رسیده بودیم) جواب مساله هست.

خوبی قضیه اینه که پترن-دیتابیس رو خودمون ساختیم و بعد از محاسبه‌ش توی زمان کمتری می‌تونیم واسه حالت‌های مختلف، جواب رو پیدا کنیم.

خب، من واسه نوشتنش از پایتون استفاده می‌کنم.
قدم اول چیه؟! یه درخت بسازیم که از حالت اولیه شروع کنه و تمام حالات بعدی رو .... نه نه نه! قدم اول اینه که یک دونه گره رو بتونیم مدل کنیم ?

 class Node:
    __slots__ = ('state', 'solution')                                                                                                                                                                                                                                                     
    def __init__(self, state='', solution=''):                                                                                                
        self.state = state                                                                                                                    
        self.solution = solution                                                                                                              

هر گره وضعیت فعلی مکعب و حرکاتی که تا اینجا طی کرده رو ذخیره می‌کنه.

وضعیت (state) روبیک رو چجوری نشون بدیم؟! واسه سادگی کار، وضعیت رو با یه رشته از اطلاعات نشون می‌دم؛ مکعب ۶ وجه داره و هر وجه هم ۹ تا خونه.
ترتیب رشته به صورت LFRBUD هست، یعنی به ترتیب وجه سمت چپ - جلو - راست - پشت - بالا - پایین ذخیره می‌شه و برای هر وجه هم ۹ تا کاراکتر (حرف اول رنگ اون خونه) داریم.

نمونه یک مکعب حل شده:

GGGGGGGGGWWWWWWWWWBBBBBBBBBYYYYYYYYYOOOOOOOOORRRRRRRRR

قدم بعدی! جای ریشه، حالت روبیک حل شده رو می‌ذاریم و شروع می‌کنیم با BFS درخت رو تا سطح ۱۰ کامل کردن.

و البته قدم بعدتر! اینکه نتایجش رو یک جا ذخیره کنیم.
من حالتهایی رو که از درخت اول تولید می‌کنم توی ردیس و مثل یک دیکشنری ذخیره می‌کنم:

state: solution

اینجوری موقع سرچ کردن توی درخت بعدی، به هر state که برسیم اون رو به عنوان کلید به ردیس می‌دیم و اگه جوابش توی ردیس ذخیره شده باشه با فاصله زمانی خیلی خیلی کمی اون رو بهمون می‌ده (ردیس از hash table واسه این کار استفاده می‌کنه؛ مزیت اینکه state رو یک رشته از کاراکترها گرفتیم همینه که بدون دردسر هَش می‌شه و مستقیم می‌شه اون رو به ردیس داد).

# generator.py
from redis import Redis
from movements import *
from node import Node

redis_cli = Redis(db=13)
parent = Node (        
    state='GGGGGGGGGWWWWWWWWWBBBBBBBBBYYYYYYYYYOOOOOOOOORRRRRRRRR'
  )

queue = [parent]
for i in range(5**10):
    top = queue.pop(0)
   
    state = top.state
    solution = top.solution
    
    if redis_cli.exists(state) == 1:    continue

    redis_cli.set(state, solution)

    # single movements (eg. U)
    rnode = Node(right_movement(state), &quotr'&quot + solution)
    lnode = Node(left_movement(state), &quotl'&quot + solution)
    unode = Node(up_movement(state), &quotu'&quot + solution)
    dnode = Node(down_movement(state), &quotd'&quot + solution)
    fnode = Node(front_movement(state), &quotf'&quot + solution)
    
    queue.extend([rnode, lnode, unode, dnode, dnode, fnode])

صد البته که ایده بهتر این بود که حرکات اضافی حذف بشند. (مثلا با چهار تا حرکت U دوباره به همون وضعیت فعلی می‌رسیم)
یا حتی اضافه کردن حرکات دوتایی مثل U2 - L2 - F2 و ... می‌تونه نتیجه بهتری بهمون بده.

مشابه کد بالا یک BFS روی وضعیت فعلی مکعب (که قراره حل بشه) می‌زنیم با این تفاوت که دیگه داده‌ها رو توی ردیس ذخیره نمی‌کنیم، بلکه هر دفعه چک می‌کنیم وضعیت فعلی توی دیتاهایی که با فایل generator.py (کد بالا) تولید کردیم هست یا نه؛ اگه بود خروجی ردیس رو به دیتای گرهِ فعلی append و چاپش می‌کنیم:

# solver.py
from redis import Redis
from movements import *
from node import Node

redis_cli = Redis(db=13)

current_state = Node(        
    state='BBYGRBOGGRBBOYYGOWYBGGRROYBWWBWWWRRYWOOYOOGWOWGGYYRBRR'
  )

queue = [current_state]
answer = ''
for i in range(5**10):
    top = queue.pop(0)

    state = top.state
    solution = top.solution

    if redis_cli.exists(state):
        answer = solution + redis_cli.get(state).decode('utf-8')
        break

    child_movements = [
        Node(right_movement(state), solution + &quotr&quot),
        Node(left_movement(state), solution +  &quotl&quot),
        Node(up_movement(state), solution + &quotu&quot),
       Node(down_movement(state), solution + &quotd&quot),
       Node(front_movement(state), solution + &quotf&quot)
    ]
    queue.extend(child_movements)

print(answer)

حالا فقط باید وضعیت گره فعلی مقداردهی بشه و تمام!
چجوری مقدار بدیم بهش؟ برنامه یا دست؟ برنامه! یه کد کوچیک با opencv که تصویر روبیک رو از وبکم بگیره و state رو چاپ کنه (اینجا توضیحش نمی‌دم، شاید یه پست جدا درباره‌ش نوشتم?)

import cv2
from myutils import (print_rectangles, get_state_by_colors)

cap = cv2.VideoCapture(1) # read from webcam
while True:
    _, frame = cap.read()
    frame = cv2.flip(frame, 1) # flip horizontal

    print_rectangles(frame)
    
    hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
    state = get_state_by_colors(hsv)
    print(state)

    # display the resulting frame
    cv2.imshow('default',frame)

    if cv2.waitKey(1) & 0xFF == ord('q'):    break

cap.release()
cv2.destroyAllWindows()

و خروجی اولیه:

خب وضعیت فعلی‌مون اینه:

state: BBYGRBOGGRBBOYYGOWYBGGRROYBWWBWWWRRYWOOYOOGWOWGGYYRBRR 

فایل generator.py رو اجرا کردیم و یک سری دیتا توی ردیس ذخیره کردیم؛ فایل دومی (solver.py) رو با این وضعیت اجرا می‌کنیم و خروجی:

و روبیک حل شده‌مون بعد از انجام دادن حرکات بالا:

حالا می‌تونیم روبیک رو بدیم به خواهر کوچیکه و خوشحالش کنیم ?