สร้างและแก้เขาวงกตคืออะไร?

สร้างและแก้เขาวงกตออนไลน์ฟรี สร้างเขาวงกตแบบสุ่มและแก้ด้วยอัลกอริทึม

เขาวงกตสร้างความหลงใหลให้แก่มนุษย์มาเป็นเวลาหลายพันปี — ตั้งแต่เขาวงกตในตำนานแห่งเกาะครีต (Labyrinth of Crete) ไปจนถึงหนังสือปริศนาสมัยใหม่และเกมวิดีโอ ตัวสร้างและแก้เขาวงกต (Maze Generator & Solver) จะสุ่มสร้างเขาวงกตโดยใช้อัลกอริทึมสองแบบ แล้วจึงค้นหาเส้นทางที่สั้นที่สุดผ่านเขาวงกต ทำให้แนวคิดเชิงอัลกอริทึมกลายเป็นประสบการณ์ภาพแบบโต้ตอบได้

อัลกอริทึมการสร้างสองแบบให้สไตล์เขาวงกตที่แตกต่างกัน: DFS (Depth-First Search) สร้างทางเดินที่ยาวและคดเคี้ยวโดยมีทางตันน้อย ส่งผลให้เขาวงกตให้ความรู้สึกเหมือนทางเดินสายเดี่ยวที่วกวน ส่วนอัลกอริทึมของ Prim สร้างทางเดินที่สั้นกว่า แตกกิ่งก้านมากกว่าและมีทางตันมากกว่า ทำให้เขาวงกตท้าทายต่อการแก้มากขึ้นด้วยกิ่งก้านมากมาย

เขาวงกตที่สร้างขึ้นจะแสดงเป็นตารางของเซลล์ที่มีผนังคั่นระหว่างกัน เซลล์เริ่มต้นมีสีเขียว (มุมซ้ายบน) และเซลล์สิ้นสุดมีสีแดง (มุมขวาล่าง) คลิก Solve เพื่อหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดสิ้นสุดโดยใช้ BFS (Breadth-First Search) เส้นทางที่แก้ได้จะสว่างเป็นสีอำพัน แสดงเส้นทางผ่านเขาวงกตอย่างชัดเจน

คลิก Generate เพื่อสร้างเขาวงกตสุ่มใหม่ — แต่ละครั้งที่สร้างจะไม่ซ้ำกัน อัลกอริทึมที่อยู่เบื้องหลังรับประกันว่าเขาวงกตทุกอันที่สร้างขึ้นสามารถแก้ได้ (มีเส้นทางจากจุดเริ่มต้นไปยังจุดสิ้นสุดเสมอ) และมีวิธีแก้เพียงวิธีเดียว (ไม่มีวงวนที่สร้างเส้นทางอื่น) ขนาดของตารางถูกปรับให้เหมาะสมเพื่อความชัดเจนบนหน้าจอ