ตัวแก้ Sudoku แบบบรรทัดเดียวของ Arthur Whitney (2011)

 (dfns.dyalog.com)
1 คะแนน โดย GN⁺ 2024-10-07 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

อัลกอริทึมแก้ปัญหา Sudoku

  • คำอธิบายปัญหา Sudoku

    • ปริศนา Sudoku ประกอบด้วยกล่องขนาด 3×3 จำนวน 9 กล่องในกริด 3×3 โดยแต่ละช่องอาจว่างเปล่าหรือมีตัวเลขตั้งแต่ 1 ถึง 9
    • ในแต่ละกล่อง 3×3, แถวทั้ง 9 แถว และคอลัมน์ทั้ง 9 คอลัมน์ ต้องมีตัวเลข 9 ตัวโดยไม่ซ้ำกัน
    • มีการยกตัวอย่างโจทย์และวิธีแก้ไว้ให้

  • ภาพรวมของอัลกอริทึม

    • ประมวลผลเมทริกซ์เป็นเวกเตอร์ และแสดงแถว คอลัมน์ และพื้นที่ของ Sudoku ด้วยเวกเตอร์ดัชนี
    • ตรวจสอบพื้นฐานของปริศนา และกรององค์ประกอบที่เป็นไปได้เพื่อค้นหาคำตอบ
    • หากช่องว่างอยู่ จะย้ายไปยังรายการถัดไป และหากช่องมีตัวเลขได้หลายค่า จะเลือกจากกลุ่มที่แคบที่สุดแล้วเพิ่มลงในรายการ
    • หากทุกช่องมีตัวเลขเพียงค่าเดียว แสดงว่าพบคำตอบแล้ว

  • บันทึกทางเทคนิค

    • เป็นโซลูชันที่ Veli-Matti Jantunen นำเสนอ โดยสามารถใช้ ⍺ เพื่อแทนสี่เหลี่ยมของ Sudoku ได้
    • ผลลัพธ์จะคืนค่าเป็นเวกเตอร์ของคำตอบทั้งหมด, เป็น ⍬ หากไม่มีคำตอบ, และเป็น '' หากมีข้อผิดพลาด
    • อัลกอริทึมนั้นเรียบง่าย โดยประมวลผลเมทริกซ์เป็นเวกเตอร์และกรององค์ประกอบที่เป็นไปได้เพื่อค้นหาคำตอบ

  • แนวทางอื่น

    • มีการนำเสนอการเขียนโค้ดทางเลือกของ David Crossley และ Arthur Whitney
    • มีการอธิบายรูปแบบการเขียนโค้ดและแนวทางที่หลากหลาย

  • ตัวอย่างและการใช้งาน

    • มีตัวอย่างหลากหลายในการแก้ปัญหา Sudoku
    • ยังมีฟังก์ชันสำหรับแยกกล่องภายในเพื่อให้อ่านโจทย์ Sudoku ได้ง่ายขึ้น

สรุปโดย GN⁺

  • มีการแนะนำอัลกอริทึมและสไตล์การเขียนโค้ดที่หลากหลายสำหรับการแก้ปัญหา Sudoku
  • ปริศนา Sudoku มีประโยชน์ในการพัฒนาการคิดเชิงตรรกะและความสามารถในการแก้ปัญหา
  • แนวทางที่หลากหลายช่วยเพิ่มความยืดหยุ่นในการแก้ปัญหา
  • ปริศนาที่มีลักษณะคล้าย Sudoku และน่าสนใจเช่น Kakuro, KenKen

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-07
ความคิดเห็นจาก Hacker News
  • ภาษา K เป็นภาษาที่ Arthur Whitney สร้างขึ้นโดยอิงจาก APL และ Scheme โดยเน้นความเร็ว ความสามารถในการประมวลผลอาร์เรย์ และไวยากรณ์ที่สื่อความหมายได้มาก
  • เมื่อวัดความซับซ้อนของโค้ด มีการเปรียบเทียบจำนวนบรรทัดของโค้ดกับระดับการบีบอัด
    • โค้ด APL ให้ความรู้สึกเหมือนข้อมูลไบนารีที่ถูกบีบอัด และรู้สึกทึ่งกับคนที่สามารถเข้าใจมันได้
  • จำนวนบรรทัดของโค้ดไม่ใช่เกณฑ์วัดที่ดี เพราะแต่ละภาษามีการใช้บรรทัดต่างกัน
    • วิธีวัดที่ดีกว่าคือพิจารณาจำนวนโหนดของ syntax tree รวมถึงความลึกและปัจจัยการแตกแขนง
  • ความชัดเจนของปัญหาเป็นสิ่งสำคัญ และภาษากลุ่ม Iversonian (รวมถึง J และ K) ก็แตกต่างจากภาษาอื่นในจุดนี้
    • วิธีแก้แบบบรรทัดเดียวชวนให้ทึ่ง และมีประโยชน์ในการอธิบายและประมวลผลอาร์เรย์อย่างมีประสิทธิภาพ
  • มีความเห็นว่าโปรแกรม K ควรลงท้ายด้วย QED และสงสัยว่ามีความเกี่ยวข้องกับ KQED หรือไม่
    • KQED เป็นพาร์ตเนอร์ของ PBS ในเขต Bay Area
  • มีคนสงสัยว่าภาษาอย่าง APL/k ช่วยให้คิดปัญหาได้อย่างมีประสิทธิภาพมากขึ้นหรือไม่
  • การเรียน APL และภาษาอาร์เรย์ช่วยกับภาษาอื่นได้ แต่สุดท้ายก็ไม่ได้ใช้เป็นประจำในชีวิตประจำวัน
    • APL แก้ปัญหาได้ยากหากไม่รู้วิธีแก้ปัญหาเฉพาะทางอยู่ก่อนแล้ว
  • มีวิธีแก้ที่ดีกว่าวิธีที่ไม่มีประสิทธิภาพซึ่งเคยเห็นในคู่มือออกแบบอัลกอริทึมบางเล่ม
    • ได้เขียนบล็อกโพสต์เกี่ยวกับเรื่องนี้ไว้ในปี 2015
  • วิธีแก้ Sudoku ด้วย Scryer Prolog อ่านง่ายและทรงพลัง และมีความสามารถด้านการแก้ constraint ที่ยอดเยี่ยม
    • Scryer Prolog เป็น Prolog สมัยใหม่ที่สอดคล้องกับ ISO และมีประสิทธิภาพสูง