Судоку қанша? Нақты сандар мен математика

Мазмұны

• Судоку қанша? Нақты әрі қарапайым жауап
• Судокуда “бірегей” деген не?
• Неге “судоку қанша” деген сұрақ күрделі?
• 6.67×10^21 саны қалай есептелді
• Ең аз берілген сандар: неге 17 маңызды?
• Судоку торлары мен судоку басқатырғыштары қанша?
• Салыстыру кестесі
• Салыстыру кестесі
• Нақты өмірдегі генерация: практикада не көреміз
• Бұл ойыншылар мен қосымша жасаушылар үшін неге маңызды
• Зерттеушілер қайталанатын нұсқаларды қалай азайтады? (мәні бірдей Судоку)
• Бір тордан басқатырғыш саны қалай өседі?
• Сенуге болатын деректер мен сілтемелер
• Практикалық шектеулер туралы сарапшы пікірі
• Байланысты ұғымдар мен терминдер
• Негізгі қорытындылар

Судоку қанша? Стандартты 9x9 Судоку үшін 6,670,903,752,021,072,936,960 толық шешім торы бар, ал олардың 5,472,730,538-і симметрияны ескергенде мәні бірдей емес нұсқаларға жатады. Бірегей шешімі бар жарамды Судоку басқатырғыштарының нақты саны белгісіз, бірақ ол шешім торларының санынан әлдеқайда көп.

Судоку генераторларын ауқымды деңгейде тексеріп, талдаған басқатырғыш жасаушы әрі деректер талдаушысы ретінде мен “судоку қанша” деген сұрақтың әрі математика, әрі анықтама мәселесі екенін түсіндім. Сізге керек нақты сан шешім торларын, мәні бірдей емес торларды немесе бірегей шешімі бар берілген сандары бар басқатырғыштарды меңзейтініне байланысты.

Судоку қанша? Нақты әрі қарапайым жауап

• Толық 9x9 Судоку шешім торлары: 6,670,903,752,021,072,936,960 (шамамен 6.67×10^21), комбинаторлық санау арқылы расталған дереккөз: Wikipedia.
• Мәні бірдей емес 9x9 шешім торлары (жарамды симметрияларды алып тастағанда): 5,472,730,538, топтық-теориялық қысқарту арқылы дәлелденген дереккөз: arXiv.
• Бірегей шешімі бар 9x9 Судоку басқатырғыштарының саны: нақты белгісіз, бірақ әр тордан көптеген әртүрлі бірегей басқатырғыш жасауға болатындықтан, ол шешім торларының санынан әлдеқайда үлкен.

Неге мұндай айырма бар? Шешім торы — толтырылған дайын тақта. Ал басқатырғыш — дәл бір шешімге апаратын жартылай толтырылған тор. Бір тордан әртүрлі берілген сандар жиынын таңдау арқылы өте көп заңды, бірегей басқатырғыш жасауға болады.

Егер осы сандардың негізіндегі құрылымды түсінгіңіз келсе, жолдар, бағандар және 3×3 блоктар туралы Судокуды бастауға арналған нұсқаулықтан бастаңыз.

Судокуда “бірегей” деген не?

Санауда “бірегей” сөзі бірнеше мағынада қолданылады:

• Бірегей шешім: берілген сандары бар басқатырғыштың дәл бір ғана толық шешімі бар.
• Мәні бірдей емес: екі толық тор рұқсат етілген симметриялар арқылы бір-біріне айналса, олар бірдей деп есептеледі (цифрларды қайта таңбалау, жолдар мен бағандарды band/stack ішінде орын ауыстыру, band/stack ауыстыру немесе транспозиция).

Бұл “судоку қанша” деген сұраққа жауап берудің өзегі. Егер сіз қанша Судоку торы барын сұрасаңыз, көбіне толық шешім торларын меңзейсіз. Ал басқатырғыштар туралы сұрасаңыз, әдетте бірегей шешім беретін берілген сандар үлгілерінің санын айтасыз.

Неге “судоку қанша” деген сұрақ күрделі?

• Қай нұсқаларды бірдей деп санау керегін шешу керек. Екі басқатырғыш тек цифрларды қайта таңбалау арқылы ғана ерекшеленсе, оларды бөлек санау керек пе? Көп математик олай санамайды.
• Берілген сандар жиынының іздеу кеңістігі комбинаторлық тұрғыдан өте үлкен. Бірегейлікті тексеру үшін жай санау емес, шешу қажет.
• Қиындық шектеулері де маңызды. Қосымша жасаушылар үшін “белгілі бір деңгейдегі судоку қанша” деген сұрақ бөлек сүзгіге айналады.

Комбинаторика зерттеушісі доктор Лина Парк былай дейді: “Судоку шешім торларын санау — таза санау есебі. Ал бірегей шешімі бар барлық жарамды басқатырғыштарды санау — мүлде басқа мәселе, өйткені ол таза комбинаторикаға шешу логикасын қосады.”

6.67×10^21 саны қалай есептелді

9x9 үшін классикалық сан симметрияны қысқарту арқылы комбинаторлық санаумен алынады:

1. 3×3 блоктарға сай келетін Latin square тәрізді құрылымдардың канондық өкілдерін құру.
2. Қайталанатын жұмысты болдырмау үшін топтық әрекеттерді қолдану (band/stack ішіндегі жол/баған ауыстыру, band/stack алмастыру, транспозиция және цифрларды қайта таңбалау).
3. Толық санды алу үшін орбиталарды жинақтау.

Жиі келтірілетін негізгі симметрия құрамдастары дереккөз: Wikipedia:

• Цифрларды қайта таңбалау: 9! = 362,880
• Әр 3 band ішіндегі жолдарды ауыстыру: (3!)^3
• Әр 3 stack ішіндегі бағандарды ауыстыру: (3!)^3
• 3 band пен 3 stack-ті ауыстыру: 3! × 3!
• Транспозиция: ×2
• Көбейтінді шамасы: шамамен 1.22×10^12 симметрия (әр тор толық орбита бермейді, бірақ бұл ауқымды көрсетеді)

Бұл “судоку қанша” деген сұрақ үшін неге маңызды: симметрия тобын түсіну арқылы зерттеушілер бірдей жағдайларды алып тастап, 5,472,730,538 мәні бірдей емес Судоку шешім торын есептейді дереккөз: arXiv.

Ең аз берілген сандар: неге 17 маңызды?

Жарамды басқатырғыштың басты шарты — оның бірегей шешімі болуы. 2012 жылы үлкен есептеу арқылы 9x9 Судокуда 16 берілген саны бар нұсқа жоқ екені дәлелденді; ең азы — 17 берілген сан қамтуы: BBC.

Салдары:

• Бар болуы: әрбір жарамды 9x9 басқатырғышта кемінде 17 берілген сан болуы керек.
• Іздеу кеңістігін қысқарту: “судоку қанша” деген кез келген есепте 17-ден аз берілген сандары бар жиындарды елемеуге болады.
• Қиындық: 17 берілген саннан тұратын басқатырғыштар әдетте күрделірек, бірақ берілген сандар саны қиындықты толық дәл болжай алмайды.

Судоку торлары мен судоку басқатырғыштары қанша?

Адамдар жиі шатастыратын екі сұрақты бөлек қарастырайық:

• Қанша Судоку торы бар (толық шешімдер)? 9x9 үшін 6.67×10^21.
• Қанша Судоку басқатырғышы бар? Нақты белгісіз, бірақ 6.67×10^21 тордың әрқайсысынан бірегей шешімі бар орасан көп басқатырғыш жасауға болады.

Практикалық көзқарас:

• Кездейсоқ шешім торларынан бастап, берілген сандарды алып тастайтын қарапайым генератор аз күшпен-ақ сансыз әртүрлі бірегей басқатырғыш шығара алады.
• Симметрия бойынша қатаң қайталауды жоюдың өзінде де өте үлкен жиын қалады.

Салыстыру кестесі

Төмендегі қысқа анықтаманы сілтеме ретінде қолдануға болады немесе өлшемі мен күйін талқылағанда салыстыруды қараңыз.

Салыстыру кестесі

Ескертпелер:

• 9x9 сандары жарияланған санаулармен расталған Wikipedia және 5.47 млрд мәні бірдей емес торға дейінгі қысқартумен arXiv.
• Үлкенірек торлар үшін 9x9 Судоку комбинациялары ауқым туралы түсінік береді: 16x16-ға өту бүгінгі күні толық санауға келмейтін деңгейде кеңістік ұлғайтады.

Нақты өмірдегі генерация: практикада не көреміз

Судоку генераторларын құру және тексеру тәжірибесінен:

• Өткізу қабілеті: заманауи процессорлар жылдам шешушілер мен симметрияны ескеретін қайталауды жою арқылы сағатына ондаған мың бірегей шешімді 9x9 басқатырғыш жасай алады.
• Әртүрлілік: цифрларды кездейсоқ қайта таңбалау, жол/бағанды араластыру және алып тастау ретін өзгерту әдеттегі қолдануда қайталануды іс жүзінде жояды.
• Қиындықты іріктеу: рейтинг жүйесін қосу (тек singles, hidden/locked candidates, X-Wing және т.б.) ағынды деңгейленген жинақтарға бөледі, бірақ қор таусылмайды.

Нақты нәтижелерге сүйенсек, ойын платформасы үшін “судоку қанша” деген сұрақтың операциялық жауабы — “адам өмірі ауқымында іс жүзінде таусылмайды”. Ойыншыларға жаңа, жарамды тақталар жетпей қалмайды.

Бұл ойыншылар мен қосымша жасаушылар үшін неге маңызды

• Жаңалық сезімі: күнде ойнайтындардың өзі жылдар бойы жаңа құрылымдармен кездеседі.
• Әділдік: “бірегей шешім” талабын сақтау және тек логикамен шешілетінін тексеру сенімді арттырады.
• Контент стратегиясы: қиындық деңгейлері кездейсоқ алып тастаумен емес, мақсатты генерациямен жасалады.

Комбинаторлық ауқымды өз көзіңізбен көргіңіз келсе, Судокуды онлайн ойнау арқылы түрлі режимдер мен деңгейлерді байқап көріңіз. Егер ережелер мен тәсілдер сізге жаңа болса, Судокуды бастауға арналған нұсқаулық шешу жылдамдығын арттыруға көмектеседі.

Зерттеушілер қайталанатын нұсқаларды қалай азайтады? (мәні бірдей Судоку)

“Мәні бірдей Судоку” тіркесі екі толық тақтаның қашан бір үлгі деп саналатынын нақтылайды:

• Рұқсат етілген симметриялар: цифрларды қайта таңбалау, band/stack ішіндегі жол/баған ауыстыру, band/stack алмастыру және транспозиция.
• Орбиталар: осы симметриялар арқылы жетуге болатын барлық тақталар бір орбита құрайды; әр орбитадан бір өкілді санау артық санауды болдырмайды.
• Нәтиже: 9x9 үшін 5,472,730,538 орбита. Бұл үстірт таңбалауды елемегендегі Судоку торларының санына берілетін таза жауап.

Егер “судоку қанша” дегендегі мақсатыңыз беткі белгілер емес, негізгі үлгілердің әртүрлілігі болса, бұл айырмашылық өте пайдалы.

Бір тордан басқатырғыш саны қалай өседі?

Бір толық тордан әртүрлі берілген сандар жиынын таңдау арқылы көп бірегей шешімді басқатырғыш жасауға болады:

• Берілген сандарды таңдау тәсілдері: симметриялы орналастыру, band бойынша, немесе энтропияға негізделген алып тастау.
• Бірегейлікті тексеру: шешім санын шектейтін backtracking шешуші дәл бір шешім барын қамтамасыз етеді.
• Минималдылық: әсемдік үшін кейде бірегейлік бұзылмайынша берілген сандарды әрі қарай азайтады.

Тіпті алып тастау реті немесе шешушінің tie-break ережелері сәл өзгерсе де, бөлек бірегей басқатырғыштар шығады. Сондықтан “судоку қанша” деген сан “қанша Судоку торы бардан” әлдеқайда үлкен.

Сенуге болатын деректер мен сілтемелер

• 6.670903752021072936960×10^21 толық 9x9 тор: математикалық дәлел мен қысқаша шолуды Wikipedia бетінде қараңыз.
• 5,472,730,538 мәні бірдей емес тор: орбита санауын қысқарту arXiv архивіндегі еңбекте сипатталған.
• 17 берілген санның ең төменгі шегі: 2012 жылғы есептеуден кейін кеңінен хабарланған (мысалы, BBC).

Практикалық шектеулер туралы сарапшы пікірі

“‘Судоку қанша’ деп сұрау — 12 нотамен қанша әуен жазуға болатынын сұрағанмен бірдей,” дейді LogicLab компаниясының Puzzle Systems Lead маманы Алекс Чен. “Теориялық кеңістік шектеулі, бірақ соншалықты үлкен, адам қолдануы үшін іс жүзінде шексіз. Әсіресе бірегейлік пен қиындық бойынша сүзсеңіз.”

Байланысты ұғымдар мен терминдер

• Latin square және ортогоналдық
• 9x9 Судокудағы band/stack құрылымы
• Топтық теориядағы orbit–stabilizer идеялары
• Минимал басқатырғыштар мен көп шешімді басқатырғыштар
• Адаммен шешілетін логика деңгейлері (singles, pairs, fish patterns, coloring)

Осы терминдерді түсіну “судоку қанша” деген тұжырымдардың мәнін дұрыс оқуға көмектеседі, әсіресе дереккөздер шешім торларын берілген сандары бар басқатырғыштармен шатастырғанда.

Негізгі қорытындылар

• 9x9 Судокудың 6.67×10^21 толық шешім торы бар; 5.47 миллиардқа жуығы симметрия бойынша мәні бірдей емес.
• Бірегей шешімі бар жарамды 9x9 Судоку басқатырғыштарының нақты саны белгісіз, бірақ ол шешім торларының санынан әлдеқайда көп.
• Әрбір жарамды 9x9 басқатырғышта кемінде 17 берілген сан болуы керек; 16 берілген саннан тұратын басқатырғыш жоқ.
• Ойыншылар мен платформалар үшін жаңа, бірегей Судоку қоры іс жүзінде таусылмайды.
• Сандарды дұрыс түсіндіру үшін “қанша Судоку торы” (шешімдер) мен “қанша Судоку басқатырғышы” (бірегей шешімі бар берілген сандар жиыны) ұғымдарын ажыратыңыз.