시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB175493627.692%

문제

스도쿠는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 퍼즐을 푸는 방법은 각 가로줄과 세로줄에 1에서 9까지의 숫자를 한 번만 넣고, 3*3칸의 작은 격자에도 1에서 9까지의 숫자를 겹치지 않게 넣어야 한다.

스도쿠를 푸는 방법에는 여러 가지 방법이 있다. 그 중 한가지 방법은 Cross-hatching이다.

Cross-hatching방법을 이용할 때는, 먼저 숫자를 하나 골라야 한다. 그런 뒤에, 그 숫자가 등장하는 가로줄이나 세로줄 또는 3*3 박스에 선을 긋는다. 이렇게 선을 그었을 때, 3*3박스에 고른 숫자가 들어갈 수 있는 칸이 한 칸일 때, 그 숫자를 채우는 것이다.

아래 그림 중 왼쪽 그림은 매우 조금만 숫자가 채워진 스도쿠이고, 오른쪽 그림은 cross-hatching 방법을 이용해서 4가 들어갈 수 있는 곳을 찾은 한가지 예이다.

부분적으로 숫자가 채워진 스도쿠 퍼즐이 주어졌을 때, cross-hatching방법만을 이용해서 스도쿠를 푸는 프로그램을 작성하시오. 더이상 이 방법을 이용해서 풀 수 없을 때 까지 스도쿠를 풀어야 한다. 다른 방법을 이용하면 안 된다.

입력으로 주어지는 스도쿠 퍼즐이 규칙을 지키지 않는 경우가 입력으로 주어질 수 있다. (예, 한 가로줄에 1이 2개 있는 경우, 숫자 1이 어떤 가로줄, 3*3박스, 세로줄에 있을 수 있는 곳이 전혀 없는 경우) 이런 경우도 판별해야 한다.

입력

입력은 9개줄로 이루어지며, 각 줄은 9개 문자로 이루어져 있다. 문자는 1~9 숫자 또는 '.'이다. 마침표는 빈 칸을 나타낸다.

출력

올바른 스도쿠 퍼즐이고, 모순이 일어나지 않는다면, 입력과 같은 형식으로 cross-hatching만을 이용해서 푼 결과를 출력한다. 그렇지 않다면 "ERROR"를 출력한다. (쌍따옴표는 출력하지 않는다)

예제 입력 1

..9......
.....4...
.......4.
.........
.4.......
.........
.........
.........
.........

예제 출력 1

4.9......
.....4...
.......4.
.........
.4.......
.........
.........
.........
.........

예제 입력 2

...1...6.
18...9...
..7.642..
2.9..6.5.
.43...72.
.6.3..9.1
..265.1..
...2...97
.5...3...

예제 출력 2

524137869
186529473
397864215
219476358
843915726
765382941
972658134
638241597
451793682

예제 입력 3

1........
..1......
.......1.
.........
.........
.........
.........
.........
.........

예제 출력 3

ERROR

예제 입력 4

........2
....1....
1........
......1..
.........
.........
.........
.......1.
.........

예제 출력 4

ERROR
W3sicHJvYmxlbV9pZCI6IjI5NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWNmZTAgXHVkNDgwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgXHVhYzAwXHViODVjIDlcdWNlNzgsIFx1YzEzOFx1Yjg1YyA5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVkNDVjXHVjNWQwIDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzQ0XHVjNmNjIFx1YjEyM1x1YjI5NCBcdWQzN2NcdWM5OTBcdWM3NzRcdWIyZTQuIFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0NzhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YWMwMSBcdWFjMDBcdWI4NWNcdWM5MDRcdWFjZmMgXHVjMTM4XHViODVjXHVjOTA0XHVjNWQwIDFcdWM1ZDBcdWMxMWMgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIxMjNcdWFjZTAsIDMqM1x1Y2U3OFx1Yzc1OCBcdWM3OTFcdWM3NDAgXHVhY2E5XHVjNzkwXHVjNWQwXHViM2M0IDFcdWM1ZDBcdWMxMWMgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWIxMjNcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzVkMFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWM5MTEgXHVkNTVjXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc0MCBDcm9zcy1oYXRjaGluZ1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Q3Jvc3MtaGF0Y2hpbmdcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YjU0Y1x1YjI5NCwgXHViYTNjXHVjODAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVhY2U4XHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwIFx1YjRhNFx1YzVkMCwgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVhYzAwXHViODVjXHVjOTA0XHVjNzc0XHViMDk4IFx1YzEzOFx1Yjg1Y1x1YzkwNCBcdWI2MTBcdWIyOTQgMyozIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWMxMjBcdWM3NDQgXHVhZTBiXHViMjk0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YzVjOFx1Yzc0NCBcdWI1NGMsIDMqM1x1YmMxNVx1YzJhNFx1YzVkMCBcdWFjZTBcdWI5NzggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NCBcdWQ1NWMgXHVjZTc4XHVjNzdjIFx1YjU0YywgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIFx1YzkxMSBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM4NzBcdWFlMDhcdWI5Y2MgXHVjMjJiXHVjNzkwXHVhYzAwIFx1Y2M0NFx1YzZjY1x1YzljNCBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgY3Jvc3MtaGF0Y2hpbmcgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyA0XHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0NCBcdWNjM2VcdWM3NDAgXHVkNTVjXHVhYzAwXHVjOWMwIFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC83YmNjMzllMy03Yjk4LTRiYWYtYTgyOS1mY2RmODNjZmRkZDlcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDM4N3B4OyBoZWlnaHQ6IDE2MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJkODBcdWJkODRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1Y2M0NFx1YzZjY1x1YzljNCBcdWMyYTRcdWIzYzRcdWNmZTAgXHVkMzdjXHVjOTkwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGNyb3NzLWhhdGNoaW5nXHViYzI5XHViYzk1XHViOWNjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQ0ODAgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0ODBcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzYwOCwgXHVkNTVjIFx1YWMwMFx1Yjg1Y1x1YzkwNFx1YzVkMCAxXHVjNzc0IDJcdWFjMWMgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCwgXHVjMjJiXHVjNzkwIDFcdWM3NzQgXHVjNWI0XHViNWE0IFx1YWMwMFx1Yjg1Y1x1YzkwNCwgMyozXHViYzE1XHVjMmE0LCBcdWMxMzhcdWI4NWNcdWM5MDRcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzc0IFx1YzgwNFx1ZDYwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwKSBcdWM3NzRcdWI3ZjAgXHVhY2JkXHVjNmIwXHViM2M0IFx1ZDMxMFx1YmNjNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgOVx1YWMxY1x1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM5MDRcdWM3NDAgOVx1YWMxYyBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYjM4XHVjNzkwXHViMjk0IDF+OSBcdWMyMmJcdWM3OTAgXHViNjEwXHViMjk0ICYjMzk7LiYjMzk7XHVjNzc0XHViMmU0LiBcdWI5YzhcdWNlNjhcdWQ0NWNcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNjJjXHViYzE0XHViOTc4IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzRcdWFjZTAsIFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0LCBcdWM3ODVcdWI4MjVcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBjcm9zcy1oYXRjaGluZ1x1YjljY1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkNDdjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgJnF1b3Q7RVJST1ImcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjMzBkXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNST1NTIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZ2FtZSBvZiBTdWRva3UsIHRoZSBvYmplY3RpdmUgaXMgdG8gcGxhY2UgaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCA5IChpbmNsdXNpdmUpIGludG8gYSA5eDkgZ3JpZCBzbyB0aGF0IGVhY2ggcm93LCBlYWNoIGNvbHVtbiwgYW5kIGVhY2ggb2YgdGhlIG5pbmUgM3gzIGJveGVzIGNvbnRhaW5zIGFsbCBuaW5lIG51bWJlcnMuIFRoZSBzdGFydGluZyBib2FyZCBpcyBwYXJ0aWFsbHkgZmlsbGVkIGluIHNvIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gbG9naWNhbGx5IGRlZHVjZSB0aGUgdmFsdWVzIG9mIHRoZSBvdGhlciBjZWxscy4gU3Vkb2t1IHB1enpsZXMgcmFuZ2UgaW4gZGlmZmljdWx0eSwgYW5kIGNvbXBsZXggYW5hbHlzaXMgbWV0aG9kcyBhcmUgcmVxdWlyZWQgdG8gc29sdmUgdGhlIGhhcmRlc3QgcHV6emxlcy4gSW4gdGhpcyBwcm9ibGVtLCBob3dldmVyLCB5b3Ugd2lsbCBpbXBsZW1lbnQgb25lIG9mIHRoZSBzaW1wbGVzdCBtZXRob2RzLCBjcm9zcy1oYXRjaGluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gY3Jvc3MtaGF0Y2hpbmcsIHdlIHNlbGVjdCBvbmUgb2YgdGhlIG5pbmUgbnVtYmVycyBhbmQsIGZvciBlYWNoIG9mIGl0cyBvY2N1cnJlbmNlcyBpbiB0aGUgZ3JpZCwgY3Jvc3Mgb3V0IHRoZSBjb3JyZXNwb25kaW5nIHJvdywgY29sdW1uIGFuZCAzeDMgYm94LiBOb3cgbG9vayBmb3IgYW55IDN4MyBib3hlcyB3aGVyZSB0aGVyZSBpcyBvbmx5IG9uZSBwb3NzaWJsZSBwbGFjZW1lbnQgZm9yIHRoZSBudW1iZXIgYW5kIHBsYWNlIGl0IHRoZXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgaW1hZ2UgYmVsb3cgc2hvd3MgYSB2ZXJ5IHNwYXJzZWx5IGZpbGxlZCBpbiBTdWRva3UgZ3JpZC4gSG93ZXZlciwgZXZlbiBpbiB0aGlzIGdyaWQgaXQgaXMgcG9zc2libGUgdG8gZGVkdWNlIHVzaW5nIGNyb3NzLWhhdGNoaW5nIHRoYXQgdGhlIG51bWJlciBpbiB0aGUgdG9wIGxlZnQgY2VsbCBpcyA0LCBhcyBpbGx1c3RyYXRlZCBpbiB0aGUgc2Vjb25kIGltYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzdiY2MzOWUzLTdiOTgtNGJhZi1hODI5LWZjZGY4M2NmZGRkOVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzg3cHg7IGhlaWdodDogMTYxcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgcGFydGlhbGx5IGZpbGxlZC1pbiBncmlkLiBZb3VyIHRhc2sgaXMgdG8gcmVwZWF0ZWRseSBhcHBseSB0aGUgY3Jvc3MtaGF0Y2hpbmcgbWV0aG9kIGZvciBkaWZmZXJlbnQgbnVtYmVycyB1bnRpbCBubyBtb3JlIGRlZHVjdGlvbnMgY2FuIGJlIG1hZGUgYWJvdXQgYW55IG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGluaXRpYWwgcGxhY2VtZW50IG9mIHRoZSBudW1iZXJzIGluIHRoZSBncmlkIG1heSBiZSBpbnZhbGlkLiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRoYXQgdGhlcmUgd2lsbCBiZSBubyBhdmFpbGFibGUgY2VsbCBmb3IgYSBudW1iZXIgaW4gYSAzeDMgYm94LiBJbiBib3RoIGNhc2VzLCB5b3UgYXJlIHRvIHJlcG9ydCBhbiBlcnJvcjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIDkgbGluZXMsIGVhY2ggY29udGFpbmluZyBleGFjdGx5IDkgY2hhcmFjdGVycy4gRWFjaCBjaGFyYWN0ZXIgd2lsbCBlaXRoZXIgYmUgYSBkaWdpdCBiZXR3ZWVuIDEgYW5kIDksIG9yIGEgcGVyaW9kICgmIzM5Oy4mIzM5OykgZGVub3RpbmcgYW4gZW1wdHkgY2VsbC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGUgaW5wdXQgaXMgdmFsaWQgYW5kIHRoZXJlIGlzIG5vIGNvbnRyYWRpY3Rpb24gd2hpbGUgc29sdmluZywgeW91IHNob3VsZCBvdXRwdXQgdGhlIGdyaWQgaW4gdGhlIHNhbWUgZm9ybWF0IGl0IHdhcyBnaXZlbiBpbiwgd2l0aCBjZWxscyBmaWxsZWQgaW4gaWYgdGhlaXIgdmFsdWUgY2FuIGJlIGRlZHVjZWQgdXNpbmcgY3Jvc3MtaGF0Y2hpbmcuIE90aGVyd2lzZSwgb3V0cHV0ICZxdW90O0VSUk9SJnF1b3Q7IChxdW90ZXMgZm9yIGNsYXJpdHkpLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #3 3번