எட்டு இராணி புதிர்

எட்டு இராணி புதிர் (Eight queens puzzle) என்பது 8×8 வரிசை கொண்ட சதுரங்கப்பலகையில் 8 சதுரங்க இராணிகளை, எந்தவிரு இராணிகளும் ஒன்றையொன்று தாக்காத வண்ணம் எவ்வாறு நிரப்ப முடியும் என்ற புதிராகும். இப்புதிருக்கான தீர்வில் எந்த இரண்டு ராணிகளும் ஒரே நிரையிலோ அல்லது ஓரே மூலைவிட்டத்திலோ அமையாது. 'n' ராணி புதிருக்கான எடுத்துக்காட்டாக 8 ராணி புதிரானது அமைந்துள்ளது. இத்தகைய 'n' ராணி புதிர்களுக்கு n=2, n= 3 தவிர அனைத்து 'n' - இயல் எண் வரிசைக்கும் தீர்வு உண்டு.[1]

abcdefgh
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
எட்டு இராணி புதிருக்கான ஒரேயொரு சமச்சீர் தீர்வு (சுழற்சி மற்றும் தனக்குத்தானே எதிரொளிப்பு நீங்கலாக).

வரலாறுதொகு

மேக்‌ஸ் பெசல் என்ற சதுரங்கவியலாளர் 1848-ல் எட்டு ராணி புதிரை வெளியிட்டார். பிரான்ஸ் நாயுக் என்பவர் 1850-ல் இப்புதிருக்கான தீர்வினை வெளியிட்டார்.[2] மேலும் இவர் 'n'- ராணி புதிருக்கானத் தீர்வினையும் வெளியிட்டார்.

இதனைத் தொடர்ந்து கார்ல் ஃப்ரெடெரிக் காஸ் உள்ளிட்ட பல கணிதவியலாளர்கள் இப்புதிருக்கானத் தீர்வைக் காண முனைந்தனர். 1878-ல் ச.குன்தர் என்பவர் அணிக்கோவைகளைப் பயன்படுத்தி இப்புதிருக்கான தீர்வினைக் காணும் முறையினை முன்மொழிந்தார்.[2]

தீர்வுதொகு

இந்த எட்டு ராணி புதிரானது 92 தனிவிதமான தீர்வுகளை கொண்டுள்ளது. சுழற்சி, எதிரொளிப்பு உருமாற்றங்களின் சமச்சீர்தன்மையைக் கொண்டு கணக்கிடும்போது இப்புதிரானது கீழே காட்டப்பட்டுள்ள 12 அடிப்படைத் தீர்வுகளைக் கொண்டுள்ளது.

12 அடிப்படைத் தீர்வுகள்தொகு

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 1

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 2

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 3

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 4

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Solution 5

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 6

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 7

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 8

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 9

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 10

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 11

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
தீர்வு 12

தீர்வுகளின் எண்ணிக்கைதொகு

கீழுள்ள அட்டவணை n × n சதுரங்கப் பலகையில் n சதுரங்க இராணிகளை வைப்பதற்கான தீர்வுகளின் எண்ணிக்கையைத் தருகிறது (n=1–10, 24–27).

அடிப்படைத் தீர்வுகள்:(OEIS-இல் வரிசை A002562)
அனைத்துத் தீர்வுகள்: (OEIS-இல் வரிசை A000170)

,

n: 1 2 3 4 5 6 7 8 9 10 ... 24 25 26 27
அடிப்படை: 1 0 0 1 2 1 6 12 46 92 ... 28,439,272,956,934 275,986,683,743,434 2,789,712,466,510,289 29,363,791,967,678,199
அனைத்து: 1 0 0 2 10 4 40 92 352 724 ... 227,514,171,973,736 2,207,893,435,808,352 22,317,699,616,364,044 234,907,967,154,122,528

இவ்வட்டணையிலிருந்து ஆறு இராணிப் புதிருக்கான தீர்வுகளின் எண்ணிக்கை ஐந்து இராணிப் புதிருக்கான தீர்வுகளை விடக் குறைவாக உள்ளதைக் காணலாம்.

சரியான தீர்வுகளின் எண்ணிக்கையைக் காண உதவும் வாய்ப்பாடு எதுவும் தற்சமயம்வரை இல்லை. தற்போதைய நிலவரப்படி தீர்வுகளின் எண்ணிக்கை முழுமையாகக் கண்டறியப்பட்டவற்றுள் 27x27 பலகையே உயர் வரிசையினதாகும்.[3]

மேற்கோள்கள்தொகு

  1. E. J. Hoffman et al., "Construction for the Solutions of the m Queens Problem". Mathematics Magazine, Vol. XX (1969), pp. 66–72. [1]
  2. 2.0 2.1 W. W. Rouse Ball (1960) "The Eight Queens Problem", in Mathematical Recreations and Essays, Macmillan, New York, pp. 165–171.
  3. The Q27 Project

மேலதிக வாசிப்புக்குதொகு

  • Bell, Jordan; Stevens, Brett (2009). "A survey of known results and research areas for n-queens". Discrete Mathematics 309 (1): 1–31. doi:10.1016/j.disc.2007.12.043. 
  • Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. பன்னாட்டுத் தரப்புத்தக எண்:0-691-11503-6. 
  • O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 see pp 72–82 for Dijkstra's solution of the 8 Queens problem.
  • "Three Dimensional NxN-Queens Problems" (1988).
  • Nudelman, S. (1995). "The Modular N-Queens Problem in Higher Dimensions". Discrete Mathematics 146 (1-3): 159–167. doi:10.1016/0012-365X(94)00161-5. 
  • Engelhardt, M. (August 2010). "Der Stammbaum der Lösungen des Damenproblems (in German, means The pedigree chart of solutions to the 8-queens problem". Spektrum der Wissenschaft: 68–71. http://www.spektrum.de/artikel/1037434&_z=798888. 
  • On The Modular N-Queen Problem in Higher Dimensions, Ricardo Gomez, Juan Jose Montellano and Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexico.
  • Wirth, Niklaus (1976), Algorithms + Data Structures = Programs, Prentice-Hall, ISBN 0-13-022418-9

வெளியிணைப்புகள்தொகு

"https://ta.wikipedia.org/w/index.php?title=எட்டு_இராணி_புதிர்&oldid=2696258" இருந்து மீள்விக்கப்பட்டது