അൽഗോരിതങ്ങൾ മനസ്സിലാക്കുന്നതിനുള്ള ഒരു പ്രിയപ്പെട്ട പ്രശ്നം പരിഗണിക്കുക, എട്ട് ക്വീൻസ് പ്രശ്നം. ക്ലാസിക് നിർവ്വചനം: "ഇടിക്കാൻ ചതുരംഗ പലക 8 രാജ്ഞികൾ, അങ്ങനെ അവരിൽ ആരും മറ്റൊരാളെ തോൽപ്പിക്കില്ല. ശരി, വിവിധ അഭിമുഖങ്ങളിൽ പ്രശ്നം വളരെ ജനപ്രിയമാണ്, വിക്കിപീഡിയ ഉടൻ തന്നെ എൻ്റെ പ്രിയപ്പെട്ട പൈത്തണിൽ ഒരു പരിഹാരം നൽകുന്നു.

ഒരു സാധാരണ വ്യക്തിയുടെ വീക്ഷണകോണിൽ നിന്നുള്ള ശരിയായ തീരുമാനമാണിത്, പക്ഷേ ഒരു ഹാക്കറുടെ വീക്ഷണകോണിൽ നിന്ന് തികച്ചും അർത്ഥശൂന്യമാണ്, എന്തുകൊണ്ടെന്ന് ഞാൻ നിങ്ങളോട് പറയും:

നമുക്ക് അൽഗോരിതം വിശകലനം ചെയ്യാം: ഒരു ക്ലാസിക് ബാക്ക്ട്രാക്കിംഗ് തിരയൽ ഉപയോഗിക്കുന്നു, പരിഹാര മേഖലയെ ഞങ്ങൾ ഒരു ഗ്രാഫിൻ്റെ രൂപത്തിൽ പ്രതിനിധീകരിക്കുന്നു, അതിൻ്റെ ഓരോ ശീർഷകവും രാജ്ഞിയുടെ സ്ഥാനമാണ്, അതിൽ അവൾ ആക്രമണത്തിനിരയാകാത്തതും ഇതിനകം സ്ഥാപിച്ചിട്ടുള്ള രാജ്ഞികളെ തോൽപ്പിക്കുന്നില്ല. ബോർഡ്, അതായത്. കൃത്യമായി എട്ട് ലംബങ്ങൾ അടങ്ങിയ എല്ലാ "ശാഖകളും" മാത്രമേ നമുക്ക് ശേഖരിക്കേണ്ടതുള്ളൂ. ഈ "ശാഖകൾ" തിരയുന്നതിനുള്ള ഒരു രീതി എന്ന നിലയിൽ, രചയിതാവ് ഞങ്ങൾക്ക് ക്ലാസിക് വീതി-ആദ്യ തിരയൽ അൽഗോരിതം വാഗ്ദാനം ചെയ്യുന്നു, അതായത്. ഗ്രാഫ് കടന്നുപോകുന്ന ക്രമം ഇതുപോലെ കാണപ്പെടും:

അൽഗോരിതം പ്രവർത്തിക്കുന്ന ഉടൻ, സാധ്യമായ എല്ലാ പരിഹാരങ്ങളും നമുക്ക് ലഭിക്കും.

അപ്പോൾ എന്താണ് പ്രശ്നം? ഞങ്ങളുടെ കാര്യത്തിൽ, ഒരു 8x8 ബോർഡിനായി, ഞങ്ങൾക്ക് 92 വ്യത്യസ്ത പരിഹാരങ്ങൾ ലഭിക്കും, എന്നാൽ യഥാർത്ഥ പ്രശ്‌നങ്ങളിൽ പലപ്പോഴും സംഭവിക്കുന്നത് പോലെ, ബോർഡിൻ്റെ വലുപ്പം ഞങ്ങൾക്ക് അറിയില്ലെന്ന് സങ്കൽപ്പിക്കുക. തായ് ഷോഗിയിലെ പോലെ ബോർഡ് 25x25 ആണെങ്കിൽ, പരിഹാരങ്ങളുടെ എണ്ണം ഇതിനകം 275,986,683,743,434 ആയിരിക്കും.

ബോർഡിൻ്റെ വലുപ്പത്തിലുള്ള പരിഹാരങ്ങളുടെ എണ്ണത്തെ ആശ്രയിക്കുന്നത് കാണിക്കുന്ന പട്ടിക:

ഇത് നമ്മുടെ സ്ക്രിപ്റ്റിന് എന്താണ് അർത്ഥമാക്കുന്നത്? അവൻ വളരെ നീണ്ട തിരയലിലേക്ക് പോകുമെന്നതും എല്ലാ തീരുമാനങ്ങളും മനസ്സിൽ സൂക്ഷിക്കേണ്ടതിനാൽ, വെറും 15 മിനിറ്റിനുള്ളിൽ പൈത്തൺ 300 മെഗാബൈറ്റ് മെമ്മറി നശിപ്പിക്കും. ശക്തമായ പ്രോസസറും വലിയ അളവിലുള്ള റാമും ഉള്ള ആർക്കും ഈ പ്രക്രിയ പൂർത്തിയായിട്ടുണ്ടോ എന്ന് പരിശോധിക്കാൻ കഴിയും...

അത്തരമൊരു പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾക്ക് ആവശ്യമായത് ഗ്രാഫിൽ സഞ്ചരിക്കുന്നതിനുള്ള ശരിയായ അൽഗോരിതം തിരഞ്ഞെടുക്കുക എന്നതാണ്, അത് ഞങ്ങളുടെ കാര്യത്തിൽ ഒരു സാധാരണ ആഴത്തിലുള്ള ആദ്യ തിരയലായിരിക്കും, തുടർന്ന് ഗ്രാഫ് ഈ ക്രമത്തിൽ സഞ്ചരിക്കും:

കോഡ് വളരെ ലളിതമായിരിക്കും, കൂടാതെ 15 മിനിറ്റിനു ശേഷവും സ്ക്രിപ്റ്റ് സമാരംഭിച്ചതിന് ശേഷമുള്ള ഒരു സെക്കൻഡിൻ്റെ അതേ അളവിലുള്ള മെമ്മറി ഉപയോഗിക്കും. പൈത്തണിൽ ഇത് നടപ്പിലാക്കുന്നത് ഇങ്ങനെയാണ്:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: n_row in range (വീതി): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): col in range(len(sol)): if (sol == new_row or abs(col - new_col) == abs(sol - new_row)): 0 റിട്ടേൺ 1 എങ്കിൽ __name__ == "__main__": n എന്ന ശ്രേണിയിലെ (8): rc_queens(1, 8, [n])
പി.എസ്. ഇത് പ്രശ്നത്തെക്കുറിച്ചുള്ള ഒരു ഹാക്കറുടെ വീക്ഷണം മാത്രമാണ്, ഒരുപക്ഷേ ആർക്കെങ്കിലും "സൈദ്ധാന്തിക കമ്പ്യൂട്ടർ സയൻസ്" കാഴ്ച നൽകാൻ കഴിയുമോ?

"8 രാജ്ഞികൾ"- ലോജിക്കൽ ചിന്തയുടെ വികസനത്തിന് ഒരു മികച്ച പസിൽ ടാസ്ക്. ഈ ഓൺലൈൻ ഫ്ലാഷ് ഗെയിം, 1848-ൽ ചെസ്സ് കളിക്കാരനായ മാക്സ് ബാസൽ കണ്ടുപിടിച്ച, പ്രശസ്തമായ ചെസ്സ് പ്രശ്നത്തിൻ്റെ സവിശേഷമായ ആധുനിക രൂപീകരണമാണ്.

ചെസ്സ് ബോർഡിലെ ഏറ്റവും ജനപ്രിയമായ ഈ ഗണിത ഗെയിമിനെക്കുറിച്ച് ചെസ്സ് പ്രേമികൾ കേട്ടിരിക്കാം. ഈ പ്രശ്നത്തിൽ 8 രാജ്ഞികളെ എങ്ങനെ ക്രമീകരിക്കാം എന്ന ചോദ്യത്തിന് ഉത്തരം കണ്ടെത്തുന്നത് അവരുടെ വികസനം ആഗ്രഹിക്കുന്ന എല്ലാവർക്കും ഉപയോഗപ്രദമാകും. ബൗദ്ധിക കഴിവുകൾ, നിലവാരമില്ലാത്ത പ്രശ്നങ്ങൾക്ക് പരിഹാരം കണ്ടെത്തുക, ഉത്തരം തേടിയുള്ള നീക്കങ്ങളിലൂടെ ചിന്തിക്കുക.

നിയമങ്ങൾ. 8 രാജ്ഞിമാരുടെ പ്രശ്‌നത്തിന് 8 കഷണങ്ങൾ - രാജ്ഞികൾ, (അല്ലെങ്കിൽ രാജ്ഞികൾ, നിങ്ങൾ ഇഷ്ടപ്പെടുന്നെങ്കിൽ) ഒരു സാധാരണ ചെസ്സ്ബോർഡിൽ (64 ചതുരങ്ങൾ, 8x8) സ്ഥാപിക്കുക എന്നതാണ് ഏക വ്യവസ്ഥ.

ഡി ആർടാഗ്നനുമായുള്ള ഒരു ചെസ്സ് ഗെയിമിനിടെ റിച്ചെലിയു പുറത്തിറക്കിയ ഡുമസിൻ്റെ "ദ ത്രീ മസ്കറ്റിയേഴ്സ്" എന്ന വാചകം ഞാൻ ഓർക്കുന്നു: "ഇതാണ് രാജ്ഞി, അവൾ ഇഷ്ടമുള്ളതുപോലെ നീങ്ങുന്നു." ഈ ഉദ്ധരണി, ഒരു പ്രത്യേക സാഹചര്യത്തിൽ അവ്യക്തമാണെങ്കിലും, ചെസ്സ് കളിയുടെ നിയമങ്ങൾ പരിചയമില്ലാത്തവർക്കുള്ളതാണ്. രാജ്ഞി ഏത് ചതുരത്തിലേക്കും ലംബമായും തിരശ്ചീനമായും ഡയഗണലായും ഏത് അകലത്തിലും നീങ്ങുന്നുവെന്ന് നമുക്ക് വ്യക്തമാക്കാം.

യഥാർത്ഥ പരിഹാരങ്ങളുടെ ആകെ എണ്ണം 12 ആണ്. സാധ്യമായ (സമമിതി പ്രവർത്തനത്തിൻ്റെ പ്രയോഗം കണക്കിലെടുത്ത്) ഓപ്ഷനുകളുടെ ആകെ എണ്ണം 92 ആണ്. 1850-ൽ ഫ്രാൻസ് നാക്ക് ആണ് ഈ പ്രശ്നത്തിനുള്ള ഉത്തരം ആദ്യമായി പ്രസിദ്ധീകരിച്ചത്. അതിനുശേഷം, പല ശാസ്ത്രജ്ഞരും ഈ പ്രശ്നം പരിഹരിക്കുകയും ഗവേഷണം ചെയ്യുകയും ചെയ്തു സ്വന്തം ഓപ്ഷനുകൾപരിഹാരങ്ങൾ. അങ്ങനെ, പ്രശസ്ത ജർമ്മൻ ഗണിതശാസ്ത്രജ്ഞനും മെക്കാനിക്കും ഭൗതികശാസ്ത്രജ്ഞനുമായ കാൾ ഗൗസ് ഈ പസിൽ വളരെ ഇഷ്ടപ്പെട്ടു, സാധ്യമായ ക്രമീകരണത്തിനായി 72 ഓപ്ഷനുകൾ കണ്ടെത്തി. അവൻ ഒരു ഉത്തരം കണ്ടെത്തുന്ന പ്രക്രിയയെ ക്രിയാത്മകമായി സമീപിച്ചു - രസകരമായ ഒരു സാങ്കേതികത ഉപയോഗിച്ച് 8 രാജ്ഞിമാരുടെ വ്യത്യസ്ത കോമ്പിനേഷനുകൾ നേടിയെടുത്തു... ബോർഡ് യഥാക്രമം 90, 180, 270 ഡിഗ്രി കറക്കി. ഇത് ഈ പസിലിന് നിസ്സാരമല്ലാത്ത ഒരു പരിഹാരമാണ്.

ചുമതല വളരെ സങ്കീർണ്ണമാണ്, പക്ഷേ രാജ്ഞികളെ എങ്ങനെ ശരിയായി സ്ഥാപിക്കാം എന്നതിനെക്കുറിച്ചുള്ള ഒരു ഓപ്ഷനെങ്കിലും വളരെ വേഗത്തിൽ കണ്ടെത്താനാകും, അതിനെ സ്പഷ്ടമെന്ന് വിളിക്കുന്നു. രാജ്ഞിമാരുടെ ഇനിപ്പറയുന്ന ക്രമീകരണം വഴിയാണ് ഏറ്റവും ജനപ്രിയമായ ശരിയായ സ്ഥാനം കൈവരിക്കുന്നത്: a2, b4, c6, d8, e3, f1, g7, h5. ഈ ക്രമീകരണത്തിൻ്റെ ഡയഗ്രം ആദ്യ ചിത്രത്തിൽ കാണിച്ചിരിക്കുന്നു, ചെസ്സ് ബോർഡ് കറക്കിയാണ് രാജ്ഞികളെ സ്ഥാപിക്കാനുള്ള ശേഷിക്കുന്ന മൂന്ന് വഴികൾ.

മറ്റ് കോമ്പിനേഷനുകൾ സ്വയം കണ്ടെത്താൻ ശ്രമിക്കുക. നല്ലതുവരട്ടെ!

പരിശീലിപ്പിക്കാവുന്ന കഴിവുകൾ

ഒരു പ്രശ്നത്തിനുള്ള ഉത്തരം തിരയുമ്പോൾ, ഇനിപ്പറയുന്ന കഴിവുകൾ പരിശീലിപ്പിക്കപ്പെടുന്നു:

• - ബൗദ്ധിക പ്രശ്നങ്ങൾക്ക് നിലവാരമില്ലാത്ത പരിഹാരങ്ങൾ കണ്ടെത്താനുള്ള കഴിവ്, കണ്ടുപിടിച്ച അൽഗോരിതത്തിൻ്റെ അടിസ്ഥാനത്തിൽ പ്രവർത്തിക്കാതിരിക്കുക, ഉത്തരം തേടൽ;
• - മാനസിക പ്രവർത്തനത്തിൻ്റെ തരവും ധാരണയുടെ തിരഞ്ഞെടുത്ത ദിശയും, അതില്ലാതെ ഒരു വസ്തുവിലെ ഏകാഗ്രത അസാധ്യമാണ്;
• ലോജിക്കൽ ചിന്ത - തരം ചിന്താ പ്രക്രിയ, ഇതിൽ ആശയങ്ങളുടെ പ്രയോഗത്തിലൂടെയും യുക്തിസഹമായ നിർമ്മാണങ്ങളിലൂടെയും അറിവ് നേടുന്നു.

നിങ്ങൾക്ക് സമാനമായ കടങ്കഥകളും ഗെയിമുകളും പസിലുകളും ടെസ്റ്റുകളും ഇഷ്ടമാണോ? കൂടുതൽ കാര്യക്ഷമമായി വികസിപ്പിക്കുന്നതിന് സൈറ്റിലെ എല്ലാ സംവേദനാത്മക മെറ്റീരിയലുകളിലേക്കും ആക്‌സസ് നേടുക.

അധ്യായം 8. എട്ട് രാജ്ഞിമാരുടെ പ്രശ്നം

നൈറ്റ് മൂവ് പ്രോബ്ലം പോലെ എയ്റ്റ് ക്വീൻസ് പ്രോബ്ലം ചെസ്സ് ബോർഡിലെ ഏറ്റവും പ്രശസ്തമായ ഗണിതശാസ്ത്ര പ്രശ്നങ്ങളിലൊന്നാണ്. നൈറ്റ് പ്രശ്നം ലിയോൺഹാർഡ് യൂലർ പഠിച്ചെങ്കിൽ, രാജ്ഞി പ്രശ്നം മറ്റൊരു മികച്ച ഗണിതശാസ്ത്രജ്ഞൻ്റെ ശ്രദ്ധ ആകർഷിച്ചു - കാൾ ഗൗസ്.

പരസ്പരം ഭീഷണിപ്പെടുത്താതിരിക്കാൻ എട്ട് രാജ്ഞികളെ ഒരു ചെസ്സ് ബോർഡിൽ എത്ര വിധത്തിൽ സ്ഥാപിക്കാം, അതായത് രണ്ടെണ്ണം ഒരേ ലംബമോ തിരശ്ചീനമോ ഡയഗണലോ അല്ല?

പ്രശ്നത്തിൻ്റെ വ്യവസ്ഥകൾ തൃപ്തിപ്പെടുത്തുന്ന രാജ്ഞികളുടെ ഒന്നോ അല്ലെങ്കിൽ മറ്റൊരു ക്രമീകരണം കണ്ടെത്തുന്നത് അത്ര ബുദ്ധിമുട്ടുള്ള കാര്യമല്ല (നാല് പരിഹാരങ്ങൾ ചിത്രം 43 ൽ കാണിച്ചിരിക്കുന്നു). നിലവിലുള്ള ക്രമീകരണങ്ങളുടെ ആകെ എണ്ണം കണക്കാക്കുന്നത് വളരെ ബുദ്ധിമുട്ടാണ്; വാസ്തവത്തിൽ, ഇത് എട്ട് രാജ്ഞിമാരുടെ പ്രശ്നമാണ്. റൂക്കുകളുടെ കാര്യത്തിലെന്നപോലെ, പരസ്പരം ആക്രമിക്കാത്ത എട്ടിൽ കൂടുതൽ രാജ്ഞികളെ ചെസ്സ്ബോർഡിൽ സ്ഥാപിക്കുന്നത് അസാധ്യമാണെന്ന് വ്യക്തമാണ്. അതനുസരിച്ച്, ഒരു n×n ബോർഡിൽ ആവശ്യമായ രീതിയിൽ n രാജ്ഞികളേക്കാൾ കൂടുതൽ സ്ഥാപിക്കുന്നത് അസാധ്യമാണ് (ഇൻ പൊതുവായ കാഴ്ചപ്രശ്നം താഴെ ചർച്ച ചെയ്യും).

അരി. 43. എട്ട് രാജ്ഞികൾ ചെസ്സ് ബോർഡിൽ പരസ്പരം ഭീഷണിപ്പെടുത്തുന്നില്ല

എട്ട് രാജ്ഞിമാരുടെ പ്രശ്‌നവും അതിൻ്റെ പരിഹാരവും ഗൗസിൽ തന്നെയാണെന്ന് പല എഴുത്തുകാരും തെറ്റായി പറയുന്നത് കൗതുകകരമാണ്. വാസ്‌തവത്തിൽ, 1848-ൽ ഇത് ആദ്യമായി രൂപപ്പെടുത്തിയത് ജർമ്മൻ ചെസ്സ് കളിക്കാരനായ എം. ബെസെൽ ആയിരുന്നു. ഡോ. എഫ്. നൗക്ക് (ജനനം മുതൽ അന്ധൻ) 60 പരിഹാരങ്ങൾ കണ്ടെത്തുകയും അവ 1850 ജൂൺ 1 ലെ "ഇല്ലസ്ട്രിയേർട്ടെ സെയ്തുങ്" എന്ന പത്രത്തിൽ പ്രസിദ്ധീകരിക്കുകയും ചെയ്തു. ഇതിനുശേഷം മാത്രമാണ് ഗൗസ് ഈ പ്രശ്നത്തിൽ താൽപ്പര്യം പ്രകടിപ്പിക്കുകയും 72 പരിഹാരങ്ങൾ കണ്ടെത്തുകയും ചെയ്തത്, അദ്ദേഹം ഒരു കത്തിൽ റിപ്പോർട്ട് ചെയ്തു. അദ്ദേഹത്തിൻ്റെ സുഹൃത്ത് ജ്യോതിശാസ്ത്രജ്ഞനായ ഷൂമാക്കർ 1850 സെപ്തംബർ 2-നാണ്. 92 സ്ഥാനങ്ങൾ അടങ്ങിയ മുഴുവൻ തീരുമാനങ്ങളും അതേ എഫ്. സയൻസസിന് ലഭിച്ചു (1850 സെപ്റ്റംബർ 21-ലെ പരാമർശിച്ച പത്രത്തിൽ അദ്ദേഹം അവ ഉദ്ധരിച്ചു). ഗണിതശാസ്ത്ര വിനോദത്തിൻ്റെ പ്രശസ്ത ജർമ്മൻ ഗവേഷകനായ ഡബ്ല്യു ആരെൻസ് ആണ് ഈ കാലഗണന സ്ഥാപിച്ചത്, അദ്ദേഹം തൻ്റെ പുസ്തകങ്ങളിൽ പരിഗണനയിലുള്ള പ്രശ്നത്തിന് ധാരാളം ഇടം നൽകി.

92 പരിഹാരങ്ങൾ എല്ലാ സാധ്യതകളെയും തളർത്തുന്നു എന്നതിൻ്റെ തെളിവ് 1874-ൽ ഇംഗ്ലീഷ് ഗണിതശാസ്ത്രജ്ഞനായ ഡി. ഗ്ലാഷർ (ഡിറ്റർമിനൻ്റുകളുടെ സിദ്ധാന്തം ഉപയോഗിച്ച്) മാത്രമാണ് ലഭിച്ചത്.

തത്വത്തിൽ, സാധ്യമായ എല്ലാ വഴികളിലും എട്ട് രാജ്ഞിമാരെ ബോർഡിൽ സ്ഥാപിക്കുന്നതിലൂടെ, ഞങ്ങൾക്ക് അനുയോജ്യമായ എല്ലാ ക്രമീകരണങ്ങളും ഞങ്ങൾ ഒടുവിൽ കണ്ടെത്തും. എന്നിരുന്നാലും, ഈ പാത വളരെ ദൈർഘ്യമേറിയതും വിരസവുമാണ്. അനുബന്ധ റൂക്ക് പ്രശ്നത്തിനുള്ള പരിഹാരങ്ങളിലേക്ക് മാത്രം നമുക്ക് സ്വയം പരിമിതപ്പെടുത്താനും അവയിൽ ഒരു ജോടി റൂക്കുകളും ഒരേ ഡയഗണലിൽ ഇല്ലാത്തവ തിരഞ്ഞെടുക്കാനും കഴിയും. എന്നാൽ ഈ സാഹചര്യത്തിൽ പോലും, തിരയൽ വളരെ വലുതാണ് (നമുക്കറിയാവുന്നതുപോലെ, 40,000-ത്തിലധികം ശ്രമങ്ങൾ ആവശ്യമാണ്). അതിനാൽ, ഒരു പ്രശ്നം "മാനുവലായി" പരിഹരിക്കുമ്പോൾ (കഴിഞ്ഞ നൂറ്റാണ്ടിൽ ഇത് കൃത്യമായി ചെയ്തു), ക്രമീകരണങ്ങളുടെ നിർബന്ധിത കണക്കെടുപ്പ് നന്നായി ചിന്തിക്കണം. രാജ്ഞികളുടെ ആവശ്യമുള്ള ക്രമീകരണത്തിനായി (പെർമെൻ്റിയർ, ലാ നോ, ഗുണ്ടർ, ഗ്ലാഷർ, ലാക്വിയർ മുതലായവയുടെ രീതികൾ) കൂടുതലോ കുറവോ ന്യായമായ തിരയൽ സംഘടിപ്പിക്കുന്നതിന് അറിയപ്പെടുന്ന നിരവധി മാർഗങ്ങളുണ്ട്. ഈ രീതികൾ നിരവധി സാഹിത്യങ്ങളിൽ വിവരിച്ചിരിക്കുന്നു വിനോദ ഗണിതശാസ്ത്രം(കൂടുതലും കഴിഞ്ഞ നൂറ്റാണ്ടിലും ഇതിൻ്റെ തുടക്കത്തിലും). നമ്മുടെ കമ്പ്യൂട്ടറുകളുടെ യുഗത്തിൽ, ഇത്തരത്തിലുള്ള ഒരു പ്രശ്‌നത്തിന് ഇത്രയധികം താൽപ്പര്യം ഉണർത്താൻ കഴിഞ്ഞില്ല. എല്ലാത്തിനുമുപരി, ഒരു ലളിതമായ കമ്പ്യൂട്ടർ പ്രോഗ്രാം സൃഷ്ടിക്കാൻ ഇത് മതിയാകും - മെഷീനിൽ അവതരിപ്പിച്ചതിന് ശേഷം കുറച്ച് മിനിറ്റിനുള്ളിൽ, ആവശ്യമായ എല്ലാ 92 സ്ഥാനങ്ങളും അച്ചടിക്കും.

രാജ്ഞി പ്രശ്‌നത്തിനുള്ള ഓരോ പരിഹാരത്തിൽ നിന്നും, ബോർഡിനെ 90, 180, 270 ° ഘടികാരദിശയിൽ ഭ്രമണം ചെയ്യുന്നതിലൂടെ മറ്റ് നിരവധി കാര്യങ്ങൾ ലഭിക്കും (360 ° റൊട്ടേഷൻ ആരംഭ സ്ഥാനത്തേക്ക് മടങ്ങുന്നു). രാജ്ഞികളുടെ ഈ ക്രമീകരണത്തിൽ നിന്ന്, ചിത്രത്തിലെ ഡോട്ട് ഇട്ട ലൈനുകളിലൊന്നുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ ബോർഡ് മിറർ ചെയ്യുന്നതിലൂടെയും പുതിയൊരെണ്ണം ലഭിക്കും. 43 (ഒന്നാം സ്ഥാനം). ഉദാഹരണത്തിന്, ഈ ചിത്രത്തിലെ ആദ്യ ക്രമീകരണത്തിൽ നിന്ന്, ബോർഡ് 90 ° തിരിക്കുമ്പോൾ, നമുക്ക് മൂന്നാമത്തേത് ലഭിക്കും, രാജാവിനെയും രാജ്ഞികളെയും വേർതിരിക്കുന്ന രേഖയുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ, നമുക്ക് നാലാമത്തേത് ലഭിക്കും. മറ്റ് ഭ്രമണങ്ങളും പ്രതിഫലനങ്ങളും ഉപയോഗിച്ച്, അഞ്ച് പരിഹാരങ്ങൾ കൂടി ലഭിക്കും.

അതിനാൽ, ബോർഡ് തിരിക്കുകയും പ്രതിഫലിപ്പിക്കുകയും ചെയ്യുമ്പോൾ, രാജ്ഞികളുടെ ഒരു ക്രമീകരണത്തിൽ നിന്ന്, പൊതുവായി പറഞ്ഞാൽ, ഏഴ് പുതിയവ ലഭിക്കും. ഒരു n×n ബോർഡിൽ (n > 1 ന്) പരസ്പരം ഭീഷണിപ്പെടുത്താത്ത n രാജ്ഞിമാരുടെ ഏത് ക്രമീകരണത്തിനും പൊതുവായ സാഹചര്യത്തിൽ, മൂന്ന് സാഹചര്യങ്ങൾ മാത്രമേ സാധ്യമാകൂ എന്ന് തെളിയിക്കപ്പെട്ടിട്ടുണ്ട്: a) ബോർഡിൻ്റെ ഒരു പ്രതിഫലനം കൊണ്ട് പുതിയത് ക്രമീകരണം ലഭിക്കുന്നു, ഭ്രമണങ്ങളും മറ്റ് പ്രതിഫലനങ്ങളും ഒന്നും നൽകുന്നില്ല; ബി) ബോർഡ് 90 ഡിഗ്രി കൊണ്ട് തിരിക്കുന്നതിലൂടെ ഒരു പുതിയ പരിഹാരം ലഭിക്കും, കൂടാതെ പ്രതിഫലനങ്ങൾ രണ്ട് ക്രമീകരണങ്ങൾ കൂടി നൽകുന്നു; c) ബോർഡിൻ്റെ മൂന്ന് ഭ്രമണങ്ങളും നാല് പ്രതിഫലനങ്ങളും എട്ട് പൊരുത്തമില്ലാത്ത രൂപങ്ങളിലേക്ക് നയിക്കുന്നു (ഒറിജിനൽ ഉൾപ്പെടെ).

എ) യഥാർത്ഥ പരിഹാരത്തെ ഇരട്ട സമമിതി എന്ന് വിളിക്കുന്നു, ബി) - സമമിതി, കൂടാതെ സി) - ലളിതമാണ്. ഒരു സാധാരണ ബോർഡിന്, എല്ലാ പരിഹാരങ്ങളും ലളിതമോ സമമിതിയോ ആണ്, കൂടാതെ ഇരട്ട സമമിതി പരിഹാരങ്ങളൊന്നുമില്ല. ഓരോ ക്ലാസിലെയും പരിഹാരങ്ങളുടെ ബീജഗണിത വ്യാഖ്യാനം ഒകുനെവിൽ കാണാം.

എട്ട് രാജ്ഞിമാരുടെ ഒരു കൂട്ടം (സെറ്റ്) ക്രമീകരണത്തെ അടിസ്ഥാന എന്ന് വിളിക്കുന്നു, ഒന്നാമതായി, ബോർഡിൻ്റെ ഭ്രമണങ്ങളിലും പ്രതിഫലനങ്ങളിലും അവ പരസ്പരം രൂപാന്തരപ്പെടുന്നില്ലെങ്കിൽ, രണ്ടാമതായി, ഈ പരിവർത്തനങ്ങൾ ഉപയോഗിച്ച് ഏതെങ്കിലും അടിസ്ഥാന ക്രമീകരണത്തിൽ നിന്ന് മറ്റേതെങ്കിലും ക്രമീകരണം ലഭിക്കും. പ്രശ്നത്തിനുള്ള അടിസ്ഥാന പരിഹാരങ്ങളുടെ ഓരോ സെറ്റിലും കൃത്യമായി 12 സ്ഥാനങ്ങൾ (എട്ട് രാജ്ഞിമാരുടെ ക്രമീകരണങ്ങൾ) അടങ്ങിയിരിക്കുന്നുവെന്ന് അറിയാം. ഈ സെറ്റുകളിൽ ഒന്ന് ഇതാ:

ബാക്കിയുള്ള 80 സ്ഥാനങ്ങൾ ഈ പന്ത്രണ്ടിൽ നിന്ന് ബോർഡിൻ്റെ ഭ്രമണങ്ങളുടെയും പ്രതിഫലനങ്ങളുടെയും ഫലമായി ലഭിക്കുന്നു. ആദ്യത്തെ 11 ക്രമീകരണങ്ങൾ ലളിതമാണ്, അവസാനത്തേത് മാത്രം സമമിതിയാണ്. അങ്ങനെ, പരസ്പരം ഭീഷണിപ്പെടുത്താത്ത എട്ട് രാജ്ഞിമാരുടെ 11×8 + 1×4 = 92 ക്രമീകരണങ്ങൾ ബോർഡിലുണ്ട്.

പ്രധാന ക്രമീകരണങ്ങൾ കണക്കിലെടുക്കുമ്പോൾ, അവയുടെ ചില രസകരമായ സവിശേഷതകൾ നിങ്ങൾക്ക് കണ്ടെത്താനാകും. ഉദാഹരണത്തിന്, അവസാനത്തെ ക്രമീകരണത്തിൻ്റെ ബാഹ്യ സമമിതി ശ്രദ്ധിക്കുന്നത് എളുപ്പമാണ് (ചിത്രം 43 ലെ രണ്ടാം സ്ഥാനം). ഇത്തരത്തിലുള്ള ഒരേയൊരു അടിസ്ഥാന പരിഹാരം, രാജ്ഞികളില്ലാത്ത ബോർഡിൻ്റെ മധ്യഭാഗം (4x4 ചതുരം) മാത്രമേ ഉള്ളൂ എന്നതും സവിശേഷതയാണ്. അതിൻ്റെ മറ്റൊരു സ്വത്ത്, രാജ്ഞികൾ a1 - h8 എന്ന ബോർഡിൻ്റെ പ്രധാന ഡയഗണൽ ഉൾക്കൊള്ളുന്നില്ല എന്നതാണ് (ആദ്യത്തെ പ്രധാന പരിഹാരത്തിനും ഈ സ്വത്ത് ഉണ്ട്).

ചിത്രത്തിലെ ആദ്യ ക്രമീകരണം. 43 കൗതുകകരമാണ്, കാരണം ഇവിടെ മൂന്ന് രാജ്ഞികളൊന്നും വയലുകളുടെ കേന്ദ്രങ്ങളിലൂടെ വരച്ച ഒരേ നേർരേഖയിൽ നിൽക്കുന്നില്ല (ഇതിനർത്ഥം ബോർഡിൻ്റെ ലംബങ്ങളും തിരശ്ചീനങ്ങളും ഡയഗണലുകളും മാത്രമല്ല * എന്നാൽ മറ്റ് ചെരിവിൻ്റെ കോണുകളുള്ള നേർരേഖകളും).

പ്രശ്നത്തിനുള്ള ഏത് പരിഹാരവും ഒരു സെറ്റായി എഴുതാം (t 1, t 2, ... t 8), ഇത് 1, 2, ..., 8 എന്ന സംഖ്യകളുടെ ക്രമമാറ്റമാണ്. ഇവിടെ ti എന്നത് തിരശ്ചീന സംഖ്യയാണ്. i-th ലംബത്തിൻ്റെ രാജ്ഞി നിൽക്കുന്ന വരി. രണ്ട് രാജ്ഞികളും ഒരേ തിരശ്ചീന രേഖയിൽ ഇല്ലാത്തതിനാൽ, എല്ലാ t x ഉം വ്യത്യസ്തമാണ്, കൂടാതെ രാജ്ഞികൾ ഒരേ ഡയഗണലിൽ അല്ലാത്തതിനാൽ, ഏത് i, j (i< j ≤ 8) имеем: |t j - t i | ≠ j - i.

ക്വീൻ പ്ലെയ്‌സ്‌മെൻ്റുകളുടെ സംഖ്യാ നൊട്ടേഷൻ ചിലപ്പോൾ വളരെ സൗകര്യപ്രദമാണ്. ഉദാഹരണത്തിന്, a1-ൽ രാജ്ഞിയുടെ ഒരു നിശ്ചിത സ്ഥാനമുള്ള രൂപങ്ങൾ കണ്ടെത്താൻ, സംഖ്യാ രൂപത്തിൽ എഴുതിയിരിക്കുന്ന എല്ലാ 92 സ്ഥാനങ്ങളിൽ നിന്നും ആദ്യ കോർഡിനേറ്റ് 1-ന് തുല്യമായവ തിരഞ്ഞെടുത്താൽ മതിയാകും. d3-ൽ രാജ്ഞിയുടെ സ്ഥാനം നിശ്ചയിച്ചിട്ടുണ്ടെങ്കിൽ, നാലാമത്തെ സ്ഥാനം നമ്പർ 3 ആയ സ്ഥാനങ്ങൾ നിങ്ങൾ തിരഞ്ഞെടുക്കണം.

1, 2, ..., 8 എന്ന സംഖ്യകൾ ആദ്യം ആരോഹണ ക്രമത്തിലും പിന്നീട് അവരോഹണ ക്രമത്തിലും എഴുതാം. ഇതിനുശേഷം, ഈ രണ്ട് ക്രമപ്പെടുത്തലുകളുടെയും ഓരോന്നിൻ്റെയും അക്കങ്ങൾ ഒരു അനിയന്ത്രിതമായ ക്രമപ്പെടുത്തലിൻ്റെ നമ്പറുകൾക്കൊപ്പം ഞങ്ങൾ ചേർക്കുന്നു, ഉദാഹരണത്തിന് (3, 7, 2, 8, 5, 1, 4, 6):

തത്ഫലമായുണ്ടാകുന്ന തുകകൾ രണ്ട് കൂട്ടം സംഖ്യകൾ ഉണ്ടാക്കുന്നു: (4, 9, 5, 12, 10, 7, 11, 14) കൂടാതെ (11, 14, 8, 13, 9, 4, 6, 7). അടുത്ത പ്രശ്നം ഉയർന്നുവരുന്നു.

1, 2,..., 8 എന്ന സംഖ്യകളുടെ ഏത് ക്രമമാറ്റങ്ങളാണ് സൂചിപ്പിക്കുന്ന സങ്കലന പ്രവർത്തനത്തിൻ്റെ ഫലമായി അത്തരം രണ്ട് സെറ്റുകൾ ഉണ്ടാകുന്നത്, അവയിൽ ഓരോന്നിലും എല്ലാ സംഖ്യകളും വ്യത്യസ്തമാണ്?

എട്ട് രാജ്ഞിമാരുടെ പ്രശ്നം ഈ ഗണിതശാസ്ത്ര പ്രശ്നവുമായി ബന്ധപ്പെട്ട് കൃത്യമായി ഗൗസിനെ താൽപ്പര്യപ്പെടുത്തി. രാജ്ഞി പ്രശ്‌നത്തിനുള്ള പരിഹാരങ്ങളും വിവരിച്ച ഗണിത പ്രശ്‌നത്തിനുള്ള പരിഹാരങ്ങളും തമ്മിൽ പരസ്പരം കത്തിടപാടുകൾ ഉണ്ടെന്ന് ഇത് മാറുന്നു. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, പരസ്പരം ഭീഷണിപ്പെടുത്താത്ത എട്ട് രാജ്ഞിമാരുടെ ഓരോ ക്രമീകരണവും ഒരു ഗണിത പ്രശ്നത്തിന് പരിഹാരം നൽകുന്നു - തിരിച്ചും. തിരഞ്ഞെടുത്ത ക്രമപ്പെടുത്തലിനായി, രണ്ട് സെറ്റുകളിലും വ്യത്യസ്ത സംഖ്യകൾ അടങ്ങിയിരിക്കുന്നു, ഇത് ആകസ്മികമല്ല - ഇത് ചിത്രം 2 ലെ ആദ്യ സ്ഥാനവുമായി പൊരുത്തപ്പെടുന്നു. 43.

ബോർഡിൻ്റെ n റൊട്ടേഷൻ ഉപയോഗിച്ച്, രാജ്ഞികൾ കൈവശപ്പെടുത്തിയിരിക്കുന്ന ചതുരങ്ങളുടെ കോർഡിനേറ്റുകളിൽ ലളിതമായ ഗണിത പ്രവർത്തനങ്ങൾ ഉപയോഗിച്ച് ചില പരിഹാരങ്ങൾ മറ്റുള്ളവരിൽ നിന്ന് ലഭിക്കുന്നത് കാണാൻ എളുപ്പമാണ്. ഈ പ്രവർത്തനങ്ങളെക്കുറിച്ചുള്ള പഠനം, പരിഹാരങ്ങളുടെ അധിക സവിശേഷതകൾ കണ്ടെത്താൻ ഞങ്ങളെ അനുവദിക്കുന്നു (അവയിൽ ചിലത് ഒകുനെവ് നൽകിയിട്ടുണ്ട്).

എൻ ക്വീൻസിൻ്റെ പ്രശ്നം. n രാജ്ഞികളെ ഒരു n×n ചെസ്സ്ബോർഡിൽ സ്ഥാപിക്കുക, അങ്ങനെ അവർ പരസ്പരം ഭീഷണിപ്പെടുത്തരുത്.

ഒരു 1x1 ബോർഡിൽ, ഒരു രാജ്ഞിയെ ഒരൊറ്റ ചതുരത്തിൽ സ്ഥാപിച്ചിരിക്കുന്നു, ഒരു പരിഹാരം നിലവിലുണ്ട്. 2x2 ബോർഡിൽ, ഒരു രാജ്ഞി, അവൾ എവിടെ നിന്നാലും, ബോർഡിൻ്റെ എല്ലാ ചതുരങ്ങളെയും ഭീഷണിപ്പെടുത്തുന്നു, രണ്ടാമത്തെ രാജ്ഞിയെ സ്ഥാപിക്കാൻ ഒരിടവുമില്ല. 3x3 ബോർഡിൽ മൂന്ന് രാജ്ഞിമാരുടെ ഏത് ക്രമീകരണത്തിലും, അവരിൽ രണ്ട് പേരെങ്കിലും പരസ്പരം ഭീഷണിപ്പെടുത്തുന്നു. അതിനാൽ, 2 അല്ലെങ്കിൽ 3 ന് തുല്യമായ n ന്, പ്രശ്നത്തിന് പരിഹാരങ്ങളില്ല.

കേസുകളിൽ n ​​> 3, ഏത് n×n ബോർഡിലും ഇതുപോലെ n റാണികളെ ക്രമീകരിക്കാൻ കഴിയുമെന്ന് അറിയാം. അവർ പരസ്പരം ഭീഷണിപ്പെടുത്താതിരിക്കാൻ. ഗൗരവമേറിയ ഗണിതശാസ്ത്ര പ്രസിദ്ധീകരണങ്ങളുടേതുൾപ്പെടെ പല ലേഖനങ്ങളും ഇത് വ്യക്തമായ വസ്തുതയിൽ നിന്ന് വളരെ അകലെയാണെന്ന് തെളിയിക്കാൻ നീക്കിവച്ചിരിക്കുന്നു.

4x4 ബോർഡിൽ ഒരു അടിസ്ഥാന ക്രമീകരണം മാത്രമേയുള്ളൂ, അത് ഇരട്ടി സമമിതിയാണ് (a2, b4, c1, d3), അതായത് ആകെ രണ്ട് പരിഹാരങ്ങളുണ്ട്. 5x5 ബോർഡിൽ രണ്ട് പ്രധാന രൂപങ്ങൾ ഉണ്ട്: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; ആകെ പത്ത് സെർച്ച് പൊസിഷനുകളുണ്ട്. രസകരമെന്നു പറയട്ടെ, നിങ്ങൾക്ക് അവയിൽ അഞ്ചെണ്ണം തിരഞ്ഞെടുക്കാം, അവ പരസ്പരം മുകളിൽ അടുക്കുമ്പോൾ, 5x5 ബോർഡിൻ്റെ എല്ലാ ചതുരങ്ങളും 25 രാജ്ഞികളാൽ നിറയ്ക്കും. പൊതുവായ സാഹചര്യത്തിൽ, സമാനമായ ചുമത്തൽ 2 അല്ലെങ്കിൽ 3 കൊണ്ട് ഹരിക്കാനാവാത്തവയ്ക്ക് മാത്രമേ സാധ്യമാകൂ. ഇതിൽ നിന്ന്, പ്രത്യേകിച്ചും, ഒരു സാധാരണ ബോർഡിന് എട്ട് പരിഹാരങ്ങൾ തിരഞ്ഞെടുക്കുന്നത് അസാധ്യമാണ്. മുഴുവൻ ബോർഡ്.

എട്ട് രാജ്ഞിമാരുടെ പ്രശ്‌നത്തിനുള്ള പരിഹാരങ്ങളുടെ മുകളിലുള്ള ബീജഗണിത ഗുണത്തെ സാമാന്യവൽക്കരിക്കുന്നത്, ഏതെങ്കിലും i, j (i) ന് n × n ബോർഡിലെ ക്രമീകരണം (t 1, t 2, ... t n) n ക്വീൻസ് ആണെന്ന് ഞങ്ങൾ മനസ്സിലാക്കുന്നു.< j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

എല്ലാ n > 5 നും ഒരു n × n ബോർഡിൽ n ക്വീനുകളുടെ ആവശ്യമുള്ള ക്രമീകരണത്തിന് സാധ്യമായ ഒരു സ്കീമിനെ ഞങ്ങൾ ഇപ്പോൾ വിവരിക്കും. തത്ഫലമായുണ്ടാകുന്ന ക്രമീകരണത്തിൽ ഞങ്ങളുടെ അവസ്ഥ തൃപ്തികരമാണെന്നതിൻ്റെ തെളിവ്, ഉദാഹരണത്തിന്, Okunev അല്ലെങ്കിൽ Yaglomov എന്നിവയിൽ കാണാം.

നമുക്ക് കേസുകളുടെ ഒരു പരമ്പര തുടർച്ചയായി പരിഗണിക്കാം. n = 6k അല്ലെങ്കിൽ n = 6k + 4 ഉപയോഗിച്ച് n ആദ്യം തുല്യമായിരിക്കട്ടെ. രണ്ടാമത്തെ തിരശ്ചീനത്തിൽ നിന്ന് ആരംഭിച്ച് ഓരോ തവണയും 2 ചതുരങ്ങൾ മുകളിലേക്കും 1 നും ചലിപ്പിച്ചുകൊണ്ട് നൈറ്റിനെ ചലിപ്പിച്ചുകൊണ്ട് ഞങ്ങൾ എല്ലാ രാജ്ഞികളുടെയും പകുതിയെ ആദ്യത്തെ n/2 ലംബങ്ങളിൽ സ്ഥാപിക്കുന്നു. വലത്തേക്ക്. ഞങ്ങൾ അതേ രീതിയിൽ ശേഷിക്കുന്ന n/2 ലംബങ്ങളിൽ രണ്ടാം പകുതി സ്ഥാപിക്കും, എന്നാൽ ആദ്യ തിരശ്ചീനത്തിൽ നിന്ന് ആരംഭിക്കുന്നു. ഒരു 6x6 ബോർഡിന് (n = 6k, k = 1) ഇത് രാജ്ഞികളുടെ ഇനിപ്പറയുന്ന ക്രമീകരണം നൽകുന്നു: a2, b4, c6, d1, e3, f5 (ചിത്രം 45-ൽ n = 10 ന് നൽകിയിരിക്കുന്ന പരിഹാരം വ്യത്യസ്തമായി ലഭിക്കും).

n = 6k + 2 എപ്പോൾ മുമ്പത്തെ സാങ്കേതികത പ്രവർത്തിക്കില്ല, കൂടാതെ രാജ്ഞികളെ കൂടുതൽ "കൗശലമുള്ള" രീതിയിൽ സ്ഥാപിക്കേണ്ടതുണ്ട്. നൈറ്റിനെ രണ്ടാമത്തെ ലംബത്തിൽ നിന്ന് നീക്കിക്കൊണ്ട് നമുക്ക് അവയെ ക്രമീകരിക്കാം

(n/2 - 2)th, മൂന്നാമത്തെ തിരശ്ചീനത്തിൽ നിന്ന് ആരംഭിച്ച്, തുടർന്ന്

(n/2 + 3)th ലംബമായ (n - 1)th, ആറാമത്തെ തിരശ്ചീനത്തിൽ നിന്ന് ആരംഭിക്കുന്നു. തൽഫലമായി, ബോർഡിൻ്റെ ആറ് ലംബങ്ങളും ആറ് തിരശ്ചീനങ്ങളും സ്വതന്ത്രമായി നിലനിൽക്കും, അതിൽ ആറ് രാജ്ഞികൾ ഇനിപ്പറയുന്ന കോർഡിനേറ്റുകളുള്ള ചതുരങ്ങൾ ഉൾക്കൊള്ളണം: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). n = 14 (n = 6k + 2, k = 2) എന്നതിനായി നമുക്ക് ചിത്രത്തിൽ ക്രമീകരണം ലഭിക്കും. 44. വഴിയിൽ, ഒരു സാധാരണ 8 × 8 ബോർഡിൽ (8 = 6k + 2, k = 1) എട്ട് രാജ്ഞിമാരുടെ സ്ഥാനം ഈ രീതിയിൽ ചിത്രത്തിലെ അതേ അത്ഭുതകരമായ പരിഹാരവുമായി പൊരുത്തപ്പെടുന്നു. 43 (രണ്ടാം സ്ഥാനം), എന്നാൽ ഇവിടെ രാജ്ഞിമാരുടെ ക്രമീകരണത്തിൽ ഒരു പാറ്റേൺ ശ്രദ്ധിക്കാൻ പ്രയാസമാണ്.

n ൻ്റെ വിചിത്ര മൂല്യങ്ങൾക്കുള്ള പ്രശ്നം പരിഗണിക്കുന്നത് ഞങ്ങൾക്ക് അവശേഷിക്കുന്നു. ഈ സാഹചര്യത്തിൽ ഒരു പരിഹാരം ലഭിക്കുന്നതിന്, "പോലും" ബോർഡുകളിൽ ഞങ്ങൾ നിർദ്ദേശിച്ച ക്രമീകരണത്തിൽ, പ്രധാന ഡയഗണൽ (താഴെ ഇടത് കോണിൽ നിന്ന് മുകളിൽ വലത്തേക്ക് പോകുന്നത്) സ്വതന്ത്രമായി നിലകൊള്ളുന്നു എന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്. ഈ സാഹചര്യം കണക്കിലെടുത്താൽ, ഒരു n×n ബോർഡിൽ n ക്വീനുകളുടെ ആവശ്യമുള്ള ക്രമീകരണം (ഒറ്റ n ന്) ഇനിപ്പറയുന്ന രീതിയിൽ ലഭിക്കും. 1 മുതൽ (n - 1) വരെയുള്ള അക്കങ്ങളുള്ള ഈ ബോർഡിൻ്റെ ലംബങ്ങളിലും തിരശ്ചീനങ്ങളിലും ഞങ്ങൾ (n - 1) രാജ്ഞിയെ ബോർഡിൽ (n - 1)×(n - 1) (n - 1) സ്ഥാപിക്കും. തുല്യമാണ്!), തുടർന്ന് ഞങ്ങൾ nth രാജ്ഞിയെ ബോർഡിൻ്റെ മുകളിൽ വലത് കോണിൽ സ്ഥാപിക്കും. വിവരിച്ച രീതി ഉപയോഗിച്ച്, 4×4 ബോർഡിലെ സൂചിപ്പിച്ചിരിക്കുന്ന ക്രമീകരണത്തിൽ നിന്ന് 5×5 ബോർഡിലെ റാണികളുടെ ആദ്യ ക്രമീകരണം നമുക്ക് ലഭിക്കും, കൂടാതെ 6×6 ബോർഡിലെ രാജ്ഞികളുടെ ക്രമീകരണത്തിൽ നിന്ന് n = 7 ന് ഇനിപ്പറയുന്നവയുണ്ട്. : a2, b4, c6, d1, e3, f5, g7 .

അൽഗോരിതങ്ങൾ മനസ്സിലാക്കുന്നതിനുള്ള ഒരു പ്രിയപ്പെട്ട പ്രശ്നം പരിഗണിക്കുക, എട്ട് ക്വീൻസ് പ്രശ്നം. ക്ലാസിക് നിർവചനം ഇതാണ്: "8 രാജ്ഞികളെ ഒരു ചെസ്സ് ബോർഡിൽ സ്ഥാപിക്കുക, അങ്ങനെ അവരാരും മറ്റൊന്നിനെ തോൽപ്പിക്കില്ല." ശരി, വിവിധ അഭിമുഖങ്ങളിൽ പ്രശ്നം വളരെ ജനപ്രിയമാണ്, വിക്കിപീഡിയ ഉടൻ തന്നെ എൻ്റെ പ്രിയപ്പെട്ട പൈത്തണിൽ ഒരു പരിഹാരം നൽകുന്നു.

ഒരു സാധാരണ വ്യക്തിയുടെ വീക്ഷണകോണിൽ നിന്നുള്ള ശരിയായ തീരുമാനമാണിത്, പക്ഷേ ഒരു ഹാക്കറുടെ വീക്ഷണകോണിൽ നിന്ന് തികച്ചും അർത്ഥശൂന്യമാണ്, എന്തുകൊണ്ടെന്ന് ഞാൻ നിങ്ങളോട് പറയും:

നമുക്ക് അൽഗോരിതം വിശകലനം ചെയ്യാം: ഒരു ക്ലാസിക് ബാക്ക്ട്രാക്കിംഗ് തിരയൽ ഉപയോഗിക്കുന്നു, പരിഹാര മേഖലയെ ഞങ്ങൾ ഒരു ഗ്രാഫിൻ്റെ രൂപത്തിൽ പ്രതിനിധീകരിക്കുന്നു, അതിൻ്റെ ഓരോ ശീർഷകവും രാജ്ഞിയുടെ സ്ഥാനമാണ്, അതിൽ അവൾ ആക്രമണത്തിനിരയാകാത്തതും ഇതിനകം സ്ഥാപിച്ചിട്ടുള്ള രാജ്ഞികളെ തോൽപ്പിക്കുന്നില്ല. ബോർഡ്, അതായത്. കൃത്യമായി എട്ട് ലംബങ്ങൾ അടങ്ങിയ എല്ലാ "ശാഖകളും" മാത്രമേ നമുക്ക് ശേഖരിക്കേണ്ടതുള്ളൂ. ഈ "ശാഖകൾ" തിരയുന്നതിനുള്ള ഒരു രീതി എന്ന നിലയിൽ, രചയിതാവ് ഞങ്ങൾക്ക് ക്ലാസിക് വീതി-ആദ്യ തിരയൽ അൽഗോരിതം വാഗ്ദാനം ചെയ്യുന്നു, അതായത്. ഗ്രാഫ് കടന്നുപോകുന്ന ക്രമം ഇതുപോലെ കാണപ്പെടും:

അൽഗോരിതം പ്രവർത്തിക്കുന്ന ഉടൻ, സാധ്യമായ എല്ലാ പരിഹാരങ്ങളും നമുക്ക് ലഭിക്കും.

അപ്പോൾ എന്താണ് പ്രശ്നം? ഞങ്ങളുടെ കാര്യത്തിൽ, ഒരു 8x8 ബോർഡിനായി, ഞങ്ങൾക്ക് 92 വ്യത്യസ്ത പരിഹാരങ്ങൾ ലഭിക്കും, എന്നാൽ യഥാർത്ഥ പ്രശ്‌നങ്ങളിൽ പലപ്പോഴും സംഭവിക്കുന്നത് പോലെ, ബോർഡിൻ്റെ വലുപ്പം ഞങ്ങൾക്ക് അറിയില്ലെന്ന് സങ്കൽപ്പിക്കുക. തായ് ഷോഗിയിലെ പോലെ ബോർഡ് 25x25 ആണെങ്കിൽ, പരിഹാരങ്ങളുടെ എണ്ണം ഇതിനകം 275,986,683,743,434 ആയിരിക്കും.

ബോർഡിൻ്റെ വലുപ്പത്തിലുള്ള പരിഹാരങ്ങളുടെ എണ്ണത്തെ ആശ്രയിക്കുന്നത് കാണിക്കുന്ന പട്ടിക:

ഇത് നമ്മുടെ സ്ക്രിപ്റ്റിന് എന്താണ് അർത്ഥമാക്കുന്നത്? അവൻ വളരെ നീണ്ട തിരയലിലേക്ക് പോകുമെന്നതും എല്ലാ തീരുമാനങ്ങളും മനസ്സിൽ സൂക്ഷിക്കേണ്ടതിനാൽ, വെറും 15 മിനിറ്റിനുള്ളിൽ പൈത്തൺ 300 മെഗാബൈറ്റ് മെമ്മറി നശിപ്പിക്കും. ശക്തമായ പ്രോസസറും വലിയ അളവിലുള്ള റാമും ഉള്ള ആർക്കും ഈ പ്രക്രിയ പൂർത്തിയായിട്ടുണ്ടോ എന്ന് പരിശോധിക്കാൻ കഴിയും...

അത്തരമൊരു പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾക്ക് ആവശ്യമായത് ഗ്രാഫിൽ സഞ്ചരിക്കുന്നതിനുള്ള ശരിയായ അൽഗോരിതം തിരഞ്ഞെടുക്കുക എന്നതാണ്, അത് ഞങ്ങളുടെ കാര്യത്തിൽ ഒരു സാധാരണ ആഴത്തിലുള്ള ആദ്യ തിരയലായിരിക്കും, തുടർന്ന് ഗ്രാഫ് ഈ ക്രമത്തിൽ സഞ്ചരിക്കും:

കോഡ് വളരെ ലളിതമായിരിക്കും, കൂടാതെ 15 മിനിറ്റിനു ശേഷവും സ്ക്രിപ്റ്റ് സമാരംഭിച്ചതിന് ശേഷമുള്ള ഒരു സെക്കൻഡിൻ്റെ അതേ അളവിലുള്ള മെമ്മറി ഉപയോഗിക്കും. പൈത്തണിൽ ഇത് നടപ്പിലാക്കുന്നത് ഇങ്ങനെയാണ്:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: n_row in range (വീതി): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): col in range(len(sol)): if (sol == new_row or abs(col - new_col) == abs(sol - new_row)): 0 റിട്ടേൺ 1 എങ്കിൽ __name__ == "__main__": n എന്ന ശ്രേണിയിലെ (8): rc_queens(1, 8, [n])
പി.എസ്. ഇത് പ്രശ്നത്തെക്കുറിച്ചുള്ള ഒരു ഹാക്കറുടെ വീക്ഷണം മാത്രമാണ്, ഒരുപക്ഷേ ആർക്കെങ്കിലും "സൈദ്ധാന്തിക കമ്പ്യൂട്ടർ സയൻസ്" കാഴ്ച നൽകാൻ കഴിയുമോ?