ปัญหาหมากรุกทางคณิตศาสตร์

ปัญหาหมากรุกทางคณิตศาสตร์คือปัญหาทางคณิตศาสตร์ที่กำหนดขึ้นโดยใช้กระดานหมากรุกและ ตัว หมากรุกปัญหาเหล่านี้จัดอยู่ในกลุ่มคณิตศาสตร์เพื่อความบันเทิงปัญหาที่รู้จักกันดีที่สุดในประเภทนี้คือปริศนาแปดควีนและ ปัญหา การเดินของอัศวินซึ่งมีความเชื่อมโยงกับทฤษฎีกราฟและคณิตศาสตร์เชิงการจัดเรียงนักคณิตศาสตร์ชื่อดังหลายคนศึกษาปัญหาหมากรุกทางคณิตศาสตร์ เช่นThabit , Euler , LegendreและGauss ^{[ 1 ]} นอกจากการหาคำตอบของปัญหาเฉพาะแล้ว นักคณิตศาสตร์มักจะสนใจใน การนับจำนวนคำตอบที่เป็นไปได้ทั้งหมด การหาคำตอบที่มีคุณสมบัติบางอย่าง รวมถึงการสรุปปัญหาไปยังกระดาน N×N หรือ M×N

ปัญหาความเป็นอิสระ

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

กระดานหมากรุกขนาด 8×8 สามารถมีราชาอิสระได้ 16 ตัว ราชินีอิสระ 8 ตัว เรืออิสระ 8 ตัว บิชอปอิสระ 14 ตัว หรืออัศวินอิสระ 32 ตัว^{[ 5 ]}

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

กษัตริย์อิสระ 16 พระองค์

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

ราชินีอิสระ 8 องค์

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

8 รุกอิสระ

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

บิชอปอิสระ 14 รูป

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

อัศวินอิสระ 32 คน

ปัญหาการครอบงำ

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

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

กษัตริย์ผู้ทรงอำนาจทั้ง 9 พระองค์

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

ราชินีผู้ทรงอำนาจ 5 องค์

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

บิชอปผู้ทรงอิทธิพล 8 รูป

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

อัศวินผู้ทรงอำนาจ 12 คน

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

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

ราชาทั้ง 12 โจมตีทุกช่อง

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

ควีนทั้ง 5 ตัวโจมตีทุกช่อง

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

บิชอป 10 รูปโจมตีทุกจัตุรัส

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

อัศวิน 14 นายโจมตีทุกช่อง

การครอบงำโดยควีนบนแนวทแยงหลักของกระดานหมากรุกขนาดใดก็ได้สามารถแสดงได้ว่าเทียบเท่ากับปัญหาในทฤษฎีจำนวนของการหาเซต Salem–Spencerซึ่งเป็นเซตของตัวเลขที่ไม่มีตัวเลขใดเป็นค่าเฉลี่ยของตัวเลขอื่นสองตัว การจัดวางควีนที่เหมาะสมที่สุดจะได้มาจากการเว้นช่องว่างของชุดช่องสี่เหลี่ยมที่มีความเท่าเทียมกันทั้งหมด (ทั้งหมดอยู่ในตำแหน่งคู่หรือทั้งหมดอยู่ในตำแหน่งคี่ตามแนวทแยง) และก่อตัวเป็นเซต Salem–Spencer ^{[ 7 ]}

ปัญหาการเดินทางแบบชิ้นส่วน

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

ปัญหาการสลับหมากรุก

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

ปริศนาสลับอัศวิน

ปริศนาการสลับบิชอป

ดูเพิ่มเติม

ปริศนาหมากรุก

หมายเหตุ

^กิก, หน้า 11
^ MacKinnon, David. "Chessdom" . GitHub . สืบค้นเมื่อ20 ตุลาคม 2024 .
^ "ทัวร์ Independent Pieces!" . Lichess . สืบค้นเมื่อ9 กรกฎาคม 2022 .
^ "mathrecreation: ปริศนาหมากรุกคณิตศาสตร์" . mathrecreation . สืบค้นเมื่อ9 กรกฎาคม 2022 .
^กิก, หน้า 98
^ Gik, หน้า 101.
^ Cockayne, EJ; Hedetniemi, ST (1986), "เกี่ยวกับปัญหาการครอบงำของควีนแนวทแยง", Journal of Combinatorial Theory , Series A, 42 (1): 137– 139, doi : 10.1016/0097-3165(86)90012-9 , MR 0843468
^กิก, หน้า 87
^ "ปริศนาสลับตัวหมาก - ฟอรัมหมากรุก "

ลิงก์ภายนอก

หมากรุกโดย เอริค ดับเบิลยู. ไวส์สไตน์จากMathWorld
ปัญหาการจัดเรียงหมากรุกโดย จอร์จ เจลลิส (จากวารสารเกมและปริศนา)
ภารกิจบนกระดานหมากรุกโดย เอ็ด เพ็กก์ จูเนียร์

[1] กิก, หน้า 11

[2] MacKinnon, David. "Chessdom" . GitHub . สืบค้นเมื่อ20 ตุลาคม 2024 .

[3] "ทัวร์ Independent Pieces!" . Lichess . สืบค้นเมื่อ9 กรกฎาคม 2022 .

[4] "mathrecreation: ปริศนาหมากรุกคณิตศาสตร์" . mathrecreation . สืบค้นเมื่อ9 กรกฎาคม 2022 .

[5] กิก, หน้า 98

[6] Gik, หน้า 101.

[7] Cockayne, EJ; Hedetniemi, ST (1986), "เกี่ยวกับปัญหาการครอบงำของควีนแนวทแยง", Journal of Combinatorial Theory , Series A, 42 (1): 137– 139, doi : 10.1016/0097-3165(86)90012-9 , MR 0843468

[8] กิก, หน้า 87

[9] "ปริศนาสลับตัวหมาก - ฟอรัมหมากรุก "

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]