Кіріспе
Рубик текшесінің оңтайлы шешімдері – бұл белгілі бір мағынада ең қысқа шешімдер. Шешімнің ұзындығын өлшеудің екі кең таралған тәсілі бар. Біріншісі – төрттен бір айналымның санын санау. Екіншісі – сыртқы қабаттың «бет бұрылыстары» деп аталатын бұрылуларын санау. Сыртқы қабатты екі ширек (90°) айналдыру үшін бір бағытта екі қимыл ширек айналдыру метрикасында (QTM) екі қимыл ретінде есептеледі, бірақ бет метрикасында бір айналдыру ретінде есептеледі (FTM немесе HTM «жартылай айналдыру метрикасы» немесе OBTM «сыртқы блок айналдыру метрикасы»). Рубик текшесінің кез келген жағдайын шешу үшін қажетті бет бұрылыстарының ең көп саны 20-ға тең, оны Дэвид Сингмастер әзірледі. Келесі стандартты қимылдар, олар кез келген беттің орталық кубиктерін басқа жерге жылжытпайды: L, R, F, B, U және D әріптері сол, оң, алдыңғы, артқы, жоғары және төмен жақтардың тиісінше сағат тіліне қарай төрттен бір айналуын көрсетеді. Жартылай айналыс (яғни бір бағыттағы 2 төрттен бір айналыс) 2 белгісін қосу арқылы көрсетіледі. Сағат тіліне қарсы бағытта айналыс негізгі таңбамен (′) белгіленеді. Алайда, бұл белгілер адамға бағытталғандықтан, біз оң деп сағат тіліне қарай, ал математикалық бағытта емес, қолданамыз. Стандартты емес қимылдар әдетте жоғарыда көрсетілген стандартты қимылдарға қарағанда кіші әріптермен көрсетіледі. Беттердің орталық кубтарын басқа жерлерге жылжыту: M, S және E әріптері ортаңғы қабаттың айналуын білдіреді. M («орталық» қабатының қысқаша атауы) R және L беттерінің арасындағы қабатты сағат тілімен (1/4 айналым) айналдыруды білдіреді (алдыңғы жағынан артқы жағына қарай), L бетін қараған кезде. S («Тұрған» қабатының қысқаша атауы) F және B беттерінің арасындағы қабатты сағат тілімен (1/4 айналым) бұруды білдіреді (жоғарыдан төменге қарай), F бетін қараған кезде. E («Экватор» қабатының қысқаша атауы) U және D беттерінің арасындағы қабатты сағат тілімен (1/4 айналым) (солдан оңға қарай) бұруды білдіреді, D бетінен көрініп тұрғандай. Қалыпты айналыстардағыдай, 2 жартылай айналысты білдіреді, ал prime (') сағат тіліне қарсы айналысты білдіреді. Оның орнына, кіші әріптер r, f және u R, F және U-мен сәйкесінше R, F және U-мен бірдей бағытта айналатын қабаттарды белгілеу үшін қолданылады. Бұл күткенге сай келеді. Көп қабатты кубтарда n-ші қабаттың аталатын бетінен айналуын көрсету үшін бет атауларының алдында сандар болуы мүмкін. 2R, 2F және 2U бұрылу қабаттарын R, F және U-мен сәйкесінше R, F және U-мен бірдей бағытта көрсету үшін қолданылады. Үш қабатты куб үшін осы жазуды қолдану көп қабатты кубтармен сәйкес келеді. Бүкіл кубты айналдыру: x, y және z әріптері куб айналдыруларын білдіреді. x – бұл кубты R бағытында айналдыруды білдіреді. y – бұл кубты U бағытында айналдыруды білдіреді. z F бағытында кубты айналдыруды білдіреді. Бұл куб айналдырулары алгоритмдерде жиі қолданылады, оларды тегіс және жылдам жасау үшін. Қалыпты айналыстардағыдай, 2 жартылай айналысты білдіреді, ал prime (') сағат тіліне қарсы айналысты білдіреді. Бұл кеңістіктегі айналулар әдетте кіші әріптермен бейнеленетінін ескеріңіз.
Optimal solutions for the Rubik's Cube are solutions that are the shortest in some sense. There are two common ways to measure the length of a solution. The first is to count the number of quarter turns. The second is to count the number of outer layer twists, called "face turns". A move to turn an outer layer two quarter (90°) turns in the same direction would be counted as two moves in the quarter turn metric (QTM), but as one turn in the face metric (FTM, or HTM "Half Turn Metric", or OBTM "Outer Block Turn Metric"). The maximal number of face turns needed to solve any instance of the Rubik's Cube is 20, which was developed by David Singmaster. The following are standard moves, which do not move centre cubies of any face to another location:
The letters L, R, F, B, U, and D indicate a clockwise quarter turn of the left, right, front, back, up, and down face respectively. A half turn (i. e. 2 quarter turns in the same direction) are indicated by appending a 2. A counterclockwise turn is indicated by appending a prime symbol ( ′ ). However, because these notations are human oriented, we use clockwise as positive, and not mathematically oriented, which is counterclockwise as positive. The following are non standard moves
Non standard moves are usually represented with lowercase letters in contrast to the standard moves above. Moving centre cubies of faces to other locations:
The letters M, S and E are used to denote the turning of a middle layer. M (short for "Middle" layer) represents turning the layer between the R and L faces 1 quarter turn clockwise (front to back), as seen facing the L face. S (short for "Standing" layer) represents turning the layer between the F and B faces 1 quarter turn clockwise (top to bottom), as seen facing the F face. E (short for "Equator" layer) represents turning the layer between the U and D faces 1 quarter turn clockwise (left to right), as seen from the D face. As with regular turns, a 2 signifies a half turn and a prime (') indicates a turn counterclockwise. Instead, lowercase letters r, f and u are also used to denote turning layers next to R, F and U respectively in the same direction as R, F and U. This is more consistent with expectations. In multiple layer cubes, numbers may precede face names to indicate rotation of the nth layer from the named face. 2R, 2F and 2U are then used to denote turning layers next to R, F and U respectively in the same direction as R, F and U. Using this notation for a three layer cube is more consistent with multiple layer cubes. Rotating the whole cube:
The letters x, y and z are used to signify cube rotations. x signifies rotating the cube in the R direction. y signifies the rotation of the cube in the U direction. z signifies the rotation of the cube on the F direction. These cube rotations are often used in algorithms to make them smoother and faster. As with regular turns, a 2 signifies a half turn and a prime (') indicates a turn counterclockwise. Note that these spacial rotations are usually represented with lowercase letters.
Төменгі шектер
Аргументтерді санау арқылы, кем дегенде 18 қимыл қажет болатын позициялар бар екенін дәлелдеуге болады. Мұны көрсету үшін, ең бастысы, барлық текше позицияларының санын санап шығу керек, содан кейін шешілген текшеден бастап, ең көп дегенде 17 қимылмен қол жеткізілетін позициялардың санын санау керек. Нәтижесінде, соңғы сан кішірек болады. Бұл дәлел көп жылдар бойы жақсартылмады. Сонымен қатар, бұл конструктивті емес дәлел: ол осы көптеген қимылдарды қажет ететін нақты позицияны көрсетпейді. "Суперлип" деп аталатын позицияның өте қиын екені болжанды. Рубик текшесі "суперлип" үлгісінде болады, егер әрбір бұрыштық элемент дұрыс орналасса, бірақ әрбір қыры бар элемент дұрыс бағытталмаса. 1992 жылы Дик Т. Винтер 20 беттік бұрылыспен "суперлип" шешімін тапты, ал оның минималдығын 1995 жылы Майкл Рид көрсетті, бұл текше тобының диаметрі үшін жаңа төменгі шекараны қамтамасыз етті. Сондай-ақ 1995 жылы Майкл Рид 24 тоқсан бұрылыспен "суперлип" шешімін тапты, ал оның минималдығын Джерри Брайан дәлелдеді.
Жоғарғы шектері
Алғашқы жоғарғы шектер "адам" алгоритмдеріне негізделген. Бұл алгоритмдердің әр бөлігі үшін ең нашар жағдайларды біріктіру арқылы, әдеттегі жоғарғы шек 100 шамасында екені анықталды. Мүмкін, жоғарғы шектің алғашқы нақты мәні Дэвид Сингмастер 1979 жылдың басында айтқан 277 қозғалыс болды. Ол өзінің текше шешу алгоритміне қажетті қимылдардың ең көп санын санады.
Текше тобының өзі өте үлкен болғанымен (~4.3×1019), оң косет кеңістіктері әлдеқайда кішідірек. Косет кеңістігі ең үлкені болып табылады және тек 1082565 элементтен тұрады. Бұл алгоритмге қажетті қозғалыстар саны әр қадамдағы ең үлкен процестің қосындысы болып табылады. Бастапқыда Тистлтвейт кез келген конфигурацияны ең көп дегенде 85 қозғалыспен шешуге болатынын көрсетті. 1980 жылдың қаңтарында ол өзінің стратегиясын жақсарып, ең көп дегенде 80 қозғалысқа қол жеткізді. Сол жылы ол бұл санды 63-ке, содан кейін 52-ге дейін төмендетті. Тистлтвейттің алгоритмі әртүрлі компьютерлік тілдерде іске асырылған.
Коцембаның алгоритмі
Тистлтвейттің алгоритмін 1992 жылы Герберт Коцемба жетілдірді. Ол аралық топтардың санын екіге дейін азайтты: Тистлтвейттің алгоритміне ұқсас, ол кубты топқа жеткізу үшін оң жақ косет кеңістігінде іздестіру жүргізеді. Содан кейін ол сол топ үшін оңтайлы шешімді іздеді. және топтарындағы іздеулердің екеуі де итеративті тереңдету A* (IDA*) әдісіне балама әдіспен жасалды. іздеуіне ең көп дегенде 12 қадам, ал іздеуіне ең көп дегенде 18 қадам қажет, бұл туралы 1995 жылы Майкл Рид көрсетті. Сондай-ақ, кубты топқа жеткізетін субоптималды шешімдерді жасау және -да қысқа шешімдерді іздеу арқылы әдетте әлдеқайда қысқа жалпы шешімдерге қол жеткізіледі. Бұл алгоритмді қолдану арқылы шешімдер әдетте 21 қадамнан кем болады, бірақ оның әрқашан солай болатынына дәлел жоқ. 1995 жылы Майкл Рид осы екі топты пайдаланып, кез келген позицияны ең көп дегенде 29 беттік бұрылыс немесе 42 тоқсандық бұрылыспен шешуге болатынын дәлелдеді. Бұл нәтижені 2005 жылы Сильвиу Раду 40-қа дейін жақсартты. Бірінші қарағанда, бұл алгоритм іс жүзінде тиімсіз болып көрінеді: егер 18 мүмкін қимыл (әр қимыл, оның кері қимылы және 180 градусқа бұруы) болса, онда іздеуге 1 квадриллионнан астам кубтік күйлер қалады. Тіпті IDA* сияқты эвристикалық компьютерлік алгоритмі, оны қысқартуға мүмкіндік берсе де, осы көптеген күйлерді іздеудің практикалық еместігі анық. Бұл мәселені шешу үшін Коцемба іздеу кестесін жасады, ол үшін дәл эвристиканы ұсынады. -қа жетуге қажетті нақты қадамдар саны белгілі болғанда, іздеу дерлік жеделдетіледі: әрбір 12 қадам үшін тек 18 кубтік күйді жасау және әр жолы ең төменгі эвристикалық мәні бар күйді таңдау қажет. Бұл екінші эвристика, яғни , үшін дәлдікті азайтуға және қазіргі заманғы компьютерде ақылға қонымды уақытта шешімді есептеуге мүмкіндік береді.
As with Thistlethwaite's algorithm, he would search through the right coset space to take the cube to group Next he searched the optimal solution for group The searches in and were both done with a method equivalent to iterative deepening A* (IDA*). The search in needs at most 12 moves and the search in at most 18 moves, as Michael Reid showed in 1995. By also generating suboptimal solutions that take the cube to group and looking for short solutions in , much shorter overall solutions are usually obtained. Using this algorithm solutions are typically found of fewer than 21 moves, though there is no proof that it will always do so. In 1995 Michael Reid proved that using these two groups every position can be solved in at most 29 face turns, or in 42 quarter turns. This result was improved by Silviu Radu in 2005 to 40. At first glance, this algorithm appears to be practically inefficient: if contains 18 possible moves (each move, its prime, and its 180 degree rotation), that leaves (over 1 quadrillion) cube states to be searched. Even with a heuristic based computer algorithm like IDA*, which may narrow it down considerably, searching through that many states is likely not practical. To solve this problem, Kociemba devised a lookup table that provides an exact heuristic for When the exact number of moves needed to reach is available, the search becomes virtually instantaneous: one need only generate 18 cube states for each of the 12 moves and choose the one with the lowest heuristic each time. This allows the second heuristic, that for , to be less precise and still allow for a solution to be computed in reasonable time on a modern computer.
Қосымша жақсартулар және Құдайдың санын табу
2006 жылы Сильвиу Раду әдістерін одан әрі жетілдіріп, кез келген позицияны ең көп дегенде 27 беттік бұрылыс немесе 35 тоқсандық бұрылыспен шешуге болатынын дәлелдеді. 2007 жылы Дэниел Кункл мен Джин Куперман суперкомпьютерді пайдаланып, барлық шешілмеген кубтарды 26 қадамнан аспайтын уақыт ішінде (беттік бұрылыс метрикасы бойынша) шешуге болатынын көрсетті. Миллиардтаған вариацияларды нақты шешуге тырысудың орнына, компьютер 15 752 күйдің біріне жеткізілді, олардың әрқайсысын бірнеше қосымша қадаммен шешуге болады. Барлығы 29 қадаммен шешіледі, ал көпшілігі 26 қадамда шешіледі. Бастапқыда 26 қадаммен шешілмегендері кейін нақты шешілді және олардың да 26 қадамда шешілетіні көрсетілді. Томас Рокики 2008 жылы жасаған есептеу дәлелінде барлық шешілмеген кубтарды 25 қадам немесе одан аз қадаммен шешуге болатынын хабарлады. Кейін бұл көрсеткіш 23 қадамға дейін төмендетілді. 2008 жылдың тамызында Рокики 22 қадамды дәлелдегенін мәлімдеді. Соңында, 2010 жылы Томас Рокики, Герберт Коциемба, Морли Дэвидсон және Джон Детридж компьютерлік көмекпен барлық куб позицияларын ең көп дегенде 20 беттік бұрылыспен шешуге болатынын дәлелдеді. 2014 жылы Томас Рокики мен Морли Дэвидсон кубты шешу үшін қажет тоқсандық бұрылыстардың максималды саны 26 екенін дәлелдеді.