ใช้ Python และการค้นหาแบบกว้าง 2 ด้านเพื่อแก้ลูกบาศก์ Rubiks ขนาด 2x2
แรงบันดาลใจจากโครงการใน MIT 6.006 สร้างขึ้นตั้งแต่เริ่มต้นอย่างมีเอกลักษณ์
https://youtu.be/ZHxLO6fubaU
สร้าง cube API, อัลกอริทึม และ GUI ตั้งแต่เริ่มต้น แต่ละด้านทั้ง 6 ด้านมี 4 ช่องที่แตกต่างกัน ทำให้มี 24 ช่อง นอกจากนี้ ยังมีชิ้นส่วนมุมทั้งหมด 8 ชิ้นที่ประกอบกันเป็นลูกบาศก์ โดยแต่ละชิ้นมี 3 ทิศทาง ดังนั้นจึงขนานไปกับสี่เหลี่ยม 24 ชิ้น
ฉันกำหนดแต่ละส่วนย่อยจาก 24 ส่วนของแต่ละด้านเป็นสตริงที่มี 'xyz' เป็นรูปแบบโดยที่ x คือสีที่หันไปทันที และ y และ z เรียงตามเข็มนาฬิการอบลูกบาศก์สำหรับมุมนั้น
ฉันเดินไปรอบๆ ลูกบาศก์และกำหนดแต่ละด้านด้วยตัวเลขคงที่ซึ่งแสดงถึงสถานะที่แก้ไขได้ ตัวอย่างเช่น 0, 1, 2, 3 คือ 4 ส่วนของด้านหน้าหันไปทางสีขาว โดยที่ 0 อยู่ซ้ายบน และส่วนอื่นๆ เรียงตามเข็มนาฬิกา
มี 12 การเคลื่อนไหวที่สามารถทำได้บนคิวบ์ ขวา, ซ้าย, บน, ล่าง, หน้า, หลัง แต่ละอันมีการเคลื่อนไหวทวนเข็มนาฬิกาด้วย ดังนั้น 6x2 = 12 การเคลื่อนไหว แต่ละ 12 อย่างนี้จัดการครึ่งหนึ่งของลูกบาศก์ ดังนั้น 12 สี่เหลี่ยม เพื่อดำเนินการย้ายเหล่านี้ ฉันได้สร้างพจนานุกรมสำหรับแต่ละ 6 ตำแหน่งตามเข็มนาฬิกา โดยให้สี่เหลี่ยมจัตุรัสย่อยหมุนจากต้นฉบับไปยังตำแหน่งต่อไปนี้ ในการทำจำนวนเฉพาะ ฉันเพิ่งเปลี่ยนคีย์และค่า
การแก้ปัญหานี้ยุ่งยากเป็นพิเศษเนื่องจากการเรียงสับเปลี่ยนคิวบ์ที่เป็นไปได้จำนวนมาก มี 24 ช่องย่อยและออกมาเป็น 24P24 = 24! ซึ่งมีค่าแมกนิจูด 10^23 มีน้อยกว่าจำนวนนี้เนื่องจากบางสถานการณ์แต่จำนวนยังคงมีมหาศาล
ในการสร้างต้นไม้ ฉันจะต้องวิ่งแต่ละท่าและวิ่งทุกท่าจากท่าที่ใหญ่มาก ความสูงของต้นไม้ 12^ ฉันสามารถจำกัดขนาดนี้ได้ด้วยการสร้างคำสั่งของตำแหน่งที่เยี่ยมชม ดังนั้นมันจะไม่ทำซ้ำการดำเนินการสำหรับการเรียงสับเปลี่ยนที่เยี่ยมชมก่อนหน้านี้
ฉันเริ่มต้นด้วยการสร้าง BFS แบบ 1 ด้าน แต่นั่นจะถึงขีดจำกัดการเรียกซ้ำเนื่องจากแผนผังการแตกแขนงจะมีขนาดใหญ่เกินไป เพื่อแก้ไขปัญหานี้ ฉันใช้ BFS แบบ 2 ด้านโดยสลับการสร้างสาขาตั้งแต่เริ่มต้นและสิ้นสุดโซลูชัน มันจะสร้างต้นไม้และตรวจสอบว่าฝั่งตรงข้ามพบจุดแล้วหรือไม่ หากเป็นเช่นนั้นก็จะคืนจุดเชื่อมต่อ
ในระหว่างทั้งหมดนี้ แต่ละโหนดจะบันทึกโหนดหลัก (สำหรับการแตกสาขาด้านหน้า) หรือลูก (สำหรับการแตกสาขาด้านหลัง) เพื่อค้นหาเส้นทางที่ใช้ ฉันพบพาเรนต์จากโหนดที่เชื่อมต่อแบบวนซ้ำ จากนั้นจึงค้นหาลูกทั้งหมดของจุดนั้น สิ่งนี้ส่งผลให้มีตำแหน่งต่างๆ มากมายตั้งแต่ช่วงที่มีการแย่งชิงไปจนถึงการแก้ไข
โครงงานนี้ประยุกต์การใช้ ทฤษฎีกราฟและการค้นหาแบบกว้างๆ ของฉัน ฉันปรับปรุงความสามารถของฉันใน Python และการเรียกซ้ำ ฉันยังทดลองพบว่าการเคลื่อนไหวสูงสุดในการแก้ลูกบาศก์ 2x2 เป็น 11 การเคลื่อนไหว เนื่องจากฉันไม่สามารถหาวิธีแก้ปัญหาที่ใช้เวลานานกว่านี้ได้
เรียนรู้วิธีใช้ไลบรารี tkinter เพื่อสร้าง GUI สำหรับโปรเจ็กต์
