1032 : Sudoku
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
สุโดกุ (sudoku, 数独 sūdoku) เป็นเกมคณิตศาสตร์เกมหนึ่ง โดยกำหนดให้มีตารางจัตุรัสขนาด 3 x 3 ตารางหน่วยอยู่ 9 ตาราง และตาราง 33 หน่วยทั้ง 9 ตารางนี้ ได้ถูกนำมาเรียงต่อกันเป็นตารางจัตุรัสขนาด 9 x 9 ตารางหน่วย เป้าหมายของการเล่นสุโดกุคือการหาจำนวนเต็ม 1-9 มาใส่ในตาราง 9 x 9 โดยที่ในแต่ละคอลัมน์ แต่ละแถว และ แต่ละตารางจัตุรัสย่อย 3 x 3 นั้นไม่มีตัวเลขซ้ำกันเลย

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

ตัวอย่าง
ตารางเริ่มต้น ตารางที่ถูกต้อง
 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

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)