எட்டு இராணி புதிர்
எட்டு இராணி புதிர் (Eight queens puzzle) என்பது 8×8 வரிசை கொண்ட சதுரங்கப்பலகையில் 8 சதுரங்க இராணிகளை, எந்தவிரு இராணிகளும் ஒன்றையொன்று தாக்காத வண்ணம் எவ்வாறு நிரப்ப முடியும் என்ற புதிராகும். இப்புதிருக்கான தீர்வில் எந்த இரண்டு ராணிகளும் ஒரே நிரையிலோ அல்லது ஓரே மூலைவிட்டத்திலோ அமையாது. 'n' ராணி புதிருக்கான எடுத்துக்காட்டாக 8 ராணி புதிரானது அமைந்துள்ளது. இத்தகைய 'n' ராணி புதிர்களுக்கு n=2, n= 3 தவிர அனைத்து 'n' - இயல் எண் வரிசைக்கும் தீர்வு உண்டு.[1]
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
வரலாறுதொகு
மேக்ஸ் பெசல் என்ற சதுரங்கவியலாளர் 1848-ல் எட்டு ராணி புதிரை வெளியிட்டார். பிரான்ஸ் நாயுக் என்பவர் 1850-ல் இப்புதிருக்கான தீர்வினை வெளியிட்டார்.[2] மேலும் இவர் 'n'- ராணி புதிருக்கானத் தீர்வினையும் வெளியிட்டார்.
இதனைத் தொடர்ந்து கார்ல் ஃப்ரெடெரிக் காஸ் உள்ளிட்ட பல கணிதவியலாளர்கள் இப்புதிருக்கானத் தீர்வைக் காண முனைந்தனர். 1878-ல் ச.குன்தர் என்பவர் அணிக்கோவைகளைப் பயன்படுத்தி இப்புதிருக்கான தீர்வினைக் காணும் முறையினை முன்மொழிந்தார்.[2]
தீர்வுதொகு
இந்த எட்டு ராணி புதிரானது 92 தனிவிதமான தீர்வுகளை கொண்டுள்ளது. சுழற்சி, எதிரொளிப்பு உருமாற்றங்களின் சமச்சீர்தன்மையைக் கொண்டு கணக்கிடும்போது இப்புதிரானது கீழே காட்டப்பட்டுள்ள 12 அடிப்படைத் தீர்வுகளைக் கொண்டுள்ளது.
12 அடிப்படைத் தீர்வுகள்தொகு
தீர்வு 1
|
தீர்வு 2
|
தீர்வு 3
|
தீர்வு 4
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Solution 5
|
தீர்வு 6
|
தீர்வு 7
|
தீர்வு 8
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
தீர்வு 9
|
தீர்வு 10
|
தீர்வு 11
|
தீர்வு 12
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
தீர்வுகளின் எண்ணிக்கைதொகு
கீழுள்ள அட்டவணை n × n சதுரங்கப் பலகையில் n சதுரங்க இராணிகளை வைப்பதற்கான தீர்வுகளின் எண்ணிக்கையைத் தருகிறது (n=1–10, 24–27).
,
| 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]
மேற்கோள்கள்தொகு
- ↑ E. J. Hoffman et al., "Construction for the Solutions of the m Queens Problem". Mathematics Magazine, Vol. XX (1969), pp. 66–72. [1] பரணிடப்பட்டது 2016-11-08 at the வந்தவழி இயந்திரம்
- ↑ 2.0 2.1 W. W. Rouse Ball (1960) "The Eight Queens Problem", in Mathematical Recreations and Essays, Macmillan, New York, pp. 165–171.
- ↑ 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. https://archive.org/details/acrossboardma00watk.
- 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.
- Allison, L.; Yee, C.N.; McGaughey, M. (1988). "Three Dimensional NxN-Queens Problems". Department of Computer Science, Monash University, Australia.
- 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
வெளியிணைப்புகள்தொகு
| The Wikibook Algorithm Implementation மேலதிக விவரங்களுள்ளன: N-queens problem |
- Weisstein, Eric W., "Queens Problem", MathWorld.