🏊 ☠️ 🙆🏽 एक प्रोग्रामर या पहेली क्राइस-क्रॉस के लिए अध्ययन करें 😬 🌄 👠

मुझे लगता है कि चार्ल्स वेर्ली द्वारा कई एब्रोवस्क नागरिकों को प्रोग्राम एदर्स फॉर प्रोग्रामर्स से परिचित किया गया है। यदि नहीं, तो यहाँ आप लेखक के साथ साक्षात्कार और पुस्तक की संक्षिप्त समीक्षा पढ़ सकते हैं। मैं खुद हाल ही में इस चीज़ में पड़ गया, और निश्चित रूप से किसी एक कार्य को लागू करने का निर्णय लिया गया।

इसलिए मैं आपके साथ एक रेखाचित्र से निपटने का प्रस्ताव करता हूं। हम जावा में लिखेंगे, हम ग्राफिक्स और जीयूआई के साथ काम करेंगे + हम अपने समाधान को खोजने के लिए वापसी के साथ खोज एल्गोरिदम का विश्लेषण करेंगे। यह संभावना नहीं है कि लेख पेशेवरों को दिलचस्पी देगा, लेकिन शुरुआती लोगों के लिए, और विशेष रूप से वे जो सिर्फ जावा सीख रहे हैं, लेख उपयोगी हो सकता है।
किसी की दिलचस्पी - स्वागत है!

समस्या का बयान

यहां मैं "अध्ययन" से एक अंश देता हूं, जो पाठक को अद्यतित करेगा।

बहुत से लोग सोचते हैं कि वर्ग पहेली को हल करना बहुत मुश्किल है, क्योंकि वे शब्द का अनुमान नहीं लगा सकते हैं। लेकिन मुझे कोशिकाओं में पत्र लिखना पसंद है। ऐसे लोगों के लिए, एक सरल पहेली है - क्रिस-क्रॉस। प्रत्येक क्राइस-क्रॉस में शब्दों की एक सूची होती है, जिन्हें लंबाई के अनुसार समूहों में सुविधा के लिए विभाजित किया जाता है और प्रत्येक समूह के भीतर वर्णानुक्रम में क्रमबद्ध किया जाता है, साथ ही साथ उस योजना से जिसमें शब्दों को दर्ज किया जाना चाहिए। यह योजना उसी नियम का पालन करती है जैसा कि क्रॉसवर्ड पहेली में - चौराहे के स्थानों पर शब्दों का एक सामान्य अक्षर होता है, हालाँकि, संख्याएँ उपलब्ध नहीं होती हैं, क्योंकि शब्द पहले से ज्ञात होते हैं, आपको केवल उन्हें सही स्थानों पर दर्ज करने की आवश्यकता होती है।

आप आकृति में इस तरह की पहेली का एक उदाहरण देख सकते हैं।

ईमानदारी से, मैं वास्तव में कोशिकाओं में पत्र लिखना पसंद नहीं करता हूं, इसलिए हमारा कार्यक्रम बस एक तैयार-पूर्ण, पूर्ण योजना + एक छोटा बोनस देगा। हम एक पाठ फ़ाइल से शब्दों की सूची पढ़ेंगे। यदि कई ऐसे हैं जो इस तरह की पहेली को हल करना चाहते हैं, तो मैं ख़ुशी से इस अवसर को जोड़ूंगा।
Nus, शब्दों से कार्रवाई तक - एक कार्य है, एक इच्छा है, चलो चलें!

आर्किटेक्चर

ठीक है, या हम कैसे स्टोर करेंगे और सब कुछ आकर्षित करेंगे ।
मेरे पास कई विकल्प थे, इस स्तर पर मैंने कई बार खरोंच से सब कुछ मिटा दिया। मुझे लगता है कि ऐसे लोग होंगे जो समाधान को सरल और अधिक सुरुचिपूर्ण तरीके से देखते हैं, किसी भी मामले में, ध्वनि आलोचना का स्वागत है।
प्रारंभिक विचार "पत्र" वर्ग और इन "शब्द" कोशिकाओं के लिए एक कंटेनर वर्ग बनाने के लिए है। प्रत्येक "सेल विद ए लेटर" अपने स्वयं के प्रतीक को संग्रहीत करता है, साथ ही दो तार्किक निर्देशांक, इन निर्देशांक को सेल के आकार (स्थिर) से गुणा करते हुए, हम आसानी से निर्धारित कर सकते हैं कि सेल और प्रतीक कहाँ खींचे गए हैं। मेरे लिए यहां मुख्य कठिनाई यह थी कि सभी शब्दों को दो प्रकारों में विभाजित किया गया है: क्षैतिज और ऊर्ध्वाधर। तदनुसार, इस दृष्टिकोण के साथ उनके सभी प्रसंस्करण के दो संस्करण भी होंगे। मैं इससे छुटकारा पाना चाहता था।
निम्नलिखित विचार: प्रत्येक शब्द में क्षैतिज शब्दों में सभी कोशिकाओं के लिए एक समन्वित आम है, और ऊर्ध्वाधर एक्स में। आइए ऐसा करते हैं: हमारे पास "शब्द का समन्वय" होगा, इस शब्द के लिए एक निरंतर मूल्य और बदले में प्रत्येक कोशिका में केवल एक समन्वय होता है। , शब्द में सभी कोशिकाओं के लिए अलग। आप कहते हैं, "फ़ुहुहुह, किसी तरह भ्रामक है," लेकिन मुझे बेहतर समाधान नहीं मिला, शायद कोड अधिक समझ में आएगा। वैसे, लेख के अंत में, GitHub पर एक लिंक देखें, आप पूरे प्रोजेक्ट कोड को देख सकते हैं।

हमारे "पत्र पिंजरे"

public class CharCell { private char value; private int variableCoord; public final static int CELL_SIZE = 30; public CharCell( char value, int variableCoord ) { this.value = value; this.variableCoord = variableCoord; } ... }

हमारा "शब्द"

चारसेल एरे को इस वर्ग में संग्रहित किया जाता है - हमारे शब्द के सभी अक्षर, इस शब्द का समन्वय और इंटेंस ओरिएंटेशन फील्ड, जिसका आप अनुमान लगा सकते हैं, इसके दो अर्थ हो सकते हैं

 public class Orientation { public final static int HORIZ = 0; public final static int VERTIC = 1; }

स्थानांतरणों का इतना सरल और निश्चित रूप से असुरक्षित कार्यान्वयन, मैं पहले से माफी मांगता हूं, लेकिन मैं इस बिंदु पर लंबे समय तक निवास नहीं करना चाहता था।

 public class Word { private CharCell [] cells; private int orientation; private int wordCoord; private int length; public Word( String word, int orientation, int wordCoord, int initialVariableCoord ) { this.orientation = orientation; this.wordCoord = wordCoord; this.length = word.length(); cells = new CharCell[length]; for ( int i = 0 ; i < length ; i++ ) { cells[i] = new CharCell( word.charAt(i), initialVariableCoord + i ) ; } } ... }

जैसा कि आप देख सकते हैं, एक नया शब्द बनाने के लिए कोड अंतरिक्ष में अपने "अभिविन्यास" से पूरी तरह से स्वतंत्र है, और अन्य, अधिक जटिल कार्यों - जोड़ने, जाँच, आदि में प्रसंस्करण में कोई अंतर नहीं होगा। लेकिन पहले चीजें, पहले आइए अब इस बात पर विचार करें कि हमारे पत्र वास्तव में कैसे खींचे जाते हैं।

ड्राइंग

ड्राइंग कोड चारसेल क्लास में निहित है और शोचर्सेल विधि (नीचे देखें) में संलग्न है, यह यहाँ है कि हम क्षैतिज और ऊर्ध्वाधर शब्दों में विभाजित कर रहे हैं।
ड्राइंग शुरू करने के लिए, आपको एक वर्ग को परिभाषित करने की आवश्यकता है जो JComponent को इनहेरिट करता है और PaintComponent () विधि को ओवरराइड करता है। हमारे कार्यक्रम में ऐसा वर्ग वर्डआयर वर्ग है, जिस पर थोड़ी देर बाद चर्चा की जाएगी। यह इस वर्ग से है कि showCharCell फ़ंक्शन Graphics2D और अन्य मापदंडों को स्वीकार करता है। पेंटकम्पोनेंट () पद्धति में ग्राफिक्स के एक प्रकार का एक पैरामीटर प्राप्त होता है, जिसमें सभी ड्राइंग विधियां और चित्र, आकार और पाठ की छवि के लिए सेटिंग्स का एक सेट होता है। हर बार एक खिड़की खींचना आवश्यक है, इसके सभी घटकों के पेंटकंपोनेंट () विधि को निष्पादित किया जाता है।

वास्तव में हमारे "सेल एक पत्र के साथ" ड्राइंग के लिए प्रक्रिया

 public void showCharCell ( Graphics2D g2D, Font font, FontRenderContext context, int orient, int constCoord ) { int coordX; int coordY; if ( orient == Orientation.HORIZ ) { coordX = variableCoord * CELL_SIZE; coordY = constCoord * CELL_SIZE; } else { coordX = constCoord * CELL_SIZE; coordY = variableCoord * CELL_SIZE; } String s = String.valueOf(value); Rectangle2D bounds = font.getStringBounds( s, context ); LineMetrics metrics = font.getLineMetrics( s, context ); float descent = metrics.getDescent(); float leading = metrics.getLeading(); Rectangle2D.Double rect = new Rectangle2D.Double( coordX, coordY, CELL_SIZE, CELL_SIZE ); double x = rect.getX() + (rect.getWidth() - bounds.getWidth())/2; double y = rect.getY() + rect.getHeight() - descent - leading; g2D.draw( rect ); g2D.drawString( s, (int)x, (int)y ); }

GetStringBounds () विधि उस आयत को लौटाती है जिस रेखा को हम खींचना चाहते हैं। हमें इसकी आवश्यकता है ताकि हमारा पत्र खींचे गए वर्ग के बीच में हो। चौड़ाई को संरेखित करने के लिए, पहले हमें उस वर्ग की चौड़ाई मिलती है, जिसमें हम अपने पत्र में प्रवेश करना चाहते हैं, इस चौड़ाई का हिस्सा पत्र द्वारा कब्जा कर लिया जाता है, इसलिए प्रत्येक तरफ खाली जगह का आकार वर्ग की चौड़ाई और चरित्र की चौड़ाई के बीच के अंतर के बराबर है। मुझे लगता है कि कोड स्पष्ट होना चाहिए। ऊंचाई में संरेखित करने के लिए, हमारे वर्ग के नीचे से प्रतीकों की लैंडिंग की गहराई और अग्रणी ( वंश और अग्रणी ) को घटाएं। अब हमारे सभी अक्षर ध्यान से उनकी कोशिकाओं में आ गए हैं।
वर्ड क्लास की एक विधि जो किसी शब्द को प्राथमिक बनाती है:

 public void showWord( Graphics2D g2D, Font font, FontRenderContext context ) { for ( int i = 0 ; i < length ; i++ ) { cells[i].showCharCell ( g2D, font, context, orientation, wordCoord ); } }

यह हमारे अध्ययन के सबसे कठिन वर्ग - वर्डआयर पर छूने का समय है
जैसा कि ऊपर उल्लेख किया गया है, यह एक JComponent है और इसमें थोड़ा संशोधित ArrayList <Word> mainWordArea शामिल है । यह हमारी शब्द योजना है, इसमें एक नया शब्द जोड़ने के लिए बहुत ही सरल है mainWordArea.add (नया शब्द ("शब्द", ओरिएंटेशन .ORIZ, x, y)) , यह है कि हमारा कार्यक्रम सभी संभव विकल्पों की कोशिश करके हमारी योजना में शब्दों को जोड़ता है।
खैर, यहाँ paintComponent () है

 @Override public void paintComponent ( Graphics g ) { Graphics2D g2D = ( Graphics2D ) g; g2D.setRenderingHint( RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON ); context = g2D.getFontRenderContext(); g2D.setFont( font ); Iterator<Word> wordAreaIter = mainWordArea.iterator(); while ( wordAreaIter.hasNext() ) wordAreaIter.next().showWord( g2D, font, context ); }

हम मुख्य रूप से मुख्य शब्दों में सभी शब्दों पर पुनरावृति करते हैं, उनमें से प्रत्येक का प्रतिपादन करते हैं।

मुझे आशा है कि मैं पाठक को कार्यक्रम के तर्क से अवगत कराने में कामयाब रहा, और हम आगे बढ़ सकते हैं, खासकर जब से सभी तैयारियां समाप्त हो गई हैं और हमारी पहेली को हल करने का समय आ गया है!

वापसी के साथ बस्ट

बैकट्रैकिंग एक समस्या का समाधान खोजने के लिए एक सामान्य तरीका है जिसमें सभी संभावित विकल्पों की पूरी गणना की आवश्यकता होती है। यहाँ और पढ़ें मैं केवल आपको हमारे कार्यक्रम के बारे में विचार बताऊंगा।
वह यथासंभव लंबे समय तक सूची से एक नया शब्द जोड़ने का प्रयास करेगा, जैसे ही योजना में एक नया शब्द जोड़ना असंभव हो जाता है, अंतिम जोड़े गए शब्द को हटाकर एक कदम पीछे जाएं और दूसरे को जोड़ने का प्रयास करें। इस तरह के एक एल्गोरिथ्म हमारे लिए सभी संभव विकल्प पाएंगे, यह अच्छा लगेगा, लेकिन ऐसा कार्यक्रम बहुत धीरे-धीरे काम करता है, और 10 शब्दों की सूची के लिए, मैं तब तक इंतजार नहीं कर सकता था जब तक इसे निष्पादित नहीं किया गया था।
मदद के लिए हमारी पुस्तक की ओर मुड़ें, मौसम लिखते हैं:

क्राइस-क्रॉस योजनाओं की गुणवत्ता उनकी "कनेक्टिविटी" के समानुपाती होती है, अर्थात, पड़ोसियों के साथ औसत शब्द जितना अधिक घनिष्ठ होते हैं, पहेली उतनी ही रोचक होती है। जब आपका प्रोग्राम लॉन्च हो, तो कनेक्टिविटी बढ़ाने का ख्याल रखें।

कनेक्टिविटी! - यह हमारे कार्यक्रम के अनुकूलन की कुंजी है। कनेक्टिविटी की गणना इस योजना में अपने क्षेत्र के चौराहों की संख्या के अनुपात के रूप में की जाएगी। उसी समय, सभी विकल्पों के माध्यम से जा रहे हैं, हम तुरंत संभावित नहीं इष्टतम (खराब तरीके से जुड़े आंशिक समाधान) को त्याग देंगे।
इस स्तर पर, मैं आपको वास्तविक गणना पद्धति से परिचित कराने के लिए तैयार हूं - शब्दबैकट्रैकिंग ()
यह कई अन्य सहायक विधियों को बुलाएगा। गैर-इष्टतम आंशिक समाधानों को अस्वीकार करने के लिए अस्वीकार () विधि जिम्मेदार होगी। शायद इस दृष्टिकोण के कारण, शब्दों की एक सूची है जिसके लिए कार्यक्रम सबसे इष्टतम समाधान नहीं देगा, लेकिन ज्यादातर मामलों में परिणाम बहुत अच्छा है। यह निर्धारित करने के लिए कि हम किसी समाधान तक पहुंचे हैं या नहीं, स्वीकार () विधि होगी। मैंने यहां सभी सहायक विधियों को पोस्ट नहीं किया, जो लोग स्रोत में देख सकते हैं। खैर, मैं मुख्य गुच्छा शुरू करूँगा।

शब्दबैकैकिंग ()

 /** *      (Backtracking) *   - */ private void wordsBackTracking ( ArrayWord<Word> wordArea, List<String> words ) { if ( accept( wordArea ) ) { ArrayWord<Word> tempWordArea = new ArrayWord<Word>( wordArea ); copyArrayWord( tempWordArea, wordArea ); allWordArea.add( tempWordArea ); mainWordArea = tempWordArea; return; } if ( reject( wordArea, words ) ) return; for ( int i = 0 ; i < words.size() ; i++ ) { List<String> tempWords = new LinkedList<String>( words ); String newWord = tempWords.get(i); tempWords.remove(i); addNewWord( wordArea, tempWords, newWord ); } } /** *   ,    */ private void addNewWord ( ArrayWord<Word> wordArea, List<String> words, String newWord ) { Word existentWord; for ( int k = 0 ; k < wordArea.size() ; k++ ) { existentWord = wordArea.get(k); ///        for ( int i = 0 ; i < existentWord.length() ; i++ ) { for ( int j = 0 ; j < newWord.length() ; j++ ) { if ( existentWord.get(i).value() == newWord.charAt(j) ) { int newOrient = invert( existentWord.orientation() ); int newWordCoord = existentWord.get(i).coord(); int initialVariableCoord = existentWord.coord() - j; Word word = new Word (newWord,newOrient,newWordCoord,initialVariableCoord); ///  ""  -   int interCount = wordArea.intersectCount(); if ( check ( wordArea, word, existentWord.coord() ) ) { wordArea.add ( word ); ///   (0,0)   int minX = wordArea.minX(); int minY = wordArea.minY(); if ( existentWord.orientation() == Orientation.HORIZ ) wordArea.setMinY( initialVariableCoord ); else wordArea.setMinX( initialVariableCoord ); ///   wordsBackTracking ( wordArea, words ); ///    wordArea.remove( wordArea.size()-1 ); wordArea.reset(); wordArea.setMinX( minX ); wordArea.setMinY( minY ); wordArea.setInterCount( interCount ); } } } } } }

wordsBackTracking दो तर्क लेता है: एक क्राइस -क्रॉस शब्द योजना (एक शब्द के साथ, कई या सभी के साथ) और अप्रयुक्त शब्दों की एक सूची। यदि समाधान उपयुक्त है, तो इसे याद रखें। यदि समाधान फ़ंक्शन को उत्कृष्ट रूप से बाहर नहीं निकाल रहा है, तो खोज ट्री को छोटा कर रहा है।
AddNewWord () विधि सर्किट में एक नया शब्द जोड़ने की कोशिश करती है, यह सुनिश्चित करते हुए कि यह क्रॉसवर्ड को संकलित करने के नियमों का उल्लंघन नहीं करता है, जब ऐसा होता है, तो यह पुन: पुनरावृत्ति के अगले स्तर पर चला जाता है । इसलिए इन दो अप्रत्यक्ष रूप से पुनरावर्ती कार्यों में काफी उपयुक्त योजनाएं हैं। शब्दों की बहुत लंबी सूची, मैं पूछने की सलाह नहीं देता, लेकिन पुस्तक से उदाहरण एक-दो है।

मैं वादा किए गए बोनस के बारे में लगभग भूल गया था, अगर आप इसे कॉल कर सकते हैं: जैसा कि एक चौकस पाठक देख सकता है, हमारे सभी समाधान पाए जाते हैं, और फ्रेम पर क्लिक करके आप उन्हें देख सकते हैं। मुझे लगता है कि यह देखना दिलचस्प होगा कि कार्यक्रम कैसे तेजी से सुरुचिपूर्ण समाधान पाता है।
और यहाँ 16 शब्दों का एक और उदाहरण दिया गया है:

आपका ध्यान के लिए धन्यवाद!

के रूप में github पर लिंक का वादा किया
शब्दों के साथ फाइल करें
लीजिए: javac CrissCrossFrame.java
रन: जावा CrissCrossFrame
इस पर, प्रिय पाठक, मुझे अपनी छुट्टी लेने की अनुमति दें और फिर से पढ़ने के लिए धन्यवाद।

एक प्रोग्रामर या पहेली क्राइस-क्रॉस के लिए अध्ययन करें