ความคิดเห็นที่ 1 วางตาหมากฮอส จากคุณ : bakasama เขียนเมื่อ : 22 ธ.ค. 54 14:02:12

ความคิดเห็นที่ 2 อันนี้โปรแจกจบของผมสมัยเรียน ป ตรีเลยครับ 1 ต้องแยกกระดานเป็นกระดานเป็นขนาด เลขคี่กับคู่ก่อนครับ 2 ต่ำแหน่งที่วางม้าได้ แล้วมีประสิทธิภาพมากที่สุด คือตรงมุม รองมาคือด้านข้าง 3 วางม้าที่ตรงกลาง โดยไม่ให้กินกันได้ นำ 123 มาคำนวนเป็นสูตรสมการ พร้อมระบุตำแหน่งที่ว่างให้เสร็จสรรพ จากคุณ : Pu121 เขียนเมื่อ : 22 ธ.ค. 54 14:53:29

ความคิดเห็นที่ 3 ถ้าไม่จำกัดจำนวนครั้งที่เดิน 8*8 ตอบ ไม่มีครับ เพราะม้าสามารถเดินไปได้ทุกช่อง ปล.ใครเคยเล่นหมากรุกใหม่น่าเคยฝึกเดินม้าให้ครบ64ช่องมาแล้ว แก้ไขเมื่อ 22 ธ.ค. 54 14:55:46 จากคุณ : slamer เขียนเมื่อ : 22 ธ.ค. 54 14:54:27

ความคิดเห็นที่ 4 ได้เต็มกระดานแหละ แต่ต้องเป็นม้าสีเดียวกัน (และไม่แทงข้างหลังกันด้วย) หรือไม่ก็ เลือกแต่ม้าอิ่ม ม้ามังสวิรัช(กินแต่หญ้า) ม้าใจดี (แก้เครียด กระทู้สามเหลี่ยม) ตอบแบบจริงจัง ขั้นแรก ต้องแบ่งม้า ออกเป็น13ม้า ที่เท่ากันทุกประการก่อน โดยหั่นเฉพาะแนวตั้งฉากเท่านั้น (น้อยใจอดกินเค๊ก) แก้ไขเมื่อ 22 ธ.ค. 54 15:02:45 จากคุณ : aLITTLEspaceAround7day เขียนเมื่อ : 22 ธ.ค. 54 14:57:59

ความคิดเห็นที่ 5 ^ ฮาาาาา 8*8 ตอบ 32? แก้ไขเมื่อ 22 ธ.ค. 54 17:10:32 แก้ไขเมื่อ 22 ธ.ค. 54 17:07:54 จากคุณ : BC@CU เขียนเมื่อ : 22 ธ.ค. 54 17:04:28

ความคิดเห็นที่ 6 ถ้าเป็น non attacking knight สำหรับกระดานความยาวด้านเป็น 2n จะวางได้มากสุด 2n2 สำหรับกระดานความยาวด้านเป็น 2n+1 จะวางได้มากสุด 2n2 + 2n หลักการก็คือวางบนช่องสีเดียวกับช่องมุมให้หมด เพราะการขยับของม้า จะเปลี่ยน parity ของสีเสมอ อย่างตอนแรกม้าอยู่ช่องสีดำ ไม่ว่าจะขยับไปช่องใด 1 ช่อง ก็จะกลายเป็นช่องสีขาวเสมอ ผิดถูกยังไงก็รบกวนชี้แนะด้วยคับ แก้ไขเมื่อ 22 ธ.ค. 54 17:22:44 จากคุณ : ชโรนนท์ เขียนเมื่อ : 22 ธ.ค. 54 17:19:30

ความคิดเห็นที่ 7 #6 ไม่มีอะไรจะชี้แนะครับ จะให้กิ๊ฟ #1 แล้ว แต่ของท่านโชร ฟังดูดีมีสกุล (แม้จะยังไม่เข้าใจก็ตาม) จากคุณ : aLITTLEspaceAround7day เขียนเมื่อ : 22 ธ.ค. 54 17:23:26

ความคิดเห็นที่ 8 สมมติว่าม้าทุกตัวไม่มีฝ่าย และแต่ละตัวก้าวร้าวมาก จากคุณ : TIYHz เขียนเมื่อ : 22 ธ.ค. 54 17:43:37

ความคิดเห็นที่ 9 ผมชักสงสัยว่า เวลาเดินนี่ เดินทีละตัว หรือเดินทีเดียวหมดเลยครับ ถ้าเดินทีละตัว ถ้าหากวางบนตาหมากฮอส ตัวแรกเดินไปลงช่องไหน ก็จะมีม้าอีกประมาณ 7 ตัว ที่ก้าวร้าวมาก (อย่างที่คุณ TIYHz ว่า) จ้องจะเขมือบแน่ ๆ เพราะลงบนจุดเกรงใจของ 8 ตัวแบบนี้ จากคุณ : Lpg_Horse เขียนเมื่อ : 22 ธ.ค. 54 17:56:51

ความคิดเห็นที่ 10 ผมไม่เก็ท #9 นะครับ ตอนแรกว่าจะมุขมาอยู่ว่า ไม่กินกันหรอก เพราะทุกตัวจะเดินพร้อมกัน ไปแลกที่กันหมด แต่เกรงใจจขกท เดี๋ยวจะหาว่าพาม้าออกทะเล เป็นม้าน้ำไปซะ ถามทิ้งท้าย นิดนึง พอจะมีหมากรุก จีน ญี่ปุ่น หรือเกาหลี ที่เล่นบนเครื่องคำนวณได้ป่าวอะครับ ขอแบบที่เป็นรูป   แบบตัวหนังสือ จำไม่ได้ ขอบคุณครับ จากคุณ : aLITTLEspaceAround7day เขียนเมื่อ : 22 ธ.ค. 54 18:16:59

ความคิดเห็นที่ 11 ตอบ คุณ Lpg_Horse ครับ คิดแค่ว่าไม่มีม้าตัวใดๆ ที่จะเดินไปตกช่องเดียวกันกับม้าตัวอื่นได้ก็พอครับ *-* จากคุณ : TIYHz เขียนเมื่อ : 22 ธ.ค. 54 18:46:26

ความคิดเห็นที่ 12 ผมขอสมมติตาราง 8*8 นะครับ เอาเลขตารางไล่ขึ้น เหมือนตัวเลขระนาบ x y ตอนนี้สมมติม้าอยู่ที่ช่อง (1,1) ช่องที่เดินไปลงได้จะมีสองช่อง คือ (2,3) กับ (3,2) เพราะอยู่มุมตาราง ไปพิจารณาช่อง (2,3) ม้าที่จะเดินมาลงช่องนี้ได้ นอกจาก (1,1) แล้ว ยังมี (1,5) (3,1) (3,5) (4,2) และ (4,4) รวมแล้ว ก็ 6 ตัว ดังนั้นหมายความว่า ถ้าเราวางม้าที่ช่อง (1,1) แล้ว เราจะไม่สามารถวางม้าไว้ที่อีก 5 ช่องที่พูดถึงได้ และก็ถ้าพิจารณาจาก (3,2) อีกอัน ก็น่าจะมีอีก 5 ตัว เหมือนกัน แสดงว่า เมื่อเราวางม้าไว้ที่ (1,1) แล้ว จะวางอีก 10 ช่องไม่ได้ ตกลงแบบนี้ถูกป่าวครับ จากคุณ : Lpg_Horse เขียนเมื่อ : 22 ธ.ค. 54 20:35:21

ความคิดเห็นที่ 13 ถ้าเราวางม้าตัวแรกที่ช่อง (1,1) แล้วเราจะไม่วางม้าตัวที่สองที่ช่อง (2,3) หรือ (3,2) จะต้องไปวางในอีก 61 ช่องที่เหลือครับ จากคุณ : TIYHz เขียนเมื่อ : 22 ธ.ค. 54 21:12:32

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

ความคิดเห็นที่ 15 ระบายสีตาราง 8 x 8 ให้เป็นตารางหมากฮอสดำสลับขาวดังรูป ถ้าวางม้าในช่องสีดำทุกช่อง  ม้าจะไม่สามารถกินกันได้เลยเพราะม้าจะเดินจากช่องดำไปช่องขาวจากช่องขาวไปช่องดำสลับไปมาเท่านั้น  ดังนั้นจำนวนม้าขั้นต่ำที่สามารถวางได้คือ 32 ตัว   ปัญหาคือเราสามารถวางม้ามากกว่า32ตัวได้หรือไม่ ถ้าเราต้องการวางม้าเพิ่มในช่องสีขาว    เราจำเป็นต้องเอาม้าบางตัวในช่องสีดำออกเพื่อไม่ให้มันกินกัน และถ้าจำนวนม้าที่ถูกนำออกน้อยกว่าม้าที่ถูกวางเพิ่ม   จำนวนม้าสูงสุดที่วางได้ก็จะมากกว่า32ตัว ดังนั้นต้องหาว่ามีวิธีที่จะเลือกทิ้งม้า n ตัวที่อยู่ในช่องดำออกไป เพื่อวางม้าอย่างน้อย n+1 ตัวเพิ่มลงในช่องสีขาวได้หรือไม่ ให้เปลี่ยนตาราง 8x8 เป็นกราฟที่มีจุดยอด 64 จุด  โดยที่จุดยอด1จุดแทนช่อง1ช่องในตาราง8x8  และช่องสีดำแทนด้วยจุดสีดำ  ช่องสีขาวแทนด้วยจุดสีขาว โดยที่จุดยอด u จะมีเส้นเชื่อมกับจุดยอด v ก็ต่อเมื่อ ม้าที่อยู่ในช่องที่แทนด้วยจุดยอด u สามารถเดินไปยังช่องที่แทนด้วยจุดยอด v ได้ การวาดกราฟดังกล่าวเป็นไปได้ยาก  แต่เราก็รู้คุณสมบัติคร่าวๆของมันได้ดังนี้ -จุดยอดของกราฟจะแบ่งเป็นสองกลุ่มคือกลุ่มของจุดขาวที่ใช้แทนช่องสีขาว32จุด และกลุ่มของจุดดำที่ใช้แทนช่องสีดำ32จุด   -จุดทุกจุดจะมีเส้นเชื่อมไปยังจุดที่มีสีตรงกันข้ามเท่านั้นไม่มีเส้นเชื่อมไปยังสีเดียวกัน -ในกราฟมีจุดขาวที่มีดีกรี2อยู่2จุด   มีจุดขาวที่มีดีกรี3อยู่4จุด   มีจุดขาวที่มีดีกรี4อยู่10จุด  มีจุดขาวที่มีดีกรี6อยู่8จุด  และมีจุดขาวที่มีดีกรี8อยู่8จุด _____(1) -มีจุดดำที่มีดีกรี2อยู่2จุด   มีจุดดำที่มีดีกรี3อยู่4จุด   มีจุดดำที่มีดีกรี4อยู่10จุด  มีจุดดำที่มีดีกรี6อยู่8จุด  และมีจุดดำที่มีดีกรี8อยู่8จุด   เช่นเดียวกับจุดขาว การที่จะเลือกทิ้งม้า n ตัวที่อยู่ในช่องดำออกไป เพื่อวางม้าอย่างน้อย n+1 ตัวเพิ่มลงในช่องสีขาว สามารถแทนได้ด้วยการเลือกลบจุดดำ n จุดพร้อมกับเส้นเชื่อมที่เชื่อมจุดแต่ละจุดในบรรดา n จุดนั้น ทิ้งออกไปจากกราฟ โดยที่เมื่อลบแล้วทำให้มีจุดขาวอย่างน้อย n+1 กลายเป็นจุดเอกเทศ  (คือจุดที่มีดีกรี0) ซึ่งเงื่อนไขที่จำเป็นที่จะสามารถทำเช่นนั้นได้คือ 1.ต้องมีจุดขาวอย่างน้อย n+1 จุดที่แต่ละจุดมีดีกรี n พอดี 2.มีจุดดำอย่างน้อยหนึ่งจุดที่มีเส้นเชื่อมไปยังจุดขาวในข้อ1.ทุกจุด จาก(1)ค่า n ที่เป็นไปได้คือ  n  = 2,3,4,6,8 พิจารณา n = 2 ไม่สามารถทำได้เพราะทั่วทั้งกราฟมีจุดยอดขาวที่มีดีกรี 2 เพียง 2 จุดนั่นคือขาดเงื่อนไขข้อ1. พิจารณา n = 3,4,6,8 ไม่สามารถทำได้เพราะขาดเงื่อนไขข้อ2. ดังนั้นจึงไม่สามารถวางม้าได้มากกว่า32ตัวในตาราง 8x8 ซึ่งในกรณีทั่วไปจะได้ว่าตาราง NxN สามารถวางม้าได้มากสุด N2/2 ตัวโดยไม่กินกัน เมื่อNเป็นจำนวนคู่  และสามารถวางม้าได้มากสุด (N2+1)/2 ตัวโดยไม่กินกัน เมื่อNเป็นจำนวนคี่   ปล. กรณี N เป็นจำนวนคี่ยังไม่แน่ใจเพราะยังไม่ได้คิดละเอียด แต่กรณี N เป็นจำนวนคู่ค่อนข้างแน่ใจแล้ว จากคุณ : อิอิคุง เขียนเมื่อ : 22 ธ.ค. 54 23:07:33

ความคิดเห็นที่ 16 ยังยืนยันคำตอบเดิม ถ้าม้าอยู่ช่องดำตาเดินจะอยู่ช่องขาว ถ้าม้าอยู่ช่องกำหมด ตาเดินก็จะอยู่ช่องขาวหมดไม่มีทางกินกันได้ จากคุณ : bakasama เขียนเมื่อ : 22 ธ.ค. 54 23:52:53

ความคิดเห็นที่ 17 #15 ขอขยายความเงื่อนไขนี้อีกซักนิดนึงซิครับ 1.ต้องมีจุดขาวอย่างน้อย n+1 จุดที่แต่ละจุดมีดีกรี n พอดี 2.มีจุดดำอย่างน้อยหนึ่งจุดที่มีเส้นเชื่อมไปยังจุดขาวในข้อ1.ทุกจุด จากคุณ : aLITTLEspaceAround7day เขียนเมื่อ : 23 ธ.ค. 54 10:56:59

ความคิดเห็นที่ 18 ชอบลำดับการคิดและการอธิบายของ คุณ อิอิคุง มากครับ อยากรู้ว่าคำอธิบายนี้เกี่ยวข้องกับทฤษฎีอะไรครับ ผมจะลองไปศึกษาดูบ้าง ป.ล. สงสัยเช่นเดียวกับ คคห. 17 ป.ล.2 คำตอบในรูปทั่วไปถูกต้องครับ จากคุณ : TIYHz เขียนเมื่อ : 23 ธ.ค. 54 11:52:34

ความคิดเห็นที่ 19 เสริม คุณ bakasama ครับ ถ้า N เป็นเลขคู่ ก็เลือกวาง ช่องดำทั้งหมด หรือ ช่องขาวทั้งหมด ถ้า N เป็นเลขคี่ ให้ดูว่าช่องที่อยู่กลางตารางเป็นสีอะไร ก็ให้วางช่องที่สีเดียวกับช่องนั้นทั้งหมด จากคุณ : TIYHz เขียนเมื่อ : 23 ธ.ค. 54 11:57:53

ความคิดเห็นที่ 20 ต้องขอโทษด้วยครับ  ระหว่างที่กำลังอ่านทวนคำอธิบายใน#15เพื่ออธิบายเพิ่มเติมให้คุณaLITTLEspaceAround7day  ผมก็เจอข้อผิดพลาดอีกจนได้  -*- จุดผิดก็คือเงื่อนไข2ข้อนี้แหละครับ 1.ต้องมีจุดขาวอย่างน้อย n+1 จุดที่แต่ละจุดมีดีกรี n พอดี 2.มีจุดดำอย่างน้อยหนึ่งจุดที่มีเส้นเชื่อมไปยังจุดขาวในข้อ1.ทุกจุด   ใน#15 ผมบอกว่า2ข้อนี้เป็นเงื่อนไขที่จำเป็น   แต่ที่ถูกต้องคือ2ข้อนี้ไม่ใช่เงื่อนไขที่จำเป็น ผมคิดตื้นไปหน่อย แถมยังไม่ใช่เงื่อนไขที่เพียงพออีกต่างหาก ดังนั้นจึงไม่สามารถใช้เงื่อนไข2.ข้อนี้มาพิสูจน์ว่าไม่สามารถวางม้ามากกว่า32ตัวได้ครับ ผมขออนุญาตแก้ไขคำอธิบายใหม่นะครับ จากคุณ : อิอิคุง เขียนเมื่อ : 23 ธ.ค. 54 21:40:46

ความคิดเห็นที่ 21 ระบายสีตาราง 8 x 8 ให้เป็นตารางหมากฮอสดำสลับขาวดังรูปด้านซ้าย ถ้าวางม้าในช่องสีดำทุกช่อง  ม้าจะไม่สามารถกินกันได้เลยเพราะม้าจะเดินจากช่องดำไปช่องขาวจากช่องขาวไปช่องดำสลับไปมาเท่านั้น ดังนั้นจำนวนม้าขั้นต่ำที่สามารถวางได้คือ 32 ตัว   ปัญหาคือเราสามารถวางม้ามากกว่า32ตัวได้หรือไม่ ให้เปลี่ยนตาราง 8x8 เป็นกราฟที่มีจุดยอด 64 จุด  โดยที่จุดยอด1จุดแทนช่อง1ช่องในตาราง8x8  และช่องสีดำแทนด้วยจุดสีดำ  ช่องสีขาวแทนด้วยจุดสีขาว โดยที่จุดยอด u จะมีเส้นเชื่อมกับจุดยอด v ก็ต่อเมื่อ ม้าที่อยู่ในช่องที่แทนด้วยจุดยอด u สามารถเดินไปยังช่องที่แทนด้วยจุดยอด v ได้ การวาดกราฟดังกล่าวเป็นไปได้ยาก  แต่เราก็รู้คุณสมบัติคร่าวๆของมันได้ดังนี้ -จุดยอดของกราฟจะแบ่งเป็นสองกลุ่มคือกลุ่มของจุดขาวที่ใช้แทนช่องสีขาว32จุด และกลุ่มของจุดดำที่ใช้แทนช่องสีดำ32จุด   -จุดทุกจุดจะมีเส้นเชื่อมไปยังจุดที่มีสีตรงกันข้ามเท่านั้นไม่มีเส้นเชื่อมไปยังสีเดียวกัน -ในกราฟมีจุดขาวที่มีดีกรี2อยู่2จุด   มีจุดขาวที่มีดีกรี3อยู่4จุด   มีจุดขาวที่มีดีกรี4อยู่10จุด  มีจุดขาวที่มีดีกรี6อยู่8จุด  และมีจุดขาวที่มีดีกรี8อยู่8จุด -มีจุดดำที่มีดีกรี2อยู่2จุด   มีจุดดำที่มีดีกรี3อยู่4จุด   มีจุดดำที่มีดีกรี4อยู่10จุด  มีจุดดำที่มีดีกรี6อยู่8จุด  และมีจุดดำที่มีดีกรี8อยู่8จุด   เช่นเดียวกับจุดขาว และจะเรียกกราฟดังกล่าวว่ากราฟ G พิจารณากราฟ H(ในรูปด้านขวา) เห็นได้ชัดว่าเราสามารถวางม้าลงในกราฟ H ได้สูงสุด32ตัวคือวางม้าในจุดดำทั้งหมด(หรือวางม้าในจุดขาวทั้งหมด)_____(1) จากความรู้เรื่อง Knight's tour จะได้ว่าในตาราง 8x8 ต้องมี open knight's tour นั่นคือกราฟ G มีกราฟ H เป็นสับกราฟ _____(2) จาก(1)และ(2)จึงสรุปได้ว่าไม่สามารถวางม้าได้มากกว่า32ตัวในตาราง 8x8 ดังนั้นจำนวนม้าสูงสุดที่สามารถวางได้ในตาราง8x8คือ32ตัว ซึ่งในกรณีทั่วไปจะได้ว่าตาราง NxN สามารถวางม้าได้มากสุด N2/2 ตัวโดยไม่กินกัน เมื่อNเป็นจำนวนคู่ และสามารถวางม้าได้มากสุด (N2+1)/2 ตัวโดยไม่กินกัน เมื่อNเป็นจำนวนคี่   ปล. คราวนี้มั่นใจร้อยเปอร์เซ็นต์ครับ  ไม่มีจุดผิดพลาดแน่นอน จากคุณ : อิอิคุง เขียนเมื่อ : 23 ธ.ค. 54 22:10:19

ความคิดเห็นที่ 22 รูปประกอบ จากคุณ : อิอิคุง เขียนเมื่อ : 23 ธ.ค. 54 22:11:03

ความคิดเห็นที่ 23 #21 http://en.wikipedia.org/wiki/Knight's_tour รูปประกอบของ G กับตัวอย่างของ H H ต้องสลับขาวดำเสมอ ถูกต้อง H เป็นซับกราฟของ G ถูกต้อง H32(64) เป็นเส้นH ที่ยาวที่สุด ถูกต้อง ประเดนผมคือ ทำไม H ต้องเป็นเส้น ถ้าเป็นต้นไม้ มีโอกาส ที่จะเยอะกว่านี้ได้หรือไม่ ปล.ให้ผมคิดเองคงจะไม่ไหว แต่ได้ลองไล่ๆดูก็สนุกดีเหมือนกัน คงไม่ว่ากันนะครับ จากคุณ : aLITTLEspaceAround7day เขียนเมื่อ : 26 ธ.ค. 54 17:15:15