ការតាមស្វែងរក "លេខរបស់ព្រះ" (God's number)

ក្នុងនាមជាអ្នកលេង Rubik (Speedcuber) ម្នាក់ដែលធ្លាប់ដណ្តើមបាន កំណត់ត្រាជាតិកម្ពុជា (National Record) ផ្នែកបង្វិលដៃម្ខាង (One-Handed) ចំនួន ២ សម័យកាល ខ្ញុំតែងតែមានសំណួរមួយចាក់ឫសក្នុងចិត្តតាំងពីក្មេងថា៖

"តើគ្រាប់ Rubik ដែលមានភាពស្មុគស្មាញដល់កម្រិតនេះ អាចដោះស្រាយបានលឿនបំផុតកម្រិតណា?"

ថ្ងៃនេះ ខ្ញុំមិនត្រឹមតែមកចែករំលែកអាថ៌កំបាំងបច្ចេកទេសប៉ុណ្ណោះទេ ប៉ុន្តែខ្ញុំក៏បានសម្រេចក្តីសុបិនតូចមួយកាលពីក្មេង ដោយបានបង្កើត បណ្ណាល័យកូដ (Library) សម្រាប់ដោះស្រាយ Rubik (Cube Solver) ផ្ទាល់ខ្លួនមួយ ដើម្បីដាក់ឱ្យអ្នករាល់គ្នាអាចយកទៅប្រើប្រាស់បានផងដែរ។

🔗 តំណភ្ជាប់លេង Demo ផ្ទាល់: rubik-solver-ui.vercel.app

ផ្នែកទី ១៖ សម្រាប់អ្នកអានទូទៅ (General Talk)

១. ក្តីសុបិនពីក្មេង និង "លេខរបស់ព្រះ" (God's Number)

កាលពីខ្ញុំនៅក្មេង ខ្ញុំធ្លាប់ស្រមៃចង់បង្កើតមនុស្សយន្ត (Robot) ដែលអាចដោះស្រាយ Rubik បានដោយខ្លួនឯង។ ពេលនោះ អ្វីដែលធ្វើឱ្យខ្ញុំងឿងឆ្ងល់បំផុតនោះគឺពាក្យថា "លេខរបស់ព្រះ" (God's Number)។

តើវាគឺជាអ្វីទៅ? ប្រសិនបើអ្នកប្រើក្បួនដោះស្រាយធម្មតា អ្នកប្រហែលជាត្រូវបង្វិល Rubik ច្រើនជាង ១០០ ដង ទើបចេញរាងដើមវិញ។ ប៉ុន្តែ "លេខរបស់ព្រះ" គឺជា ចំនួនជុំបង្វិលតិចបំផុត ដែលអង្គដែលមានប្រាជ្ញាលើសលប់ (ដូចជាព្រះជាម្ចាស់) នឹងប្រើដើម្បីដោះស្រាយគ្រាប់ Rubik ទោះបីជាវាស្ថិតក្នុងស្ថានភាពដែលច្របូកច្របល់អាក្រក់បំផុតយ៉ាងណាក៏ដោយ។

ពាក្យ "God's Number" នេះត្រូវបានបង្កើតឡើងដោយលោក David Singmaster ដែលជាអ្នកគណិតវិទ្យាមួយរូប។ នៅឆ្នាំ ១៩៨០ គាត់បានធ្វើការទស្សន៍ទាយយ៉ាងជឿជាក់ថា លេខនេះប្រហែលជា ២០ ហើយការទាយរបស់គាត់គឺពិតជាត្រឹមត្រូវ!

អត្ថន័យនៃគំនិតនេះគឺ៖ មិនថាគ្រាប់ Rubik ត្រូវបានគេរាយប៉ាយដល់ទៅ ៤៣ កោដិកោដិ (43 Quintillion) ស្ថានភាពក៏ដោយ ក៏វាតែងតែមាន "ផ្លូវកាត់" ដែលខ្លីបំផុតជានិច្ច នោះគឺ ត្រឹមតែ ២០ ជុំប៉ុណ្ណោះ យ៉ាងច្រើន។

២. ដំណើរស្វែងរកក្នុងរយៈពេល ៣០ ឆ្នាំ — ប្រវត្តិសាស្ត្រពេញលេញ

តើអ្នកវិទ្យាសាស្ត្រចំណាយពេលយូរប៉ុណ្ណាទើបបញ្ជាក់ថា "២០" គឺជាចម្លើយពិតប្រាកដ? នេះគឺជាប្រវត្តិសាស្ត្រនៃការស្រាវជ្រាវ (គិតតាមការបង្វិលបែប Half-Turn Metric — HTM):

• ឆ្នាំ ១៩៨០: ទាយថាប្រហែល ~៨០ ជុំ និងរកឃើញព្រំដែនក្រោមដំបូងគេគឺ ≥១៨ ជុំ។

• ឆ្នាំ ១៩៨១: ធ្លាក់មកត្រឹម ៥២ ជុំ (បង្ហាញក្បួនដំបូងដោយ Morwen Thistlethwaite)។

• ឆ្នាំ ១៩៩០ - ១៩៩២: ធ្លាក់ពី ៤២ មក ៣៧ ជុំ (ដោយ Hans Kloosterman, Michael Reid និង Dik Winter)។

• ឆ្នាំ ១៩៩២: ធ្លាក់មក ៣២ ជុំ (Herbert Kociemba ចាប់ផ្តើមប្រើ Two-Phase Algorithm)។

• ឆ្នាំ ១៩៩៥: ធ្លាក់មក ២៩ ជុំ និងរកឃើញព្រំដែនក្រោមថ្មី ≥២០ ជុំ (Michael Reid រកឃើញស្ថានភាព Superflip)។

• ឆ្នាំ ២០០៦ - ២០០៨: ធ្លាក់ពី ២៧ មកត្រឹម ២២ ជុំ (គណនាដោយប្រើ Supercomputer ពីអ្នកវិទ្យាសាស្ត្រជាច្រើន)។

• ឆ្នាំ ២០១០ (ចម្លើយចុងក្រោយ): ២០ ជុំគត់! God's Number ត្រូវបានបញ្ជាក់ជាផ្លូវការដោយ Rokicki, Kociemba, Davidson, Dethridge ដោយមានជំនួយពីកុំព្យូទ័ររបស់ Google។

ដើម្បីបញ្ជាក់ថា គ្មានស្ថានភាពណាមួយទាមទារការបង្វិលលើសពី ២០ ជុំឡើយ ក្រុមអ្នកស្រាវជ្រាវបានខ្ចីកម្លាំងកុំព្យូទ័រមហិមារបស់ Google។ ប្រសិនបើប្រើកុំព្យូទ័រធម្មតា គេត្រូវចំណាយពេលដល់ទៅ ~៣៥ ឆ្នាំ ដើម្បីគណនាគ្រប់ករណីទាំងអស់។ លទ្ធផលនេះត្រូវបានបោះពុម្ពផ្សាយជាផ្លូវការក្នុងទស្សនាវដ្តី SIAM Journal on Discrete Mathematics នាឆ្នាំ ២០១៣។

២.ក. Superflip — ស្ថានភាព "បញ្រ្ចាស់" ដ៏ល្បីល្បាញ

អ្នកវិទ្យាសាស្ត្របានរកឃើញស្ថានភាពមួយដែល ដែលដាច់ខាតត្រូវតែប្រើ ២០ ជុំពេញ ដើម្បីដោះស្រាយ។ ស្ថានភាពនោះឈ្មោះថា "Superflip"។

ក្នុងស្ថានភាពនេះ៖ បំណែកជ្រុង (Corners) ទាំង ៨ នៅកន្លែងដើម ហើយចំណុចកណ្តាល (Centers) ទាំង ៦ ក៏ត្រូវពណ៌គ្នា ប៉ុន្តែ បំណែកគែម (Edges) ទាំង ១២ ត្រូវបានក្រឡាប់បញ្ច្រាស់ពណ៌ទាំងអស់! លោក Michael Reid បានបង្ហាញនៅឆ្នាំ ១៩៩៥ ថា ស្ថានភាពនេះក្លាយជា "ព្រំដែនក្រោម" ដ៏រឹងមាំ ដែលបញ្ជាក់ថា God's Number មិនអាចតិចជាង ២០ បានទេ។ (Algorithm សម្រាប់សាកល្បងធ្វើ Superflip: R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U)

២.ខ. God's Number គិតតាមក្បួនផ្សេងគ្នា

ការគណនាខាងលើគឺគិតតាមក្បួន HTM ដែលចាត់ទុកការបង្វិល ៩០ ដឺក្រេ និង ១៨០ ដឺក្រេ ថាជា ១ ជុំដូចគ្នា។ ប៉ុន្តែបើយើងគិតតាមក្បួន Quarter-Turn Metric (QTM) ការបង្វិល ១៨០ ដឺក្រេ នឹងត្រូវរាប់ជា ២ ជុំ។

• Half-Turn (HTM): God's Number គឺ ២០ (បញ្ជាក់ឆ្នាំ ២០១០)។ ស្ថានភាពពិបាកបំផុតគឺ Superflip និងមានករណីផ្សេងទៀតរាប់រយលាន។

• Quarter-Turn (QTM): God's Number គឺ ២៦ (បញ្ជាក់ឆ្នាំ ២០១៤)។ អ្វីដែលគួរឱ្យអស្ចារ្យគឺ មានតែ ១ ស្ថានភាពគត់ ប៉ុណ្ណោះដែលពិបាកដល់កម្រិត ២៦ ជុំ (គឺស្ថានភាព Superflip បូកជាមួយការបង្វិលចំណុចកណ្តាល ៤ ឬហៅថា Fourspot)។

២.គ. លេខរបស់ព្រះ សម្រាប់ Rubik ទំហំផ្សេងៗ

• 2×2×2: ១១ ជុំ (បញ្ជាក់រួចរាល់)

• 3×3×3: ២០ ជុំ (បញ្ជាក់រួចរាល់ ឆ្នាំ ២០១០)

• 4×4×4: ~៣២ ជុំ (មិនទាន់ដឹងច្បាស់ ដឹងត្រឹមថាយ៉ាងហោចណាស់ ៣១ ជុំ)

• 5×5×5: មិនទាន់ស្គាល់ (ការស្រាវជ្រាវកំពុងបន្ត)

៣. គណិតវិទ្យានៅពីក្រោយលេខ ៤៣ កោដិកោដិ (43 Quintillion)

ដើម្បីយល់ពីភាពស្មុគស្មាញនៃ Rubik (3×3×3) យើងត្រូវមើលពីរបៀបដែលបំណែករបស់វាអាចរៀបចំបាន៖

• បំណែកជ្រុង (8 Corners): អាចផ្លាស់ប្តូរទីតាំងបាន 8! = 40,320 បែប និងអាចបែរមុខបាន 3^7 = 2,187 ទិសដៅ។

• បំណែកគែម (12 Edges): អាចផ្លាស់ប្តូរទីតាំងបាន 12!/2 = 239,500,800 បែប (ចែក ២ ដើម្បីរក្សាតុល្យភាព Parity) និងអាចក្រឡាប់ពណ៌បាន 2^11 = 2,048 ទិសដៅ។

រូបមន្តសរុប: 8! × 3^7 × (12!/2) × 2^11 = 43,252,003,274,489,856,000 គឺប្រហែល ៤.៣ × 10^19 ស្ថានភាព ឬ ៤៣ កោដិកោដិ!

💡 ឧទាហរណ៍ងាយយល់៖ ប្រសិនបើអ្នកមានគ្រាប់ Rubik ចំនួន ៤៣ កោដិកោដិគ្រាប់ ហើយយកវាទៅក្រាលលើដី នោះអ្នកនឹងអាចគ្របដណ្តប់ផ្ទៃផែនដីទាំងមូលបានកម្រាស់ដល់ទៅ ២៧៣ ជាន់!

ស្ថិតិគួរឱ្យចាប់អារម្មណ៍៖ ទោះបីជា God's Number គឺ ២០ ក៏ពិតមែន ប៉ុន្តែស្ថានភាពភាគច្រើនមិនតម្រូវឱ្យបង្វិលដល់ ២០ ជុំនោះទេ៖

• ≤ ១៥ ជុំ: ~0.2%

• ១៦ ជុំ: ~2.6%

• ១៧ ជុំ: ~26.7%

• ១៨ ជុំ: ~67.0% (នេះជាករណីភាគច្រើនបំផុត)

• ១៩ ជុំ: ~3.4%

• ២០ ជុំ: កម្រណាស់! (ប្រហែល ១ ក្នុងចំណោម ៩ ពាន់លាន)

៤. ភាពជាក់ស្តែងនៃក្បួនដោះស្រាយតាមកុំព្យូទ័រ

ទោះបីយើងដឹងថា ២០ ជុំគឺជាផ្លូវកាត់ខ្លីបំផុត ប៉ុន្តែការបញ្ជាឱ្យកុំព្យូទ័រគិតរកផ្លូវ ២០ ជុំនេះភ្លាមៗ គឺត្រូវប្រើកម្លាំងម៉ាស៊ីនខ្លាំង និងចំណាយពេលយូរខ្លាំងណាស់។ ដើម្បីឱ្យកម្មវិធី Solver របស់ខ្ញុំអាចគិតរកចម្លើយបានក្នុងរយៈពេល តិចជាង ១ វិនាទី ខ្ញុំបានប្រើប្រាស់ក្បួនដ៏ឆ្លាតវៃមួយឈ្មោះថា Kociemba's Two-Phase Algorithm។ ក្បួននេះស្វែងរកចម្លើយដែល "កៀកនឹងព្រះបំផុត" (Near-Optimal) តែលឿនជាងគ្នារាប់ពាន់ដង។

ការប្រៀបធៀបវិធីសាស្ត្រដោះស្រាយ:

• Beginner Method (កម្រិតដំបូង): ប្រើពេល ≥ ១ នាទី (ប្រហែល 100-120 ជុំ)

• CFOP (កីឡាករល្បឿនលឿន): ប្រើពេល < ១០ វិនាទី (ប្រហែល 50-60 ជុំ)

• Optimal Solver (រក ២០ ជុំគត់): ប្រើពេលគិតជាម៉ោង (២០ ជុំគត់)

• Kociemba Two-Phase (កម្មវិធីរបស់ខ្ញុំ): ប្រើពេល < ១ វិនាទី (ស្វែងរកបានប្រហែល 20-22 ជុំ)

🔗 តំណភ្ជាប់លេង Demo ផ្ទាល់: rubik-solver-ui.vercel.app

ផ្នែកទី ២៖ អាថ៌កំបាំងបច្ចេកទេស (Technical Deep Dive)

ចំណាំ: ផ្នែកខាងក្រោមនេះ គឺជាការរៀបរាប់ស៊ីជម្រៅអំពីបច្ចេកទេសសរសេរកូដសម្រាប់ Developers។

១. របៀបដែលកុំព្យូទ័រ "មើលឃើញ" គ្រាប់ Rubik

កុំព្យូទ័រមិនស្គាល់ពណ៌ទេ វាស្គាល់តែ "លេខ"។ នៅក្នុងកូដ (Class SearchState) ខ្ញុំបានបែងចែកលក្ខណៈសម្បត្តិ Rubik ជា ២ ធំៗ៖ ទីតាំង (Permutation) និង ទិសដៅ/ការបែរមុខ (Orientation)។ ទិន្នន័យទាំងនេះត្រូវបានបំប្លែងទៅជា កូអរដោនេ (Coordinates) ដែលជាលេខសុទ្ធ៖

• Corner Orientation (0–2186): កំណត់ការមួល (Twist) ជ្រុងទាំង ៨

• Edge Orientation (0–2047): កំណត់ការក្រឡាប់ (Flip) គែមទាំង ១២

• UD Slice Position (0–494): កំណត់ទីតាំងគែមនៅស្រទាប់កណ្តាល

• Corner Permutation (0–40319): កំណត់ទីតាំងជ្រុង (8!)

• Edge Permutation (0–40319): កំណត់ទីតាំងគែម (8!)

២. ផែនទី និងត្រីវិស័យ (Precomputation & Pruning Tables)

មុននឹងចាប់ផ្តើមដោះស្រាយ មុខងារ initSolver() នឹងបង្កើត "ផែនទី" ទុកជាមុន ដែលយើងហៅថា Pruning Tables។ វានឹងប្រាប់កុំព្យូទ័រថា៖ "បើឯងស្ថិតក្នុងកូអរដោនេនេះ ឯងត្រូវបង្វិលយ៉ាងតិច X ជុំទៀតទើបដល់គោលដៅ"។ ប្រសិនបើកូដកំពុងដើរលើផ្លូវដែលចំណាយជុំលើសផែនទី វានឹងផ្តាច់ផ្លូវនោះចោលភ្លាមៗ (Pruning)។

៣. យន្តការ Two-Phase Algorithm

ក្បួននេះបែងចែកការងារជា ២ ដំណាក់កាល៖

• Phase 1 (Orientation Phase): រុញ Rubik ពីស្ថានភាព ៤៣ កោដិកោដិ ឱ្យធ្លាក់ចូលមកក្នុងក្រុមតូចមួយ (Subgroup H) ដែលមានត្រឹមតែ ~១.៩៥ ពាន់លានស្ថានភាព។

• Phase 2 (Permutation Phase): កុំព្យូទ័រនឹងបន្តដោះស្រាយដោយប្រើការបង្វិលតែ ៦ មុខប៉ុណ្ណោះ (U, D, R2, L2, F2, B2) ដើម្បីបញ្ចប់ការដោះស្រាយទាំងស្រុង។

៤. ការរុករកជម្រៅ (Iterative Deepening A* — IDA*)

កូដរបស់ខ្ញុំប្រើប្រាស់ Algorithm ឈ្មោះ IDA* ដើម្បីរុករកចម្លើយ៖

for (let depth = 1; depth <= maxDepth; depth++) {
  phase1(root, depth);
  if (found.solution !== null) break;
}

អ្វីដែលធ្វើឱ្យ IDA* លេចធ្លោ គឺវាប្រើប្រាស់ RAM ស្ទើរតែ ០, កាត់ចោលផ្លូវខុសបានលឿន និងរកឃើញចម្លើយដែលស្ទើរតែ Optimal ជានិច្ច។

៥. របៀបដំឡើង និងប្រើប្រាស់បណ្ណាល័យកូដ (Library)

៥.១. សម្រាប់គម្រោង TypeScript / Node.js

npm install rubik-solver

import { Cube, initSolver, solve, scramble } from 'rubik-solver';

// ហៅតែម្តងគត់នៅពេលបើកកម្មវិធី (~1-2s)
initSolver();

// បង្កើតគ្រាប់ Rubik ថ្មីមួយ រួចធ្វើការបង្វិលវា
const cube = new Cube().move("R U R' U' R' F R2 U' R' U' R U R' F'");

// ស្វែងរកដំណោះស្រាយ
const solution = solve(cube);
console.log(solution); // Output: "F R U R' U' F'"

// បង្កើតចលនាក្រឡុក (Scramble)
const randomScramble = scramble();
console.log(randomScramble);

៥.២. សម្រាប់គម្រោង Python (Pure-Python with NumPy)

pip install rubik-solver-py

from rubik_solver import Cube, init_solver, solve, scramble

init_solver()

cube = Cube().move("R U R' U' R' F R2 U' R' U' R U R' F'")
solution = solve(cube)
print(solution)  # Output: "F R U R' U' F'"

random_cube = Cube.random()
print(f"ដោះស្រាយចេញក្នុង ({len(solve(random_cube).split())} ជុំ): {solve(random_cube)}")

🔗 Source Codes (GitHub Links):

• 💻 TypeScript Repo: mrrtmob/rubik-solver

• 🐍 Python Repo: mrrtmob/rubik-solver-py

សេចក្តីសន្និដ្ឋាន

ពីការជា Speed Cuber ម្នាក់ដែលប្រើប្រាស់ដៃម្ខាងបំបែកកំណត់ត្រាជាតិ រហូតមកដល់ការអង្គុយសរសេរកូដដើម្បីគ្រប់គ្រងអាថ៌កំបាំងនៃ Rubik នេះ ខ្ញុំគ្រាន់តែចង់ចែករំលែក និងលើកទឹកចិត្តអ្នករាល់គ្នាថា៖

"ភាពស្មុគស្មាញនៃជីវិត ក៏មិនខុសពីគ្រាប់ Rubik ដែរ — វាតែងតែមានដំណោះស្រាយដែលខ្លីបំផុត និងល្អបំផុតជានិច្ច ប្រសិនបើយើងមិនបោះបង់ការស្វែងរក។ ហើយដូចជាអ្នកវិទ្យាសាស្ត្រដែលសុខចិត្តចំណាយពេល ៣០ ឆ្នាំដើម្បីរកឃើញ God's Number ដែរ — ភាពអត់ធ្មត់ ជួនកាលគឺជា Algorithm ដ៏ល្អបំផុតនៅក្នុងជីវិត" 🧩

📚 ប្រភពឯកសារយោង:

1. cube20.org

2. Wikipedia: Optimal solutions for Rubik's Cube

3. Rokicki et al., "The Diameter of the Rubik's Cube Group Is Twenty", SIAM Journal on Discrete Mathematics, Vol. 27, 2013.