ปัญหาวางหมากรุก: วางได้เยอะสุดกี่ตัว?

มีกระดานหมากรุกขนาด N*M
N,M >= 4

1. วาง Queen ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

 

    การเดินของ Queen คือ ตลอดแนวทแยง และตลอดแนวตรงดังรูป ที่ 1

รูปที่ 1 แสดงการเดินของ Queen

"ลองวาง Queen บนกระดาน 5*8 กันนะครับ"

「วางได้ประมาณนี้ขอรับ 」

รูปที่ 2 วาง Queen บนกระดาน 5*8

มาลองวิเคราะห์การวางควีนดูนะครับ

กระดานมี 5 แถว กับ 8 หลัก

 แต่ละแถววาง Queen ได้แค่ตัวเดียว

แต่ละหลักวาง Queen ได้แค่ตัวเดียว

เนื่องจากมีแค่ 5 แถว

ดังนั้น ถ้าวางดีๆ

ก็ยังวางได้ไม่เกิน 5 ตัวอยู่ดี 

ดังที่เห็นในรูปข้างบน

สรุปคือ วางควีนได้มากสุดเท่ากันเลขที่น้อยที่สุดของหลักและแถว

maxQueen = min(row, column)

2. วาง Rook ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

การเดินของ Rook คือ ตลอดแนวตรงดังรูป ที่ 3

รูปที่ 3 การเดิน Rook

การวิเคราะห์ Rook เหมือนกันกับ Queen เลยครับ

「ทำไมล่ะขอรับ」

"เพราะการเดินของ Rook เหมือน Queen ที่เดินทแยงไม่ได้ไงล่ะ"

การวาง Rook บนกระดานจึงมองจากแถวหรือหลักที่น้อยกว่าเช่นกัน

นั่นคือ 

ในแต่ละหลักวางได้ตัวเดียว

ในแต่ละแถววางได้ตัวเดียว

ดังนั้นจะได้สมการเดียวกันกับ Queen คือ

maxRook= min(row, column)

3. วาง King ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

King เดินได้ 1 ก้าว รอบทิศทาง ดังรูปที่ 4

รูปที่ 4 การเดินของ King

"บนกระดาน 5*9 การวาง King จะเป็นแบบไหน?"

「ประมาณนี้ขอรับ」

อ่า ทีนี้ลองวิเคราะห์กันดูครับ

พบว่า King แต่ละตัวกินพื้นที่ 2*2 ดังรูปครับ

จะเห็นว่า หลังจากแบ่งกระดานด้วยสี่เหลี่ยม 2*2 แล้ว

อาจมีส่วนที่เหลืออยู่จากการแบ่งนั้น ต้องนำมาคิดด้วยนะครับ

จากข้างบน 5x9

นำมาแบ่งด้วย 2x2

คือ 5x9 / 2x2

ได้ (5/2) * (9/2)

เท่ากับ 2 * 4 = 8 ซึ่งยังไม่ครบ

ต้องรวมเศษจากการแบ่งเข้าไปด้วย

เปลี่ยนเป็น (5/2 + 5%2) * (9/2 + 9%2)

เท่ากับ (2+1) * (4+1) = 3 * 5 = 15

ซึ่งเป็นคำตอบที่ถูกต้อง

ดังนั้น สรุปว่า

maxKing = (row/2 + row%2) * (column/2 + column%2)

4. วาง Knight ได้มากสุดกี่ตัวโดยที่แต่ละตัวกินตัวอื่นไม่ได้ และไม่โดนตัวอื่นกินใน 1 ตาเดิน

การเดินของ Knight เป็นรูปตัว L (เดินข้ามหมากตัวอื่นได้) แบบรูปที่ 5

รูปที่ 5 การเดินของ Knight

"กระดาน 8*8 วาง Knight ยังไงให้เยอะๆ?"

「แบบนี้ขอรับ」

นี่เป็นวิธีที่ดีที่สุดในการวาง Knight ลงบนกระดานครับ

กระดานขนาด 8x8 = 64
ได้ Knight 32 ตัว

 「แสดงว่าได้ Knight เป็น 1/2 เท่าของขนาดกระดานสินะขอรับ?」

"เกือบถูก แต่ยังไม่ใช่ เพราะเรา ยังไม่ได้พิจารณากรณีที่ขนาดกระดานเป็นเลขคี่"

พิจารณากรณีที่กระดานขนาดเป็นเลขคี่ดูครับ

เช่น เมื่อกระดานขนาด 3x5 = 15 เป็นเลขคี่

จะได้ตามรูปข้างล่าง

กระดาน 3x5 วาง knight ได้ 8 ตัว

3*5 = 15 

15/2 = 7.5 --> 8

ดังนั้น ได้สมการคือ

maxKnight = (row*column)/2 + (row*column)%2

"สำหรับปัญหาของคราวนี้ก็มีแค่นี้นะครับ"

「ไว้เจอกันอีกทีที่บทความหน้านะขอรับ ^^ 」