Arthur Whitney का वन-लाइनर Sudoku सॉल्वर (2011)

 (dfns.dyalog.com)
1 पॉइंट द्वारा GN⁺ 2024-10-07 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Dyalog APL का sudoku, खाली जगहों को 0 मानने वाली puzzle matrix से सभी संभावित solution matrices लौटाता है, और उसी समस्या को APL/K style में कई तरीकों से implement करता है
  • मूल target 9×9 Sudoku है, जिसमें हर 3×3 box, row और column में 1 से 9 तक के अंक बिना दोहराव के होने चाहिए
  • input prob में भरे हुए cells के लिए 1-9 और खाली cells के लिए 0 होता है, और optional left argument shape से 2×3, 3×4 जैसे non-square boxes भी specify किए जा सकते हैं
  • Veli-Matti Jantunen का solving algorithm matrix को vectorize करता है, row·column·box indices बनाता है, फिर candidates घटाते हुए सबसे ज्यादा constrained group से expansion शुरू करता है
  • उदाहरण s33 और s22 में प्रत्येक के 3 solutions हैं, जबकि 3 4 sudoku s34 में 2 solutions हैं; साथ में Arthur Whitney का K 5 one-liner और कई APL reimplementations भी पेश किए गए हैं

Sudoku input और sudoku function का result

  • Sudoku puzzle एक grid है जिसमें 3×3 boxes, 3×3 arrangement में होते हैं, और हर cell या तो खाली होता है या उसमें 1 से 9 तक का अंक होता है
  • solution को तीनों no-duplicate conditions पूरी करनी होती हैं
    • हर 3×3 box में 1 से 9 तक के अंक बिना दोहराव के हों
    • हर 9-cell row में 1 से 9 तक के अंक बिना दोहराव के हों
    • हर 9-cell column में 1 से 9 तक के अंक बिना दोहराव के हों
  • prob matrix भरे हुए cells के लिए 1-9 और खाली cells के लिए 0 इस्तेमाल करती है
  • optional left argument shape, default square न होने वाली puzzle का box shape specify करता है
    • 6×6 matrix में sub-region 2×3 हो तो इसे 2 3 sudoku mat के रूप में call किया जाता है
  • result एक vector है जिसमें सभी solution matrices होते हैं
    • अगर कोई solution न हो तो ⍬ लौटाता है
    • error situation '' से दिखाई जा सकती है, और document में लिखा है कि “यह नहीं होना चाहिए, लेकिन result की संख्या बहुत ज्यादा होने पर” ऐसा हो सकता है

Veli-Matti Jantunen solution का flow

  • algorithm Sudoku matrix को vector की तरह handle करता है, और rows·columns·Sudoku regions को अलग-अलग index vectors से represent करता है
  • basic checks पास करने के बाद candidate list में alternatives को एक-एक करके check करता है
  • हर step में सभी cells के possible elements filter किए जाते हैं
    • अगर किसी भी cell में कोई possible value नहीं है, तो उसे solution candidate से exclude कर दिया जाता है
    • अगर किसी cell में candidate numbers दो या अधिक हैं, तो सबसे constrained group से cell चुना जाता है और उस cell के candidate combinations को list में जोड़ा जाता है
    • अगर सभी cells में केवल एक-एक number बचता है, तो उसे solution माना जाता है और अगले candidate पर बढ़ता है
  • उसी section में मौजूदा Sudoku table को दूसरे table में shuffle करने वाला Shuffle function भी शामिल है

Arthur Whitney one-liner और alternative implementations

  • David Crossley का alternative sudoku implementation input के रूप में N×N setting लेता है और उन cases को target करता है जहाँ box size N*÷2 integer हो
    • input एक valid arrangement होना चाहिए, जिसमें कुछ cells में 1 से N तक के numbers हों और बाकी में 0
    • हर row, column और box में result में 1 से N तक के सभी numbers शामिल होने चाहिए
    • implementation के अंदर valid, search, rules, sole, singles, uniques, matches, NinN, setup जैसे helper functions हैं
  • Arthur Whitney का K 5 solution एक line code के रूप में प्रस्तुत है
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last ने Whitney के code को D-function में port करके sudoku implementation दिया है
  • Morten Kromberg की rewrite K के कुछ components को explicitly define करती है, जिससे यह original के ज्यादा करीब रूप लेती है
    • K version की तरह यह matrix नहीं बल्कि 81-element vector input और return करती है
  • Roger Hui का Sudoku implementation ज्यादा generalized form में है और non-square puzzles भी handle करता है
    • svec solution vector बनाता है, और pvex तथा pvec possible placements को expand करते हैं
    • avl possible numbers की list बनाता है, और emt खाली cells के row·column indices ढूंढता है
    • rcb, box, cmap, CMAP row·column·box conflict relationships construct करते हैं

Example puzzles और solution count

  • s33 एक 9×9 sample problem है, और sudoku s33 result में 3 solutions हैं
  • sbox function, inner boxes को divide करके Sudoku grid को पढ़ने में आसान तरीके से display करता है
    • 0 को dot (·) के रूप में दिखाया जाता है
    • box boundaries बनी हुई character matrix form में output होता है
  • s22 एक 4×4 sample problem है, और sbox¨ sudoku s22 result में 3 solutions हैं
  • s34 एक sample problem है जो 3×4 boxes इस्तेमाल करता है
    • 3 4 sbox s34 से problem को box-separated form में display किया जाता है
    • 3 4 sudoku s34 result में 2 solutions हैं

Reference links और साथ देखने लायक items

  • sudoku_bfs इस algorithm को दिखाने वाले example से link होता है
  • TryAPL के “Learn” में step-by-step demo है: http://www.TryAPL.org
  • execution behavior दिखाने वाला video है: http://www.youtube.com/watch?v=DmT80OseAGs
  • साथ देखने लायक items के रूप में queens, sudoku_bfs, X, sudokuX दिए गए हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-10-07
Hacker News टिप्पणियां

  • वह लाइन K में लिखी गई है। K एक भाषा है जिसे Arthur Whitney ने APL और Scheme के आधार पर बनाया था
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • कभी-कभी मैं code complexity का अंदाज़ा code की लाइनों की संख्या की तुलना नीचे वाले output से करके लगाता हूं
    tar -cf - . | gzip | base64 | wc -l
    यानी एक तरह से यह देखना कि “यह कितनी अच्छी तरह compress होता है?” APL देखकर मुझे वह समय याद आता है जब गलती से gzip output terminal पर भेज दिया हो
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    यह देखकर प्रभावशाली लगता है कि कुछ लोग ऐसे code को follow करते हुए “क्या bug ढूंढ सकते हो?” तक करते हैं। यह compressed binary data जैसा लगता है, जहां पहले से सबके पास वही dictionary हो

    • मुझे सचमुच जिज्ञासा है कि APL programmers maintainability और readability के बारे में कैसे सोचते हैं। क्या वे code में बहुत बारीकी से comments डालते हैं या अलग से documentation रखते हैं
    • “क्या bug ढूंढ सकते हो?” की बात हो तो तुरंत कुछ चीज़ें दिखती हैं। बंद न हुआ single quote और right operand के बिना ∘ जैसी syntax errors हैं, और n n←⍴⍵ n को दो बार set करता है, जो ऐसा संकेत लगता है कि ⍵ को 2-dimensional माना जा रहा है, लेकिन मंशा के हिसाब से _ n←⍴⍵ या n←⊃⌽⍴⍵ ज़्यादा स्वाभाविक है
      साथ ही ⊥ में, अगर ⍴⍵ single integer या खाली vector नहीं है तो error आएगी, इसलिए आखिर में यह n←⍴⍵ से अलग नहीं रह जाता और और confusing बनता है। कई redundant , और ↑⍵ भी हटाए जा सकते हैं, और पूरा expression असल में लगभग p←(n+1)⍴⊂⍳n×n←⍴⍵ जैसा हो जाता है, यानी 1..n² vector की n+1 copies देने वाली संरचना
      ऊपर से अजीब दिखने के बावजूद, symbols और basic operations सीख लें तो APL हैरानी की बात है कि काफी सीधा है। हालांकि fluent होने में समय लगता है, और उस मुकाम पर पहुंचने पर यह superpower जैसा महसूस होता है
    • यह देखते हुए कि अरबों लोग non-English characters पढ़ते और लिखते हैं, मुझे नहीं पता कि APL पढ़ने वाले लोग होना ज्यादा खास या चौंकाने वाली बात है या नहीं

  • यह बात सही है कि भाषा के समर्थक speed, array processing की आसानी, और expressive syntax पर जोर देते हैं
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • हालांकि पता नहीं maintainability तक इसका advantage है या नहीं

  • Code की lines की संख्या अच्छा metric नहीं है, क्योंकि हर भाषा में lines लिखने का तरीका अलग होता है
    बेहतर माप यह हो सकता है कि “constants” या “function calls” जैसे अर्थपूर्ण non-terminal symbols के आधार पर syntax tree nodes की संख्या गिनी जाए। उससे भी आगे, उस tree की depth और branching factor को भी ध्यान में लिया जाए तो और अच्छा होगा

    • सिर्फ semantics ही मायने रखती है, ऐसा कहना मुझे स्वीकार करना मुश्किल लगता है। भाषा का user experience, clarity, सोचने का तरीका और expressiveness भी महत्वपूर्ण हैं, और code का visual size इन पर असर डालता है
      One-line solution screen space लगभग नहीं घेरता, इसलिए complex problems से निपटते समय यह बड़ा advantage बनता है। आंखों को screen के भीतर हिलाना, files के बीच जाकर scroll करने से कहीं कम भारी है, और cognitive load मायने रखता है
      K न जानते हुए भी, constants अगर साथ-साथ दिखें तो ऐसा लगता है जैसे problem के direct data representation का इस्तेमाल हो रहा हो। अगर K culture ऐसे code को बढ़ावा देता है और सोच को directness और simplicity की ओर झुकाता है, तो मैं अपनी team में ऐसा special sauce लाना चाहूंगा
    • Built-in functions और system library APIs ऐसे metrics को बिगाड़ देते हैं। उदाहरण के लिए HQ9+ “Hello, world!” output के मामले में काफी अच्छा है
      https://cliffle.com/esoterica/hq9plus/
    • Information amount मापने का पसंदीदा metric, algorithmic information theory की तरह, बस bits की संख्या है
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • यह one-line code साफ तौर पर मज़ाक में बनाया गया है, और कोई भी तर्कसंगत रूप से यह दावा नहीं कर रहा कि यह पढ़ने में आसान code है। यहां definition पर बहस करना असली बात से चूकना है। मुद्दा यह है कि “K में बेहद dense code लिखा जा सकता है”

  • मैं अक्सर सोचता था कि APL/K जैसी languages इस्तेमाल करने पर programmer वाकई problem के बारे में ज़्यादा efficiently सोच पाता है या नहीं

    • kdb+/Q programmer के तौर पर, मेरे हिसाब से यह problem type पर निर्भर करता है। Data arrays से काम करते समय दो arrays को जोड़कर average निकालने को avg a+b के रूप में सोचना और लिखना निश्चित रूप से आसान है
      Array-centric न होने वाली भाषा में boundary checks, बड़े for loops, sum और count रखने के लिए temporary variables वगैरह की जरूरत पड़ने की संभावना ज्यादा है। C जैसी भाषा में जो काम करीब 6 lines का होगा, Q में वह 6 characters में हो जाता है
      हालांकि हर भाषा में ऐसी सुविधाएं होती हैं जो कुछ खास problems पर बेहतर reasoning में मदद करती हैं। Algebraic data types और pattern matching वाली functional languages, जैसे OCaml या F#, बड़े switch या if-else-if से बेहतर हैं, और async/await जैसी syntactic sugar वाली languages concurrency handling में फायदेमंद हैं
    • जिन problem families को आसानी से vectorize किया जा सकता है, उनमें array-centric languages सोच और solution को ज़्यादा efficient बना देती हैं। क्योंकि वे data structures और iteration के details को abstract कर देती हैं
      Quant के तौर पर काम करते समय मैंने kdb+/q को 5 साल से ज्यादा mid-frequency strategies में खूब इस्तेमाल किया, लेकिन जब order book calculations जैसे high-frequency trading वाले हिस्से में गया, जो आसानी से या efficiently vectorize नहीं होते, तो array-centric language को जारी रखना उलटे problem reasoning को और complex बनाने लगा
    • Dyalog नाम की आधुनिक APL-family language की एक talk में मैंने यह दावा सुना था कि यह notation कुछ खास idioms को ज्यादा आसानी से पहचानने देता है
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      वह हिस्सा compiler context में था, लेकिन पूरी talk Dyalog और APL को mathematical notation system के रूप में देखती है। मुख्य flow यह है कि सामान्य code की तुलना में mathematical expressions को optimize करना आसान हो सकता है
    • Hillel Wayne अपने newsletter में इस topic को कभी-कभी उठाते हैं। मैं इस बात से convinced हूं कि वे सचमुच कुछ problems को array languages में बेहतर सोचते हैं, लेकिन वह experience कैसा लगता है, यह अभी भी ठीक से imagine नहीं कर पाता
    • Array-language style की अच्छी बात यह है कि algorithm variants पर चर्चा करते समय संबंधित code snippet कुछ characters का होता है, इसलिए सीधे body text में आ जाता है। वही बात कहने के लिए जिन traditional vertical languages में कई lines या दर्जनों lines चाहिए, उनमें code blocks और explanation text को लगातार मिलाना पड़ता है

  • यहां सबसे अहम बातों में से एक यह है कि ऊपर दिया गया problem generator बहुत स्पष्ट है। यही J और K समेत Iverson-style symbolic languages और दूसरी languages के बीच का फर्क है
    इसमें one-line solution जैसी शान और ताकत नहीं है, लेकिन सख्त comments के बिना भी यह काफी साफ-सुथरा और समझ में आने लायक है। हालांकि मुझे नहीं लगता कि lamp अच्छा comment symbol है
    one-line solution हैरान करने वाला है, और tacit programming दिमाग घुमा देने वाली हद तक शानदार है। glyph-based language की अनोखी compression को functional programming को समझाने और लागू करने के लिए इस्तेमाल करना, और फिर उसे पूरे arrays पर लागू करना—यह विचार genius है
    https://www.jsoftware.com/papers/fork.htm

    • सिर्फ इसलिए कि आप सब कुछ बिना spaces के एक ही line में लिख सकते हैं, इसका मतलब यह नहीं कि आपको ऐसा करना ही चाहिए
      बेशक, अगर वह क्षमता हटा दी जाए तो लोगों को ज्यादा verbose code लिखने के लिए मजबूर किया जा सकता है, लेकिन तब interactive tool के रूप में इसकी ताकत काफी घट जाएगी। Iverson-style languages बहुत छोटा code लिखने देती हैं, इसलिए interactive work में उपयोगी होती हैं। उस समय का code तो save भी नहीं होता, इसलिए वह सचमुच write-only code होता है
      जब file में जाने वाला code लिख रहे हों, तो अपनी पसंद की style चुन सकते हैं, और उस समय मैं कम compressed तरीके से लिखने की सलाह दूंगा। फिर भी Iverson-style languages verbose style में लिखने पर भी ज्यादातर languages की तुलना में काफी छोटा code देती हैं

  • ज्यादातर लोग symbols की वजह से हिचकते हैं, लेकिन मेरी समस्या वह नहीं थी
    मुझे APL और array languages पसंद हैं, और उनसे सीखी चीजों ने दूसरी languages इस्तेमाल करने में भी काफी मदद की। लेकिन वे मेरे रोजमर्रा के tools नहीं बने; symbols की वजह से नहीं, बल्कि 3–4 साल तक बीच-बीच में इस्तेमाल करने के बाद मैं एक ऐसी दीवार से टकराया जिसे पार नहीं कर पाया
    दूसरी languages में आम तौर पर किसी problem को मोटे तौर पर हल करने की एक general approach होती है, और बाद में जब उस problem की “trick” मिल जाए तो उसे ज्यादा elegant और efficient बनाया जा सकता है। APL में ऐसा temporary workaround नहीं लगा; ऐसा लगा कि या तो आपको trick पता है या नहीं पता
    मुझे ठीक-ठीक नहीं मालूम कि सच में ऐसा ही है, या काफी tricks सीखने के बाद problem-solving intuition बन जाती है, या अंत तक सिर्फ tricks ही रहती हैं, या फिर मैंने कोई core strategy document नहीं पढ़ा

    • यह अहसास गलत नहीं है। array languages सीखते समय ऐसा impression मिलना बहुत आसान है। लंबे समय से इस्तेमाल करने वाला कोई व्यक्ति problem देखकर कह सकता है, “इतना complex क्यों हल किया, बस ⍸⍣¯1 इस्तेमाल कर लेते?” जबकि शायद किसी ने आपको कभी बताया ही नहीं कि ⍸ का inverse operation होता है और उसे कैसे इस्तेमाल करते हैं
      मैं आज भी कई सालों से ऐसी languages इस्तेमाल कर रहा हूं, लेकिन कुछ array programmers जो code walls बनाते हैं, वे थोड़े intimidating लगते हैं। मैं समझता हूं कि वे ऐसा क्यों लिखते हैं, लेकिन निजी तौर पर मुझे code में थोड़ा whitespace होना पसंद है
      मैं APL-based array language बना रहा हूं, और शुरुआती लक्ष्यों में से एक था कि if statements जैसी चीजें इस्तेमाल करने वाले beginners को punish न किया जाए और imperative style को first-class citizen बनाया जाए। मुझे यह style pure APL style और सामान्य imperative languages के बीच की चीज लगती है
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • जिस दीवार की बात की गई है, वह मौजूदा APL onboarding path की वास्तविक समस्या है। पिछले साल मैंने इसी topic पर talk भी दी थी, और यह बिल्कुल भी व्यक्ति की गलती नहीं है
      फिर भी यह language की अपनी limitation भी नहीं है। मेरे अनुभव में उस दीवार को तोड़ने की प्रक्रिया ही paradigm के click होने की प्रक्रिया थी। एक साल तक YAML parser prototype बनाते हुए करीब 500 घंटे hacking करने के बाद ही चीजें जुड़नी शुरू हुईं
      मुख्य बात डेटा-चालित design principles, अच्छे notation की Iverson-style खूबियों को software architecture में ठोस रूप से इस्तेमाल करने का तरीका, और idioms व वे domain concepts को कैसे व्यक्त करते हैं—इनसे परिचित होने का संयोजन लगती है
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • इस विषय पर एक video है
    https://www.youtube.com/watch?v=DmT80OseAGs
    solution को https://tryapl.org/ पर खुद आजमा सकते हैं

  • इस one-liner की तुलना अलग-अलग programming languages के code golf solutions से करना दिलचस्प हो सकता है
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • दिलचस्प बात यह है कि एक खास problem, यानी brute-force Sudoku solver, का नंबर 1 solution दरअसल K snippet है। नंबर 2 K solution की नकल से बना J solution है
      https://codegolf.stackexchange.com/a/5030