หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

ปริศนาม้าลาย

ปัจจุบันในปี 2024 โปรเจ็กต์ส่วนใหญ่ไม่ได้รับการบำรุงรักษา ฉันใช้มันเป็นสนามเด็กเล่นสำหรับบางสิ่งที่ฉันอยากลอง แต่ฉันไม่แนะนำให้ใครสร้างสิ่งนี้ขึ้นมา

ตัวอย่างปริศนา

จำปริศนาตรรกะที่มีลักษณะเช่นนี้ได้ไหม? พวกเขามีเบาะแสเช่น:

  • มีบ้านหลังหนึ่งระหว่าง Tushar และ Maui

  • วิดีโอเกมโปรดของ Ruby คือโปเกมอน

  • คนดื่มชัยไม่ชอบสีฟ้า

ฉันชอบสิ่งเหล่านี้ตั้งแต่ยังเป็นเด็ก และการดูการพูดคุย PyCon 2019 ของ Raymond Hettinger เป็นแรงบันดาลใจให้ฉันกลับมาทบทวนปัญหาเหล่านี้อีกครั้ง เขาแสดงให้เราเห็นว่าจะแก้ปัญหาอย่างไร ฉันต้องการเรียนรู้วิธีสร้างพวกมัน

ด้วยการใช้ Python สมัยใหม่และตัวแก้ปัญหาความพึงพอใจแบบจำกัด (SAT) โปรเจ็กต์นี้สามารถใช้เพื่อสร้างปริศนาม้าลายแบบสุ่มได้

โครงสร้าง

โปรเจ็กต์นี้ใช้ Python 3.12 และ Poetry

จุดเข้าสู่โปรเจ็กต์นี้คือ src/main.py ; ดังนั้นให้รันด้วย [poetry run] python -m src.main เราใช้คำถามเพื่อสร้าง CLI ที่มีการโต้ตอบแบบง่ายๆ

ไฟล์สำคัญอื่นๆ ได้แก่:

  • puzzle.py มีคลาส Puzzle หลัก ซึ่งส่วนใหญ่จะติดอยู่กับเบาะแสและองค์ประกอบของปริศนา

  • clues.py กำหนดเบาะแส (คำสั่งระดับสูงกว่าที่เราสามารถแปลงเป็น CNF) และโรงงานหลายแห่งเช่น found_at หรือ same_house ; generate.py มียูทิลิตี้สำหรับสร้างเบาะแส

  • elements.py และ traptor_elements.py มีองค์ประกอบปริศนาต่างๆ

สุดท้าย sat_utils.py มียูทิลิตี้พื้นฐานสำหรับการโต้ตอบกับ pycosat ของตัวแก้ปัญหา SAT รหัสนี้เขียนเกือบทั้งหมดโดย Raymond Hettinger สำหรับการพูดคุยในปี 2019 ของเขา (ขอบคุณ!)

ตัวอย่าง

 ❯ บทกวีรัน python -m src.main? ปริศนามีขนาดใหญ่แค่ไหน? (ใช้ปุ่มลูกศร)
 » 5
   4
   3? เลือกประเภทกับดัก (ใช้ปุ่มลูกศร)
   - เขตร้อน
 - ตำนาน? - ปริศนาควรมีสมูทตี้ด้วยหรือไม่? (ใช้ปุ่มลูกศร)
 " ใช่
   เลขที่? - ปริศนาควรมีฝาขวดด้วยหรือไม่ (ใช้ปุ่มลูกศร)
 " ใช่
   เลขที่

เบาะแส
-----# ... ละเว้นข้อความรสชาติบางส่วน ...1. Lesser Traptor และ Swamp Traptor อยู่ในบ้านเดียวกัน
2. Ancient Traptor จะอยู่ทางด้านซ้ายของ Chocolate Smoothie
3. Ancient Traptor และ Lemon Smoothie อยู่ในบ้านเดียวกัน
4. Volcano Traptor อยู่ทางด้านซ้ายของ Restless Traptor โดยตรง
5. Cave Traptor และฝาขวดสีเขียวอยู่ในบ้านหลังเดียวกัน
6. มีบ้านสองหลังระหว่าง Lake Traptor และ Snapper Traptor
7. ฝาขวดสีเขียวและ Fierce Traptor อยู่ในบ้านเดียวกัน
8. มีบ้านหลังหนึ่งอยู่ระหว่างฝาขวดดำกับสมูทตี้มะพร้าว
9. มีบ้านหลังหนึ่งอยู่ระหว่าง Lesser Traptor กับกีวีสมูทตี้
10. Dweller Traptor และ Chocolate Smoothie อยู่ในบ้านเดียวกัน
11. ฝาขวดสีแดงและ Dweller Traptor อยู่ในบ้านเดียวกัน
12. ฝาขวดสีแดงอยู่ทางซ้ายมือของ Hoarder Traptor
13. มีสองบ้านระหว่างสมูทตี้ Starfruit และฝาขวดสีเหลือง
14. Lake Traptor และ Black bottlecaps อยู่ในบ้านหลังเดียวกัน
15. Stalker Traptor และ Fierce Traptor อยู่ในบ้านเดียวกัน

                                                             สารละลาย

┃ Nest ┃ MythicalTraptorPrimary ┃ MythicalTraptorSecondary ┃ MythicalTraptorTertiary ┃ สมูทตี้ ┃ ฝาขวด ┃

│ 1 │ กับดักที่ดุร้าย │ กับดักถ้ำ │ กับดักสตอล์กเกอร์ │ สมูทตี้สตาร์ฟรุต │ ฝาขวดสีเขียว │
│ 2 │ Traptor โบราณ │ Traptor ทะเลสาบ │ Traptor ตีนตะขาบ │ สมูทตี้มะนาว │ ฝาขวดสีดำ │
│ 3 │ Lesser Traptor │ Swamp Traptor │ Dweller Traptor │ ช็อคโกแลตสมูทตี้ │ ฝาขวดสีแดง │
│ 4 │ กับดักที่ยิ่งใหญ่ │ กับดักภูเขาไฟ │ กับดักนักสะสม │ สมูทตี้มะพร้าว │ ฝาขวดสีเหลือง │
│ 5 │ กับดักกระสับกระส่าย │ กับดักภูเขา │ กับดักปลากะพง │ สมูทตี้กีวี │ ฝาขวดสีน้ำเงิน │

งานในอนาคต

ในเดือนกุมภาพันธ์ 2024 ฉันต้องพิจารณาสิ่งใดว่า "เสร็จสิ้น"

  • เพิ่มเทมเพลต HTML เนื่องจากไซต์ที่ฉันสร้างเหล่านี้กำหนดให้ฉันต้องรวมสิ่งต่าง ๆ เช่นแท็ก BR

  • ปรับปรุงไวยากรณ์ในผลลัพธ์ เช่น การใช้อักษรตัวพิมพ์ใหญ่ในข้อความแต่งกลิ่น

  • เพิ่มทรัพยากรส่วนหัว/ส่วนท้ายที่ฉันคัดลอก/วางลงในการส่ง

บางทีสักวันหนึ่งฉันจะพิจารณาเว็บอินเตอร์เฟส ฉันสามารถยกโปรเจ็กต์โดยใช้ไพโอไดด์ได้หรือไม่ หรือไพโคแซตแบบ C จะทำให้เกิดปัญหาได้หรือไม่ แล้วอินเทอร์เฟซการเขียนโปรแกรมลอจิกอื่นๆ เช่น PySAT, การเขียนโปรแกรมชุดคำตอบ หรืออื่นๆ จากเธรด HN นี้ล่ะ

สิ่งเหล่านี้อาจเกิดขึ้นได้ แต่ในที่สุดโครงการนี้ก็มาถึงจุดที่ฉันพอใจแล้ว ดังนั้นฉันจึงตื่นเต้นที่จะแบ่งปันและเขียนเกี่ยวกับเรื่องนี้

บันทึกการเปลี่ยนแปลงที่ไม่สมบูรณ์

18-02-2024: ปรับปรุงผลลัพธ์

2/18: ทำให้ผลลัพธ์ง่ายขึ้น ลดรายละเอียดลง สวยขึ้น อัปเดต README นี้ด้วยการจัดรูปแบบและการเปลี่ยนแปลงใหม่ ใช้เครื่องกำเนิดปริศนาเพื่อสร้างปริศนาใหม่ในที่สุด!

17/2/2017: อัปเดตลายเซ็นปริศนาให้ยอมรับวิธีแก้ปัญหาเท่านั้น โดยอนุมานองค์ประกอบและคลาสองค์ประกอบจากนั้น เพิ่มจอแสดงผลที่ดีกว่าสำหรับโซลูชัน

25-11-2566 และ 26-11-2566: ลดความซับซ้อน

11/26: ทำความสะอาดตรรกะการสร้างปริศนา/วิธีแก้ปัญหา ให้ผู้ใช้เลือกขนาดปริศนา

25/11: ตั้งชื่อประเภททั่วไปบางประเภทเป็นนามแฝงประเภท (ขอบคุณ Python 3.12) ใช้การบันทึกแทนการพิมพ์

19-11-2023: ทดสอบต่อ

เพิ่มการทดสอบประเภทเบาะแสภายใน generate.py

แก้ไขข้อผิดพลาดที่ฉันแนะนำใน clues.py ไฟล์นั้นเข้าใจยากมาก แต่ก็ยากที่จะเขียนการทดสอบหน่วยด้วย การแปลงนิพจน์บูลีนเป็น CNF ด้วยมือไม่ใช่เรื่องสนุก

ปรับน้ำหนักของเบาะแสในการแก้ปัญหา เตรียมบูรณาการปริศนาและคลาสการแก้ปัญหา

ลบการเลือกสมูทตี้แบบช่องทำเครื่องหมายออก เนื่องจากจะกีดขวางเมื่อพยายามสร้างปริศนาอย่างรวดเร็ว

13-11-2023: ทดสอบและปรับโครงสร้างใหม่ต่อไป

เพิ่มการทดสอบต่อไป เสร็จสิ้นการทดสอบหน่วยสำหรับ sat_utils.py และเริ่มสองสามรายการสำหรับ clues.py แม้ว่าไฟล์นั้นจะทดสอบได้ยากมากเนื่องจากความยากลำบากในการแปลง DNF-to-CNF ด้วยคอมพิวเตอร์ด้วยมือ

ขั้นตอนต่อไปคือการรวมปริศนาและวิธีแก้ปัญหาเข้าด้วยกัน สร้าง __repr__ ที่ดีขึ้น และลดความซับซ้อนของวิธีการแสดงขนาดปริศนา (แอตทริบิวต์บน Puzzle tuple ของ ints 1 ถึง N เพียงตัวเลข n_houses ฯลฯ)

12-11-2023: การอัปเดตเครื่องมือ

ลบสีดำและใช้ผ้าสำหรับจัดรูปแบบ อัปเดตการอ้างอิง เพิ่ม CLI ใหม่ด้วยการใช้งานที่เรียบง่ายและชัดเจนยิ่งขึ้น python -m src.main

05-06-2023: การปรับปรุงการพิมพ์

เปลี่ยนชื่อ SATLiteral -> PuzzleElement (สมูทตี้ แมว ฯลฯ ); สิ่งนี้ทำให้ชัดเจนว่ามันไม่ใช่ตัวอักษรในความหมายแบบบูลีน แต่เป็นชื่อของตัวละครในปริศนาแทน

สร้าง SATLiteral ประเภทใหม่ (ซึ่งเป็น str ในเสื้อโค้ทกันฝน) สิ่งนี้แสดงถึงตัวอักษรในความหมายตัวแปรบูลีน เช่น "Value el is at house loc " หรือ "Value el is not at house loc " ภายใน สิ่งเหล่านี้จะแสดงด้วยจำนวนเต็ม i และค่าที่เป็นลบ -i

ใช้ (ใหม่) SATLiteral เป็นประเภทการส่งคืนของ comb(el: str, loc: int) -> SATLiteral การแมปองค์ประกอบปริศนากับตัวอักษร และ neg(el: SATLiteral) -> SATLiteral เพื่อลบล้างตัวอักษร

เพิ่ม Clause: tuple[SATLiteral, ...] แทน "∨" (บูลีน OR; การแยกส่วน) ของตัวอักษร; เช่น (1, -5, 6) เป็นคำแยกที่ระบุว่า x_1 เป็นจริง x_5 ไม่จริง หรือ x_6 เป็นจริง

เพิ่ม ClueCNF: list[Clause] ซึ่งแสดงถึง "∧" (boolean AND; การเชื่อม) ของ Clause s ปริศนาใน CNF คือ "AND ของ ORs" ("∧ ของ ∨s" หรือ "∧ ของ Clauses")

03-06-2023: ปรับปรุงการแสดงผลการพิมพ์

พิมพ์ปริศนาให้ชัดเจนยิ่งขึ้น ลดความฟุ่มเฟือยของการลดเบาะแส

01-06-2023: การสร้างแบบสุ่ม

สุ่มสร้างปริศนา (พร้อมเมล็ด) ในการวิ่งแต่ละครั้ง

25-05-2023: การล้างข้อมูล

ย้ายตัวอย่างไปไว้ในไฟล์ของตัวเอง อัปเดตเป็น Python 3.12 (เบต้า) เพิ่มกฎผ้าสำลีเพิ่มเติม เคลียร์สินค้านำเข้า.

25-04-2566: ฟื้นคืนชีพจากความตาย

เพิ่มเครื่องมือ dev (black, ruff, pyright); run black & ruff ในการคอมมิตล่วงหน้า อัพเดทบางประเภท.

คำจำกัดความ

  • "∧" คือบูลีน AND

  • "∨" คือบูลีนหรือ

  • ข้อคือ "∨ ของตัวอักษร"

  • CNF คือ "∧ ของข้อ" หรือเทียบเท่ากับ "∧ ของ ∨s" ("และของ ORs")

ในทางตรงกันข้าม DNF คือ "∨ ของ ∧s" DNF คือ คำตอบ สำหรับปัญหา SAT DNF ของ "A หรือ B หรือ C" อ่านว่า A, B และ C เป็นงานที่ได้รับมอบหมายที่ถูกต้อง (น่าพอใจ) ทั้งหมด การแปลง CNF เป็น DNF จึงเป็น NP-hard เนื่องจากจาก DNF คุณสามารถอ่านวิธีแก้ปัญหาของ CNF ได้

CNF คือ ∧ ของ ∨s โดยที่ ∨ อยู่เหนือตัวแปรหรือการปฏิเสธ (ตัวอักษร) ∨ ของตัวอักษรเรียกอีกอย่างว่าอนุประโยค DNF คือ ∨ ของ ∧s; ∧ ของตัวอักษรเรียกว่าเทอม

นั่ง

หัวใจสำคัญของโครงการนี้คือการแสดงปริศนาม้าลายว่าเป็นปัญหา ความพึงพอใจแบบบูลีน (SAT) (Wikipedia

ปัญหา 3-SAT เป็นที่รู้กันว่าเป็น NP-complete นั่นคืออาจไม่มีอัลกอริธึมเวลาพหุนามที่จะแก้ปัญหาได้ นี่เป็นเพียงการอธิบายกรณีทั่วไปเท่านั้น

ปัญหาของเรามีขนาดเล็กและชัดเจน (ท้ายที่สุดแล้ว เรากำลังสร้างปัญหาเหล่านี้เพื่อมนุษย์โดยเฉพาะ!) สิ่งนี้ทำให้เหมาะอย่างยิ่งสำหรับนักแก้ปัญหา SAT สมัยใหม่ และการพูดคุยของ Hettinger (และบันทึกย่อ) แสดงให้เห็นอย่างสวยงาม

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด