Kỹ thuật & Thuật toán

Cách trình giải khối Rubik trực tuyến hoạt động: Từ camera đến 20 nước xoay

Đọc màu một khối Rubik thật qua webcam máy tính hoặc camera điện thoại trong điều kiện phòng thực tế — dưới ánh đèn vàng ấm, lóa sáng từ cửa sổ hay ánh sáng yếu buổi tối — rồi biến các điểm ảnh đó thành lời giải 3D khoảng 20 nước xoay đòi hỏi bốn giai đoạn thị giác máy tính và toán học tổ hợp chặt chẽ.

Góc nhìn kỹ thuật bên trong bộ quét camera, mô hình theo dõi màu sắc, bộ tìm hướng 3D và thuật toán giải hai giai đoạn của rubik.page.

Giai đoạn 1 · Thị giác máy tính

Nhận diện lưới phối cảnh tự do không cần khung ngắm cố định

Nhiều trình quét khối Rubik đời cũ buộc người dùng phải căn khối Rubik nằm khít bên trong một khung lưới 3×3 cứng nhắc vẽ giữa màn hình rồi tự bấm nút “Chụp” sáu lần. Cách làm đó vừa chậm vừa dễ sai: chỉ cần bàn tay nghiêng nhẹ là màu phông nền phía sau sẽ tràn vào ô lấy mẫu.

Trên rubik.page, bạn chỉ cần giơ từng mặt của khối Rubik ra trước camera theo bất kỳ thứ tự nào và ở bất kỳ vị trí nào trong khung hình:

  1. Trích xuất cạnh và đường viền thích ứng: Từng khung hình video được phân tích bằng OpenCV để định vị các tứ giác ứng viên của miếng dán màu cũng như biên bao ngoài của mặt khối Rubik, hoạt động tốt ngay cả trên các khối nhựa không viền (stickerless) có góc bo tròn.
  2. Khớp mạng lưới phối cảnh 3×3 (Homography): Bằng phép biến đổi phối cảnh phẳng và chấm điểm hình học, bộ dò khớp một lưới chiếu 3×3 lên mặt đang nhìn thấy (hoặc một cặp hai mặt kề nhau gặp nhau tại đường nối giữa hai mặt), đồng thời loại bỏ các lưới giả ở hậu cảnh như bàn phím, giá sách hay gạch lát tường nhờ bộ lọc đồng thuận chống nhảy lưới qua 3 khung hình.
  3. Lấy mẫu vùng lõi miếng dán màu: Khi lưới 3×3 đã khóa ổn định, bộ dò chỉ lấy mẫu phần lõi bên trong của từng ô trong 9 ô — bỏ qua viền nhựa đen và rìa phản xạ bóng gương — rồi chuyển đổi điểm ảnh sang không gian màu cảm nhận thị giác CIELAB (L*, a*, b*).
Giai đoạn 2 · Khoa học màu sắc

Hiệu chuẩn đồng thời bảng màu CIELAB trên toàn bộ 54 miếng dán màu

Thách thức khó nhất khi quét khối Rubik qua camera là màu sắc biến đổi rất mạnh theo nguồn sáng và chất liệu bề mặt khối:

  • Dưới bóng đèn sợi đốt hoặc đèn LED ánh vàng ấm trong phòng, miếng dán màu trắng ngả sang vàng kem, còn màu đỏ và màu cam dịch sát lại gần nhau nếu chỉ phân ngưỡng RGB/HSV cố định.
  • Trên các dòng speedcube bề mặt nhám mờ hoặc tông màu pastel “macaron”, xanh lá bạc hà và xanh dương nhạt có độ sáng L* rất cao và độ bão hòa thấp, dễ bị bộ phân loại đơn giản nhận nhầm thành màu trắng.
  • Trong phòng thiếu sáng, màu xanh dương đậm và xanh lá đậm giảm mạnh độ chói, dễ lẫn với viền nhựa tối màu.

Để xử lý chính xác mọi trường hợp đó, rubik.page sử dụng bộ khớp bảng màu Bayes đồng thời trong không gian CIELAB thay vì các ngưỡng cắt RGB cứng:

  • Xác nhận 3 khung hình cho mỗi mặt: Ngay khi bạn giữ yên một mặt trong ba khung hình nhất quán (~0,5 giây), chín phép đo CIELAB của mặt đó được ghi nhận và dấu tích xanh xác nhận bạn có thể xoay sang mặt tiếp theo.
  • Tiên nghiệm góc sắc độ tương đối: Các màu được đánh giá tương đối so với chính điểm trắng đo được trên khối Rubik trong mặt phẳng sắc độ (a*, b*), bảo toàn thứ tự góc tự nhiên của nhóm màu nóng (Đỏ → Cam → Vàng) và nhóm màu lạnh (Xanh lá → Xanh dương).
  • Phân bổ toàn cục 6×9: Khi các mặt mới tiếp tục được quét vào, bộ theo dõi tối ưu đồng thời cả sáu cụm màu trên toàn bộ các miếng dán màu đã quan sát, đảm bảo không màu nào vượt quá 9 miếng dán màu và tự động gán nhãn chuẩn xác lại cho các mặt quét trước đó khi mô hình ánh sáng ngày càng hội tụ.
Giai đoạn 3 · Kiểm soát camera

Khử lóa phản chiếu và tự động bù phơi sáng phần cứng

Webcam và camera điện thoại luôn tự động đo sáng dựa trên toàn bộ căn phòng. Nếu bạn ngồi ngược sáng trước cửa sổ hoặc đưa khối Rubik bóng lại gần đèn bàn, camera rất dễ làm cháy sáng các miếng dán màu vàng nhạt thành trắng tinh (L* ≥ 97) hoặc phủ bóng lóa trắng xóa lên một vài ô.

Bộ quét của chúng tôi xử lý ánh sáng gắt phối hợp trên cả trình duyệt và máy chủ:

  1. Mặt nạ cắt vùng cháy sáng: Bên trong mỗi ô miếng dán màu, những điểm ảnh bị lóa trắng do ánh sáng xiên đều bị loại bỏ trước khi tính giá trị màu CIELAB trung vị của ô đó.
  2. Đóng băng chống lóa theo thời gian: Nếu một miếng dán màu vốn đã có số đo màu ổn định bỗng nhiên vọt độ sáng (L*) và tụt độ bão hòa sắc độ trong khi phần còn lại của mặt vẫn đứng yên, bộ theo dõi nhận diện đó là vệt bóng đèn lướt qua và giữ nguyên phép đo sạch trước đó thay vì ghi đè thành màu trắng.
  3. Điều khiển phơi sáng & đèn pin phần cứng: Trên các trình duyệt và thiết bị hỗ trợ API MediaStream exposureCompensation và torch, trang web tự động hạ mức phơi sáng khi phát hiện cháy sáng, đồng thời cung cấp nút Đèn pin một chạm (kèm bù phơi sáng âm tự động để đèn LED không làm bạc màu miếng dán) khi phòng quá tối.
Giai đoạn 5 · Tìm kiếm tổ hợp

Thuật toán hai giai đoạn của Herbert Kociemba và Con số của Chúa (20)

Một khối Rubik 3×3 có 4,325 × 1019 trạng thái hợp lệ. Năm 2010, các nhà nghiên cứu đã chứng minh rằng Con số của Chúa (God's Number) theo hệ đếm nửa vòng (HTM) bằng 20: mọi trạng thái khả giải đều có thể giải xong trong không quá 20 nước xoay (trong đó mỗi nước xoay 90° hoặc 180° của một mặt đều tính là 1 nước). Tuy nhiên, duyệt vét cạn trực tiếp cây tìm kiếm rộng 1820 nhánh là điều bất khả thi trong thời gian thực.

Để tìm ra lời giải gần tối ưu từ 18–22 nước xoay chỉ trong một phần nhỏ của giây, rubik.page sử dụng Thuật toán hai giai đoạn (Two-Phase Algorithm) của Herbert Kociemba, chia bài toán tìm kiếm thành hai nhóm con toán học lồng nhau bằng thuật toán IDA* (Iterative-Deepening A*) kết hợp các bảng cắt tỉa tính sẵn:

Giai đoạn Nhóm con toán học Mục tiêu đạt được của bước tìm kiếm Kích thước không gian trạng thái
Pha 1
G0 → G1
Đủ 18 nước xoay:
⟨U, D, L, R, F, B⟩
Định hướng đúng cả 8 mảnh góc, định hướng đúng cả 12 mảnh cạnh và đưa đủ 4 mảnh cạnh tầng giữa (FR, FL, BR, BL) vào lát cắt xích đạo giữa. 37 × 211 × C(12, 4) = 2,217,093,120 trạng thái (tối đa 12 nước)
Pha 2
G1 → {I}
Chỉ xoay 180° ở mặt bên:
⟨U, D, L2, R2, F2, B2⟩
Hoán vị 8 mảnh góc, 8 mảnh cạnh U/D và 4 mảnh cạnh tầng giữa về đúng vị trí đã giải mà không làm mất định hướng đã đạt ở Pha 1. 8! × 8! × 4! ÷ 2 = 19,508,428,800 trạng thái (tối đa 18 nước)

Vì sao việc tách chuỗi G0 → G1 → {I} lại tăng tốc đột phá đến vậy? Bởi thay vì phải nhân hai không gian hàng chục tỷ trạng thái với nhau (4,3 × 1019), IDA* giải nối tiếp Pha 1 (~2,2 tỷ trạng thái) và Pha 2 (~19,5 tỷ trạng thái) thông qua các bảng tra khoảng cách tọa độ siêu gọn, tìm ra lời giải hoàn chỉnh xoay quanh mốc 20 nước gần như tức thì.

Giai đoạn 6 · Hai chế độ

Chế độ Giải nhanh so với chế độ Luyện tập 7 giai đoạn tương tác

Ngay sau khi quét xong khối Rubik trên rubik.page, bạn có thể lựa chọn giữa hai bộ máy xử lý hoàn toàn khác nhau tùy theo mục đích:

  • Giải (Bộ máy hai giai đoạn Kociemba): Tính toán lời giải ngắn khoảng 20 nước xoay nhằm đưa khối Rubik thật của bạn trở về nguyên trạng nhanh nhất có thể. Từng bước xoay được minh họa mượt mà trên khối Rubik 3D kèm mô hình thu nhỏ cố định góc nhìn và chỉ dẫn bằng lời dễ hiểu (“xoay mặt phải theo chiều kim đồng hồ”).
  • Luyện tập (Bộ máy sư phạm 7 giai đoạn từng tầng): Mô phỏng phương pháp 7 bước cho người mới bắt đầu trực tiếp ngay trên thế xáo trộn thực tế bạn vừa quét. Thay vì đi những đường tắt máy tính khó hiểu, chế độ này chia bài giải thành các giai đoạn con người dễ học (Hoa cúc, Dấu cộng trắng, Góc trắng, Tầng giữa, Dấu cộng vàng, Cạnh vàng, Vị trí góc, Xoay góc cuối), viền sáng đúng mảnh ghép và vị trí đích trên mô hình 3D, giải thích vì sao chọn công thức đó và tích hợp sẵn chế độ câu hỏi Tự kiểm tra.

Trải nghiệm cả hai chế độ Giải và Luyện tập trên khối Rubik của bạn