1032 : Sudoku
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
สุโดกุ (sudoku, 数独 sūdoku) เป็นเกมคณิตศาสตร์เกมหนึ่ง โดยกำหนดให้มีตารางจัตุรัสขนาด 3 x 3 ตารางหน่วยอยู่ 9 ตาราง และตาราง 33 หน่วยทั้ง 9 ตารางนี้ ได้ถูกนำมาเรียงต่อกันเป็นตารางจัตุรัสขนาด 9 x 9 ตารางหน่วย เป้าหมายของการเล่นสุโดกุคือการหาจำนวนเต็ม 1-9 มาใส่ในตาราง 9 x 9 โดยที่ในแต่ละคอลัมน์ แต่ละแถว และ แต่ละตารางจัตุรัสย่อย 3 x 3 นั้นไม่มีตัวเลขซ้ำกันเลย
ความยากง่ายของเกมสุโดกุจะอยู่ที่จำนวนเต็มในบางช่องของตารางที่บังคับไว้ก่อนการเริ่มเล่น เพื่อจำกัดอิสระในการวางตัวเลขที่เหลือ ซึ่งเป็นส่วนสำคัญในการสร้างทักษะทางคณิตศาสตร์ให้กับผู้เล่น จากตัวอย่างต่อไปนี้ ตารางซ้ายคือโจทย์สุโดกุข้อหนึ่งพร้อมช่องบังคับเริ่มต้น และตารางขวาคือเป็นตัวอย่างของคำตอบที่ถูกต้องแบบหนึ่ง ทั้งนี้คำตอบที่ถูกอาจมีรูปแบบมากกว่าหนึ่งแบบก็ได้
ตัวอย่าง
การเล่นสุโดกุนี้ได้รับความนิยมเพิ่มขึ้นเรื่อยๆจนกระทั่งมีการจัดการแข่งขันสุโดกุขึ้นมา เนื่องจากในการแข่งขันมีผู้เข้าแข่งขันจำนวนมาก การตรวจสอบว่าตารางนั้นถูกต้องหรือไม่นั้นเป็นงานที่ใช้เวลามาก ทำให้มีความจำเป็นที่จะต้องอาศัยโปรแกรมคอมพิวเตอร์ช่วยตรวจ
โจทย์
จงเขียนโปรแกรมเพื่อตรวจสอบว่าตารางสุโดกุที่ส่งเข้ามาตรวจในระหว่างการแข่งขันนั้น มีผู้เข้าแข่งขันคนใดทำถูกต้องบ้าง
ข้อมูลนำเข้า
ข้อมูลส่งออกจะมีหมายเลขของผู้เข้าแข่งขันที่ตอบได้ถูกต้องบรรทัดละหนึ่งหมายเลข บรรทัดหนึ่ง ๆ จะแสดงจำนวนเต็ม i หากว่าตารางสุโดกุของผู้เข้าแข่งขันคนที่ i เป็นคำตอบที่ถูกต้องตามโจทย์และเงื่อนไข บรรทัดสุดท้ายให้แสดงคำว่า 'END'
ที่มา: การสอบแข่งขันคณิตศาสตร์และวิทยาศาสตร์โอลิมปิกแห่งประเทศไทย
ประจำปี พ.ศ.2549 (สอบแข่งขันรอบที่ 2 ภาคปฏิบัติวันที่ 1)
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ความยากง่ายของเกมสุโดกุจะอยู่ที่จำนวนเต็มในบางช่องของตารางที่บังคับไว้ก่อนการเริ่มเล่น เพื่อจำกัดอิสระในการวางตัวเลขที่เหลือ ซึ่งเป็นส่วนสำคัญในการสร้างทักษะทางคณิตศาสตร์ให้กับผู้เล่น จากตัวอย่างต่อไปนี้ ตารางซ้ายคือโจทย์สุโดกุข้อหนึ่งพร้อมช่องบังคับเริ่มต้น และตารางขวาคือเป็นตัวอย่างของคำตอบที่ถูกต้องแบบหนึ่ง ทั้งนี้คำตอบที่ถูกอาจมีรูปแบบมากกว่าหนึ่งแบบก็ได้
ตัวอย่าง
| ตารางเริ่มต้น | ตารางที่ถูกต้อง |
| 5 3 | 7 | 6 | 1 9 5 | 9 8 | | 6 -------+-------+------ 8 | 6 | 3 4 | 8 3 | 1 7 | 2 | 6 -------+-------+------ 6 | | 2 8 | 4 1 9 | 5 | 8 | 7 9 |
5 3 4 | 6 7 8 | 9 1 2 6 7 2 | 1 9 5 | 3 4 8 1 9 8 | 3 4 2 | 5 6 7 -------+-------+------ 8 5 9 | 7 6 1 | 4 2 3 4 2 6 | 8 5 3 | 7 9 1 7 1 3 | 9 2 4 | 8 5 6 -------+-------+------ 9 6 1 | 5 3 7 | 2 8 4 2 8 7 | 4 1 9 | 6 3 5 3 4 5 | 2 8 6 | 1 7 9 |
การเล่นสุโดกุนี้ได้รับความนิยมเพิ่มขึ้นเรื่อยๆจนกระทั่งมีการจัดการแข่งขันสุโดกุขึ้นมา เนื่องจากในการแข่งขันมีผู้เข้าแข่งขันจำนวนมาก การตรวจสอบว่าตารางนั้นถูกต้องหรือไม่นั้นเป็นงานที่ใช้เวลามาก ทำให้มีความจำเป็นที่จะต้องอาศัยโปรแกรมคอมพิวเตอร์ช่วยตรวจ
โจทย์
จงเขียนโปรแกรมเพื่อตรวจสอบว่าตารางสุโดกุที่ส่งเข้ามาตรวจในระหว่างการแข่งขันนั้น มีผู้เข้าแข่งขันคนใดทำถูกต้องบ้าง
ข้อมูลนำเข้า
- บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็ม n (0 < n <= 100) ซึ่งเป็นจำนวนผู้เข้าแข่งขัน
- เก้าบรรทัดถัดมาเป็นตารางโจทย์สุโดกุเริ่มต้นที่ผู้เข้าแข่งขันทุกคนจะต้องทำเหมือนกัน โดยในแต่ละบรรทัดคือแต่ละแถวของตารางเริ่มต้น ซึ่งแต่ละแถวประกอบด้วยจำนวนเต็ม x (0 <= x <= 9) อยู่ 9 ตัวคั่นด้วยช่องว่าง จำนวนเต็มแต่ละตัวคือค่าที่อยู่ในตารางสุโดกุ โดยค่าเป็น 0 หมายถึงค่าเริ่มต้นนั้นเป็นช่องว่าง
- ทุก ๆ 9 บรรทัดถัดมาจะเป็นตารางสุโดกุของผู้เข้าแข่งขันคนที่ 1 ไปถึงคนที่ n ดังนั้นข้อมูลของผู้เข้าแข่งขันคนที่ i จึงเริ่มต้นที่บรรทัด 9i+2 ไปจนถึงบรรทัดที่ 9i+8 ซึ่งแต่ละแถวประกอบด้วยจำนวนเต็ม y (1 <= y <= 9) อยู่ 9 ตัวคั่นด้วยช่องว่าง จำนวนเต็มแต่ละตัวคือค่าที่อยู่ในตารางสุโดกุของผู้เข้าแข่งขันคนที่ i
ข้อมูลส่งออกจะมีหมายเลขของผู้เข้าแข่งขันที่ตอบได้ถูกต้องบรรทัดละหนึ่งหมายเลข บรรทัดหนึ่ง ๆ จะแสดงจำนวนเต็ม i หากว่าตารางสุโดกุของผู้เข้าแข่งขันคนที่ i เป็นคำตอบที่ถูกต้องตามโจทย์และเงื่อนไข บรรทัดสุดท้ายให้แสดงคำว่า 'END'
ที่มา: การสอบแข่งขันคณิตศาสตร์และวิทยาศาสตร์โอลิมปิกแห่งประเทศไทย
ประจำปี พ.ศ.2549 (สอบแข่งขันรอบที่ 2 ภาคปฏิบัติวันที่ 1)
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 2 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 1 1 1 6 7 8 9 1 2 1 1 1 1 9 5 3 4 8 1 1 1 1 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 | 2 END |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)