อัลกอริทึมของพระเจ้าสำหรับลูกบาศก์รูบิกเป็นแนวคิดที่มาจากการอภิปรายเกี่ยวกับวิธีการแก้ปริศนาลูกบาศก์รูบิก^{[ 1 ]}แต่ยังสามารถนำไปใช้กับปริศนาเชิงการจัดเรียง และเกมคณิตศาสตร์ อื่นๆ ได้อีก ด้วย^{[ 2 ]}หมายถึงอัลกอริทึมใดๆ ที่สร้างวิธีแก้ปัญหาโดยใช้จำนวนการเคลื่อนไหวน้อยที่สุดเท่าที่จะเป็นไปได้ (กล่าวคือ ผู้แก้ปัญหาไม่ควรต้องใช้การเคลื่อนไหวมากกว่าจำนวนนี้) การอ้างอิงถึงพระเจ้าขึ้นอยู่กับแนวคิดที่ว่า สิ่งมีชีวิต ที่รอบรู้จะทราบขั้นตอนที่เหมาะสมที่สุดจากการกำหนดค่าใดๆ ก็ตาม

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

อัลกอริทึมสามารถถือได้ว่าสามารถแก้ปริศนาดังกล่าวได้ หากรับการกำหนดค่าเริ่มต้นแบบสุ่มเป็นอินพุต และสร้างลำดับการเคลื่อนไหวที่นำไปสู่การกำหนดค่าสุดท้ายเป็นเอาต์พุต ( หากสามารถแก้ปริศนาได้จากการกำหนดค่าเริ่มต้นนั้น มิฉะนั้นจะบ่งชี้ถึงความเป็นไปไม่ได้ของวิธีแก้ปัญหา) วิธีแก้ปัญหาที่ดีที่สุดคือ ลำดับการเคลื่อนไหวสั้นที่สุดเท่าที่จะเป็นไปได้ ค่าสูงสุดของสิ่งนี้ในบรรดาการกำหนดค่าเริ่มต้นทั้งหมดเรียกว่าจำนวนของพระเจ้า [ ^{3 ] หรือ เรียก}อย่างเป็นทางการว่าค่ามินิแม็กซ์^{[ 4 ]}ดังนั้น อัลกอริทึมของพระเจ้าสำหรับปริศนาที่กำหนด จึงเป็นอัลกอริทึมที่แก้ปริศนาและสร้างเฉพาะวิธีแก้ปัญหาที่ดีที่สุดเท่านั้น

นักเขียนบางคน เช่น เดวิด จอยเนอร์ พิจารณาว่าอัลกอริทึมที่จะเรียกว่า "อัลกอริทึมของพระเจ้า" ได้อย่างเหมาะสมนั้น ควรจะใช้งานได้จริง ด้วย ซึ่งหมายความว่าอัลกอริทึมนั้นไม่ต้องการหน่วยความจำหรือเวลาจำนวนมากเป็นพิเศษ ตัวอย่างเช่น การใช้ตารางค้นหา ขนาดใหญ่ ที่จัดทำดัชนีโดยการกำหนดค่าเริ่มต้นจะช่วยให้สามารถค้นหาวิธีแก้ปัญหาได้อย่างรวดเร็วมาก แต่จะต้องใช้หน่วยความจำจำนวนมหาศาล^{[ 5 ]}

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

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

ปริศนาสิบห้าสามารถแก้ได้ด้วยการเคลื่อนย้ายไทล์เดี่ยว 80 ครั้ง^{[ 6 ]}หรือการเคลื่อนย้ายไทล์หลายอัน 43 ครั้ง^{[ 7 ]}ในกรณีที่เลวร้ายที่สุด สำหรับการวางนัยทั่วไปของปริศนาnปัญหาของการค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุดนั้นเป็นปัญหาNP-hard [ ^{8 ]}ดังนั้นจึงไม่ทราบว่ามีอัลกอริทึม God ที่ใช้งานได้จริงหรือ ^ไม่

สำหรับ ปริศนา หอคอยฮานอย อัลกอริทึมของพระเจ้าเป็นที่รู้จักสำหรับจำนวนดิสก์ที่กำหนด จำนวนการเคลื่อนย้ายเพิ่มขึ้น ^แบบทวีคูณตามจำนวนดิสก์( )${\displaystyle 2^{n}-1}$ [ ^{9 ]}

อัลกอริทึมในการกำหนดจำนวนการเคลื่อนย้ายขั้นต่ำเพื่อแก้ลูกบาศก์รูบิกได้รับการตีพิมพ์ในปี 1997 โดยRichard E. Korf [ ^{10 ] แม้ว่า}จะทราบกันมาตั้งแต่ปี 1995 แล้วว่า 20 เป็นขอบเขตล่างของจำนวนการเคลื่อนย้ายสำหรับวิธีแก้ปัญหาในกรณีที่เลวร้ายที่สุด แต่ Tom Rokicki ได้พิสูจน์ในปี 2010 ว่าไม่มีการจัดเรียงใดที่ต้องใช้การเคลื่อนย้ายมากกว่า 20 ครั้ง^{[ 11 ]}ดังนั้น 20 จึงเป็นขอบเขตบนที่ชัดเจน ของความยาวของวิธีแก้ปัญหาที่เหมาะสมที่สุด นักคณิตศาสตร์David Singmasterได้ "คาดเดาอย่างไม่รอบคอบ" ว่าตัวเลขนี้คือ 20 ในปี 1980 ^{[ 4 ]}

เกมที่รู้จักกันดีบางเกมที่มีชุดกฎและการเคลื่อนไหวที่กำหนดไว้อย่างดีและจำกัดมากนั้น ไม่เคยมีอัลกอริทึมของพระเจ้าสำหรับกลยุทธ์การชนะที่กำหนดไว้ ตัวอย่างเช่น เกมกระดานหมากรุกและโกะ^{[ 12} ] เกมทั้งสองนี้มีจำนวนตำแหน่งที่เพิ่มขึ้นอย่างรวดเร็วในแต่ละการเคลื่อนไหว จำนวนตำแหน่งที่เป็นไปได้ทั้งหมดประมาณ 5×10 ^{44 [ 13 ]}สำหรับหมากรุกและ 10 ¹⁸⁰ (บนกระดาน 19×19) สำหรับโกะ^{[ 14 ] นั้น}มากเกินไปที่จะอนุญาตให้มีวิธีแก้ปัญหาแบบใช้กำลังทั้งหมดด้วยเทคโนโลยีการคำนวณในปัจจุบัน (เปรียบเทียบกับลูกบาศก์รูบิกที่ได้รับการแก้ไขแล้วด้วยความยากลำบากอย่างมาก ซึ่งมีเพียงประมาณตำแหน่ง 4.3 × 10 ¹⁹ตำแหน่ง^{[ 15 ]} ) ด้วยเหตุนี้ การกำหนดอัลกอริทึมของพระเจ้าสำหรับเกมเหล่านี้ด้วยกำลังทั้งหมดจึงเป็นไปไม่ได้ แม้ว่าคอมพิวเตอร์หมากรุกจะถูกสร้างขึ้นมาซึ่งสามารถเอาชนะผู้เล่นมนุษย์ที่เก่งที่สุดได้ แต่พวกมันก็ไม่ได้คำนวณเกมทั้งหมดจนจบ ตัวอย่างเช่น Deep Blueค้นหาเพียง 11 ตาเดินล่วงหน้า (นับการเดินของผู้เล่นแต่ละคนเป็นสองตาเดิน) ลดพื้นที่การค้นหาเหลือเพียง 10 ^{17 [} 16 ^{] หลังจากนั้น มันจะประเมินแต่ละตำแหน่งเพื่อหาความ ได้} เปรียบตามกฎที่ได้มาจากการเล่นและประสบการณ์ของมนุษย์

แม้แต่กลยุทธ์นี้ก็ยังเป็นไปไม่ได้สำหรับโกะ นอกจากจะมีตำแหน่งที่ต้องประเมินจำนวนมากแล้ว ยังไม่มีใครสร้างชุดกฎง่ายๆ สำหรับประเมินความแข็งแกร่งของตำแหน่งโกะได้สำเร็จเหมือนที่ทำในหมากรุก แม้ว่าเครือข่ายประสาทเทียมที่ฝึกฝนผ่านการเรียนรู้แบบเสริมแรงจะสามารถให้การประเมินตำแหน่งที่เกินความสามารถของมนุษย์ได้ก็ตาม^{[ 17 ]} อัลกอริทึมการประเมินมีแนวโน้มที่จะทำผิดพลาดขั้นพื้นฐาน^{[ 18 ]}ดังนั้นแม้แต่การมองไปข้างหน้าอย่างจำกัดโดยมีเป้าหมายจำกัดอยู่ที่การค้นหาตำแหน่งชั่วคราวที่แข็งแกร่งที่สุด อัลกอริทึมของพระเจ้าก็ยังเป็นไปไม่ได้สำหรับโกะ

ในทางกลับกันหมากรุก (หมากฮอส) ถูกสงสัยมานานแล้วว่า "เล่นจนหมด" โดยผู้เชี่ยวชาญ^{[ 19 ]} ในปี 2550 Schaeffer และคณะได้พิสูจน์เรื่องนี้โดยการคำนวณฐานข้อมูลของตำแหน่งทั้งหมดที่มีตัวหมากสิบตัวหรือน้อยกว่านั้น โดยให้ขั้นตอนวิธีของพระเจ้าสำหรับเกมหมากรุกตอนจบทั้งหมด ซึ่งใช้เพื่อพิสูจน์ว่าเกมหมากรุกที่เล่นอย่างสมบูรณ์แบบทั้งหมดจบลงด้วยการเสมอ^{[ 20 ]} อย่างไรก็ตาม หมากรุกที่มีเพียงตำแหน่ง5 × 10 ^{20 [ 21 ]}และน้อยกว่านั้นอีก3.9 × 10 ¹³ในฐานข้อมูล^{[ 22 ]}เป็นปัญหาที่แก้ไขได้ง่ายกว่ามาก – อยู่ในระดับเดียวกับลูกบาศก์รูบิก

ขนาดของเซตตำแหน่งของปริศนาไม่ได้กำหนดว่าอัลกอริทึมของพระเจ้าเป็นไปได้หรือไม่ ปริศนาหอคอยฮานอยที่แก้แล้วสามารถมีจำนวนชิ้นส่วนได้ตามอำเภอใจ และจำนวนตำแหน่งจะเพิ่มขึ้นแบบทวีคูณตามอย่างไรก็ตาม อัลกอริทึมการแก้ปัญหาสามารถนำไปใช้กับปัญหาขนาดใดก็ได้ โดยมีเวลาทำงานที่ปรับขนาดตาม^{[ 23 ]}${\displaystyle 3^{n}}$${\displaystyle 2^{n}}$

• เครื่องออราเคิล
• การเคลื่อนไหวอันศักดิ์สิทธิ์
• หลักฐานจากหนังสือเล่มนั้น
• กลุ่มลูกบาศก์รูบิค
• เกมที่แก้ไขแล้ว