ปัญหากระดานหมากรุกที่ถูกทำลายเป็นปริศนาการปูพื้นกระเบื้อง ที่ แม็กซ์ แบล็กตั้งขึ้นในปี 1946 ซึ่งถามว่า:

สมมติว่า กระดานหมากรุก (หรือกระดานหมากฮอส ) ขนาดมาตรฐาน 8×8 ถูกเอาออกไปสองมุมตรงข้ามกัน ทำให้เหลือ 62 ช่อง เป็นไปได้หรือไม่ที่จะวางโดมิโนขนาด 2×1 จำนวน 31 ตัว ให้ครอบคลุมช่องทั้งหมดเหล่านี้?

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

ปัญหากระดานหมากรุกที่ถูกทำลายเป็นตัวอย่างหนึ่งของการปูพื้นแบบโดมิโนบนตารางและ โพลีโอ มิโน หรือที่รู้จักกันในชื่อ "แบบจำลองไดเมอร์" ซึ่งเป็นกลุ่มปัญหาทั่วไปที่มีการศึกษาในกลศาสตร์สถิติมาตั้งแต่ผลงานของRalph H. FowlerและGeorge Stanley Rushbrookeในปี 1937 ^{[ 1 ]}การปูพื้นแบบโดมิโนยังมีประวัติการใช้งานจริงมายาวนานในการออกแบบทางเท้าและการจัดเรียงพื้นเสื่อทาทามิ^{[ 2 ]}

ปัญหากระดานหมากรุกที่ถูกทำลายนั้นถูกเสนอโดยนักปรัชญาMax BlackในหนังสือCritical Thinking (1946) ของเขา โดยมีคำใบ้ถึงวิธีแก้ปัญหาโดยใช้การระบายสีเพื่อพิสูจน์ความเป็นไปไม่ได้^{[ 3 ] [ 4 ]}ปัญหานี้ได้รับความนิยมในช่วงทศวรรษ 1950 ผ่านการอภิปรายในภายหลังโดย Solomon W. Golomb (1954) ^{[ 5 ]} George Gamowและ Marvin Stern (1958) ^{[ 6 ]} Claude Berge (1958) ^{[ 4 ] [ 7 ]}และMartin Gardnerใน คอลัมน์ Scientific American ของเขา เรื่อง " Mathematical Games " (1957) ^{[ 8 ]}

การใช้ปัญหากระดานหมากรุกที่ถูกทำลายในการให้เหตุผลอัตโนมัติมีที่มาจากข้อเสนอการใช้งานโดยJohn McCarthyในปี 1964 ^{[ 9 ] [ 10 ]}นอกจากนี้ยังมีการศึกษาในวิทยาศาสตร์การรู้คิดในฐานะกรณีทดสอบสำหรับความเข้าใจเชิงสร้างสรรค์^{[ 11 ] [ 12 ] [ 13 ]}ซึ่งเป็นแรงจูงใจดั้งเดิมของ Black สำหรับปัญหานี้^{[ 3 ]}ในปรัชญาคณิตศาสตร์มีการตรวจสอบในการศึกษาเกี่ยวกับธรรมชาติของ การ พิสูจน์ทางคณิตศาสตร์^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]}

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

มีการค้นพบการพิสูจน์ความเป็นไปไม่ได้อื่นๆ อีกหลายวิธี การพิสูจน์โดยShmuel Winogradเริ่มต้นด้วยการอุปมาน ในการปูกระดานที่กำหนด หากแถวหนึ่งมีจำนวนช่องสี่เหลี่ยมที่ไม่ได้ถูกปกคลุมด้วยโดมิโนแนวตั้งจากแถวก่อนหน้าเป็นจำนวนคี่ แสดงว่าโดมิโนแนวตั้งจำนวนคี่จะต้องขยายไปยังแถวถัดไป แถวแรกมีจำนวนช่องสี่เหลี่ยมที่ไม่ได้ถูกปกคลุมด้วยโดมิโนจากแถวก่อนหน้าเป็นจำนวนคี่อย่างเห็นได้ชัด (กล่าวคือ 7) ดังนั้น โดยการอุปมาน แต่ละคู่ของแถวที่ต่อเนื่องกันเจ็ดคู่จะมีโดมิโนแนวตั้งจำนวนคี่ ทำให้ได้จำนวนรวมเป็นจำนวนคี่ ด้วยเหตุผลเดียวกัน จำนวนโดมิโนแนวนอนทั้งหมดก็ต้องเป็นจำนวนคี่เช่นกัน เนื่องจากผลรวมของจำนวนคี่สองจำนวน จำนวนโดมิโนทั้งหมด—ทั้งแนวตั้งและแนวนอน—จึงต้องเป็นจำนวนคู่ แต่ในการปูกระดานหมากรุกที่เสียหาย ต้องใช้โดมิโน 31 ตัว ซึ่งเป็นจำนวนคี่^{[ 19 ] [ 20 ]}อีกวิธีหนึ่งคือการนับขอบของแต่ละสีรอบขอบของกระดานหมากรุกที่เสียหาย จำนวนของพวกมันจะต้องเท่ากันในพื้นที่ปูกระเบื้องใดๆ บนกระดานหมากรุก เนื่องจากโดมิโนแต่ละตัวมีขอบสามด้านของแต่ละสี และขอบภายในระหว่างโดมิโนแต่ละคู่จะจับคู่ขอบเขตของสีตรงข้ามกัน อย่างไรก็ตาม กระดานหมากรุกที่ถูกทำลายจะมีขอบสีหนึ่งมากกว่าอีกสีหนึ่ง^{[ 21 ]}

ถ้าเอาช่องสี่เหลี่ยมสองช่องที่มีสีตรงข้ามกันออกไป กระดานที่เหลือก็สามารถปูด้วยโดมิโนได้เสมอ ผลลัพธ์นี้คือ^{ทฤษฎีบท}ของโกโมรี [ ^{22 ]} ซึ่งตั้งชื่อ ตามนักคณิตศาสตร์ราล์ฟ อี. โกโมรีผู้ซึ่งตีพิมพ์บทพิสูจน์ในปี 1973 ^{[ 18 ] [ 20 ]}ทฤษฎีบทของโกโมรีสามารถพิสูจน์ได้โดยใช้วงจรแฮมิลโทเนียนของกราฟตารางที่เกิดจากช่องสี่เหลี่ยมบนกระดานหมากรุก การเอาช่องสี่เหลี่ยมสองช่องที่มีสีตรงข้ามกันออกไปจะแบ่งวงจรนี้ออกเป็นสองเส้นทาง โดยแต่ละเส้นทางมีจำนวนช่องสี่เหลี่ยมเท่ากัน เส้นทางทั้งสองนี้สามารถแบ่งออกเป็นโดมิโนได้ง่ายโดยการเดินตามเส้นทางเหล่านั้น^{[ 22 ]}ทฤษฎีบทของโกโมรีใช้ได้เฉพาะกับการเอาช่องสี่เหลี่ยมสีละหนึ่งช่องออกไปเท่านั้น การเอาช่องสี่เหลี่ยมจำนวนมากออกไป โดยมีจำนวนสีเท่ากัน อาจส่งผลให้เกิดบริเวณที่ไม่สามารถปูด้วยโดมิโนได้ แต่การพิสูจน์ความเป็นไปไม่ได้โดยอาศัยการระบายสีนั้นใช้ไม่ได้ผล^{[ 23 ]}

ปัญหาการปูพื้นโดมิโนบนโพลีโอมีโนเช่น ปัญหากระดานหมากรุกที่ถูกทำลาย สามารถแก้ไขได้ใน^เวลาพหุนามไม่ว่าจะโดยการแปลงให้เป็นปัญหาในทฤษฎีกลุ่ม [ ^{21 ] [ 24 ]}หรือเป็นตัวอย่างของการจับคู่แบบทวิภาคในการกำหนดแบบหลังนี้ จะได้กราฟแบบทวิภาคที่มีจุดยอดสำหรับแต่ละช่องสี่เหลี่ยมบนกระดานหมากรุกที่มีอยู่ และมีขอบสำหรับทุกคู่ของช่องสี่เหลี่ยมที่อยู่ติดกัน ปัญหาคือการหาระบบของขอบที่สัมผัสแต่ละจุดยอดเพียงครั้งเดียว เช่นเดียวกับการพิสูจน์ความเป็นไปไม่ได้ของปัญหากระดานหมากรุกที่ถูกทำลายโดยใช้การระบายสี ข้อเท็จจริงที่ว่ากราฟนี้มีจุดยอดสีหนึ่งมากกว่าอีกสีหนึ่ง หมายความว่ากราฟนี้ไม่ตรงตามเงื่อนไขที่จำเป็นของทฤษฎีบทการแต่งงานของฮอลล์ดังนั้นจึงไม่มีการจับคู่^{[ 23 ] [ 25 ] [ 26 ]}ปัญหานี้ยังสามารถแก้ไขได้โดยการกำหนดเป็นปัญหาความพึงพอใจของข้อจำกัดและใช้การเขียนโปรแกรมแบบกึ่งกำหนดเพื่อการผ่อนคลาย^{[ 27 ]}

ในปี พ.ศ. 2507 จอห์น แมคคาร์ธีเสนอให้กระดานหมากรุกที่ถูกทำลายเป็นปัญหาที่ยากสำหรับ ระบบ พิสูจน์อัตโนมัติโดยกำหนดสูตรเป็นตรรกะลำดับที่หนึ่งและเรียกร้องให้มีระบบที่สามารถกำหนดความไม่สามารถแก้สูตรนี้ได้โดยอัตโนมัติ^{[ 9 ]}การพิจารณาปัญหานี้ส่วนใหญ่ให้คำตอบ "ในเชิงแนวคิด" ซึ่งไม่สามารถนำไปใช้กับสูตรตรรกะของแมคคาร์ธีได้^{[ 28 ]}แม้จะมีวิธีการทั่วไป เช่น วิธีการที่อิงตามการจับคู่กราฟ แต่การแก้ปัญหาสูตรตรรกะของแมคคาร์ธีนั้นยากขึ้นอย่างมาก[ 29 ^{] [ 30 ] [ 31 ]ซึ่งเน้น}ย้ำถึงความจำเป็นของวิธีการในปัญญาประดิษฐ์ที่สามารถเปลี่ยนไปใช้การแสดงปัญหาที่เหมาะสมกว่าโดยอัตโนมัติ^{[ 32 ]}และสำหรับ ระบบ การแสดงความรู้ที่สามารถจัดการความเท่าเทียมกันระหว่างการแสดงที่แตกต่างกันได้^{[ 10 ]}การพิสูจน์แบบสั้นสามารถทำได้โดยใช้การแก้ปัญหาด้วยตัวแปรเพิ่มเติม^{[ 33 ]}หรือในระบบการพิสูจน์ที่แข็งแกร่งกว่าซึ่งอนุญาตให้แสดงรูปแบบการปูพื้นที่ที่หลีกเลี่ยงได้ซึ่งสามารถตัดพื้นที่การค้นหาได้^{[ 34 ]}ตัวช่วยพิสูจน์ระดับสูงสามารถจัดการกับการพิสูจน์ความเป็นไปไม่ได้ตามการระบายสีได้โดยตรง^{ซึ่งรวม}ถึงIsabelle [ ^{35 ]}ระบบMizar ^{[ 36 ]}และNqthm [ ^{37 ]}

	เอ	ข	ค	ง	อี	เอฟ	จี	ชม.
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	เอ	ข	ค	ง	อี	เอฟ	จี	ชม.

ปัญหาการเดินทางของวาซีร์

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

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

การทัวร์กระดานหมากรุกแบบนี้ยังเป็นพื้นฐานของปริศนาประเภทหนึ่งที่เรียกว่าNumbrixซึ่งต้องการการทัวร์ที่ตำแหน่งของช่องสี่เหลี่ยมบางช่องตรงกับเบาะแสที่กำหนด^{[ 39 ]}ความเป็นไปไม่ได้ของการทัวร์จากมุมหนึ่งไปยังอีกมุมหนึ่งแสดงให้เห็นถึงความเป็นไปไม่ได้ของปริศนา Numbrix ที่มีเบาะแส 1 ในมุมหนึ่งและ 64 ในมุมตรงข้าม

ทฤษฎีบทของ De Bruijnเกี่ยวข้องกับความเป็นไปไม่ได้ในการบรรจุทรงสี่เหลี่ยมลูกบาศก์ บางรูป เข้าไปในทรงสี่เหลี่ยมลูกบาศก์ที่ใหญ่กว่า ตัวอย่างเช่น ตามทฤษฎีบทนี้ เป็นไปไม่ได้ที่จะเติม กล่อง ขนาด 6 × 6 × 6ด้วย ทรงสี่เหลี่ยมลูกบาศก์ขนาด 1 × 2 × 4การพิสูจน์ใช้การโต้แย้งการระบายสีกระดานหมากรุกที่คล้ายกับปัญหากระดานหมากรุกที่ถูกทำลาย^{[ 40 ]}