시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 24 21 36.842%

문제

스도쿠는 가로 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.......
.........
.........
.........
.........
W3sicHJvYmxlbV9pZCI6IjI5NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWNmZTAgXHVkNDgwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgXHVhYzAwXHViODVjIDlcdWNlNzgsIFx1YzEzOFx1Yjg1YyA5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVkNDVjXHVjNWQwIDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzQ0XHVjNmNjIFx1YjEyM1x1YjI5NCBcdWQzN2NcdWM5OTBcdWM3NzRcdWIyZTQuIFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0NzhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YWMwMSBcdWFjMDBcdWI4NWNcdWM5MDRcdWFjZmMgXHVjMTM4XHViODVjXHVjOTA0XHVjNWQwIDFcdWM1ZDBcdWMxMWMgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIxMjNcdWFjZTAsIDMqM1x1Y2U3OFx1Yzc1OCBcdWM3OTFcdWM3NDAgXHVhY2E5XHVjNzkwXHVjNWQwXHViM2M0IDFcdWM1ZDBcdWMxMWMgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWIxMjNcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzVkMFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWM5MTEgXHVkNTVjXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc0MCBDcm9zcy1oYXRjaGluZ1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Q3Jvc3MtaGF0Y2hpbmdcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YjU0Y1x1YjI5NCwgXHViYTNjXHVjODAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVhY2U4XHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwIFx1YjRhNFx1YzVkMCwgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVhYzAwXHViODVjXHVjOTA0XHVjNzc0XHViMDk4IFx1YzEzOFx1Yjg1Y1x1YzkwNCBcdWI2MTBcdWIyOTQgMyozIFx1YmMxNVx1YzJhNFx1YzVkMCBcdWMxMjBcdWM3NDQgXHVhZTBiXHViMjk0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YzVjOFx1Yzc0NCBcdWI1NGMsIDMqM1x1YmMxNVx1YzJhNFx1YzVkMCBcdWFjZTBcdWI5NzggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NCBcdWQ1NWMgXHVjZTc4XHVjNzdjIFx1YjU0YywgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIFx1YzkxMSBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM4NzBcdWFlMDhcdWI5Y2MgXHVjMjJiXHVjNzkwXHVhYzAwIFx1Y2M0NFx1YzZjY1x1YzljNCBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgY3Jvc3MtaGF0Y2hpbmcgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyA0XHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0NCBcdWNjM2VcdWM3NDAgXHVkNTVjXHVhYzAwXHVjOWMwIFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZGsucG5nXCIgc3R5bGU9XCJ3aWR0aDogNDA3cHg7IGhlaWdodDogMTc0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmQ4MFx1YmQ4NFx1YzgwMVx1YzczY1x1Yjg1YyBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjYzQ0XHVjNmNjXHVjOWM0IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgY3Jvc3MtaGF0Y2hpbmdcdWJjMjlcdWJjOTVcdWI5Y2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0NzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViMzU0XHVjNzc0XHVjMGMxIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDQ4MCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMmE0XHViM2M0XHVjZmUwIFx1ZDM3Y1x1Yzk5MFx1Yzc3NCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNjA4LCBcdWQ1NWMgXHVhYzAwXHViODVjXHVjOTA0XHVjNWQwIDFcdWM3NzQgMlx1YWMxYyBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwLCBcdWMyMmJcdWM3OTAgMVx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVhYzAwXHViODVjXHVjOTA0LCAzKjNcdWJjMTVcdWMyYTQsIFx1YzEzOFx1Yjg1Y1x1YzkwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzQgXHVjODA0XHVkNjAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjApIFx1Yzc3NFx1YjdmMCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVkMzEwXHViY2M0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCA5XHVhYzFjXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxIFx1YzkwNFx1Yzc0MCA5XHVhYzFjIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiMzhcdWM3OTBcdWIyOTQgMX45IFx1YzIyYlx1Yzc5MCBcdWI2MTBcdWIyOTQgJiMzOTsuJiMzOTtcdWM3NzRcdWIyZTQuIFx1YjljOFx1Y2U2OFx1ZDQ1Y1x1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM2MmNcdWJjMTRcdWI5NzggXHVjMmE0XHViM2M0XHVjZmUwIFx1ZDM3Y1x1Yzk5MFx1Yzc3NFx1YWNlMCwgXHViYWE4XHVjMjFjXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQsIFx1Yzc4NVx1YjgyNVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIGNyb3NzLWhhdGNoaW5nXHViOWNjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQ0N2MgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAmcXVvdDtFUlJPUiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWMzMGRcdWI1MzBcdWM2MzRcdWQ0NWNcdWIyOTQgXHVjZDljXHViODI1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNCk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ1JPU1MiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBnYW1lIG9mIFN1ZG9rdSwgdGhlIG9iamVjdGl2ZSBpcyB0byBwbGFjZSBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIDkgKGluY2x1c2l2ZSkgaW50byBhIDl4OSBncmlkIHNvIHRoYXQgZWFjaCByb3csIGVhY2ggY29sdW1uLCBhbmQgZWFjaCBvZiB0aGUgbmluZSAzeDMgYm94ZXMgY29udGFpbnMgYWxsIG5pbmUgbnVtYmVycy4gVGhlIHN0YXJ0aW5nIGJvYXJkIGlzIHBhcnRpYWxseSBmaWxsZWQgaW4gc28gdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBsb2dpY2FsbHkgZGVkdWNlIHRoZSB2YWx1ZXMgb2YgdGhlIG90aGVyIGNlbGxzLiBTdWRva3UgcHV6emxlcyByYW5nZSBpbiBkaWZmaWN1bHR5LCBhbmQgY29tcGxleCBhbmFseXNpcyBtZXRob2RzIGFyZSByZXF1aXJlZCB0byBzb2x2ZSB0aGUgaGFyZGVzdCBwdXp6bGVzLiBJbiB0aGlzIHByb2JsZW0sIGhvd2V2ZXIsIHlvdSB3aWxsIGltcGxlbWVudCBvbmUgb2YgdGhlIHNpbXBsZXN0IG1ldGhvZHMsIGNyb3NzLWhhdGNoaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBjcm9zcy1oYXRjaGluZywgd2Ugc2VsZWN0IG9uZSBvZiB0aGUgbmluZSBudW1iZXJzIGFuZCwgZm9yIGVhY2ggb2YgaXRzIG9jY3VycmVuY2VzIGluIHRoZSBncmlkLCBjcm9zcyBvdXQgdGhlIGNvcnJlc3BvbmRpbmcgcm93LCBjb2x1bW4gYW5kIDN4MyBib3guIE5vdyBsb29rIGZvciBhbnkgM3gzIGJveGVzIHdoZXJlIHRoZXJlIGlzIG9ubHkgb25lIHBvc3NpYmxlIHBsYWNlbWVudCBmb3IgdGhlIG51bWJlciBhbmQgcGxhY2UgaXQgdGhlcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBpbWFnZSBiZWxvdyBzaG93cyBhIHZlcnkgc3BhcnNlbHkgZmlsbGVkIGluIFN1ZG9rdSBncmlkLiBIb3dldmVyLCBldmVuIGluIHRoaXMgZ3JpZCBpdCBpcyBwb3NzaWJsZSB0byBkZWR1Y2UgdXNpbmcgY3Jvc3MtaGF0Y2hpbmcgdGhhdCB0aGUgbnVtYmVyIGluIHRoZSB0b3AgbGVmdCBjZWxsIGlzIDQsIGFzIGlsbHVzdHJhdGVkIGluIHRoZSBzZWNvbmQgaW1hZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2RrLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NHB4OyB3aWR0aDo0MDdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiBhIHBhcnRpYWxseSBmaWxsZWQtaW4gZ3JpZC4gWW91ciB0YXNrIGlzIHRvIHJlcGVhdGVkbHkgYXBwbHkgdGhlIGNyb3NzLWhhdGNoaW5nIG1ldGhvZCBmb3IgZGlmZmVyZW50IG51bWJlcnMgdW50aWwgbm8gbW9yZSBkZWR1Y3Rpb25zIGNhbiBiZSBtYWRlIGFib3V0IGFueSBudW1iZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbml0aWFsIHBsYWNlbWVudCBvZiB0aGUgbnVtYmVycyBpbiB0aGUgZ3JpZCBtYXkgYmUgaW52YWxpZC4gSXQgaXMgYWxzbyBwb3NzaWJsZSB0aGF0IHRoZXJlIHdpbGwgYmUgbm8gYXZhaWxhYmxlIGNlbGwgZm9yIGEgbnVtYmVyIGluIGEgM3gzIGJveC4gSW4gYm90aCBjYXNlcywgeW91IGFyZSB0byByZXBvcnQgYW4gZXJyb3I8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiA5IGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgZXhhY3RseSA5IGNoYXJhY3RlcnMuIEVhY2ggY2hhcmFjdGVyIHdpbGwgZWl0aGVyIGJlIGEgZGlnaXQgYmV0d2VlbiAxIGFuZCA5LCBvciBhIHBlcmlvZCAoJiMzOTsuJiMzOTspIGRlbm90aW5nIGFuIGVtcHR5IGNlbGwuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlIGlucHV0IGlzIHZhbGlkIGFuZCB0aGVyZSBpcyBubyBjb250cmFkaWN0aW9uIHdoaWxlIHNvbHZpbmcsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSBncmlkIGluIHRoZSBzYW1lIGZvcm1hdCBpdCB3YXMgZ2l2ZW4gaW4sIHdpdGggY2VsbHMgZmlsbGVkIGluIGlmIHRoZWlyIHZhbHVlIGNhbiBiZSBkZWR1Y2VkIHVzaW5nIGNyb3NzLWhhdGNoaW5nLiBPdGhlcndpc2UsIG91dHB1dCAmcXVvdDtFUlJPUiZxdW90OyAocXVvdGVzIGZvciBjbGFyaXR5KS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=