시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 50 17 15 34.091%

문제

스도쿠는 가로 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+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmQ4MFx1YmQ4NFx1YzgwMVx1YzczY1x1Yjg1YyBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjYzQ0XHVjNmNjXHVjOWM0IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgY3Jvc3MtaGF0Y2hpbmdcdWJjMjlcdWJjOTVcdWI5Y2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0NzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViMzU0XHVjNzc0XHVjMGMxIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDQ4MCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyYTRcdWIzYzRcdWNmZTAgXHVkMzdjXHVjOTkwXHVjNzc0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM2MDgsIFx1ZDU1YyBcdWFjMDBcdWI4NWNcdWM5MDRcdWM1ZDAgMVx1Yzc3NCAyXHVhYzFjIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjAsIFx1YzIyYlx1Yzc5MCAxXHVjNzc0IFx1YzViNFx1YjVhNCBcdWFjMDBcdWI4NWNcdWM5MDQsIDMqM1x1YmMxNVx1YzJhNCwgXHVjMTM4XHViODVjXHVjOTA0XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc3NCBcdWM4MDRcdWQ2MDAgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMCkgXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YjNjNCBcdWQzMTBcdWJjYzRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIDlcdWFjMWNcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIDlcdWFjMWMgXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YjI5NCAxfjkgXHVjMjJiXHVjNzkwIFx1YjYxMFx1YjI5NCAmIzM5Oy4mIzM5O1x1Yzc3NFx1YjJlNC4gXHViOWM4XHVjZTY4XHVkNDVjXHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWMyYTRcdWIzYzRcdWNmZTAgXHVkMzdjXHVjOTkwXHVjNzc0XHVhY2UwLCBcdWJhYThcdWMyMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgXHVjNzg1XHViODI1XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgY3Jvc3MtaGF0Y2hpbmdcdWI5Y2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDQ3YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0ICZxdW90O0VSUk9SJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YzMwZFx1YjUzMFx1YzYzNFx1ZDQ1Y1x1YjI5NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDUk9TUyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIGdhbWUgb2YgU3Vkb2t1LCB0aGUgb2JqZWN0aXZlIGlzIHRvIHBsYWNlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgOSAoaW5jbHVzaXZlKSBpbnRvIGEgOXg5IGdyaWQgc28gdGhhdCBlYWNoIHJvdywgZWFjaCBjb2x1bW4sIGFuZCBlYWNoIG9mIHRoZSBuaW5lIDN4MyBib3hlcyBjb250YWlucyBhbGwgbmluZSBudW1iZXJzLiBUaGUgc3RhcnRpbmcgYm9hcmQgaXMgcGFydGlhbGx5IGZpbGxlZCBpbiBzbyB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIGxvZ2ljYWxseSBkZWR1Y2UgdGhlIHZhbHVlcyBvZiB0aGUgb3RoZXIgY2VsbHMuIFN1ZG9rdSBwdXp6bGVzIHJhbmdlIGluIGRpZmZpY3VsdHksIGFuZCBjb21wbGV4IGFuYWx5c2lzIG1ldGhvZHMgYXJlIHJlcXVpcmVkIHRvIHNvbHZlIHRoZSBoYXJkZXN0IHB1enpsZXMuIEluIHRoaXMgcHJvYmxlbSwgaG93ZXZlciwgeW91IHdpbGwgaW1wbGVtZW50IG9uZSBvZiB0aGUgc2ltcGxlc3QgbWV0aG9kcywgY3Jvc3MtaGF0Y2hpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGNyb3NzLWhhdGNoaW5nLCB3ZSBzZWxlY3Qgb25lIG9mIHRoZSBuaW5lIG51bWJlcnMgYW5kLCBmb3IgZWFjaCBvZiBpdHMgb2NjdXJyZW5jZXMgaW4gdGhlIGdyaWQsIGNyb3NzIG91dCB0aGUgY29ycmVzcG9uZGluZyByb3csIGNvbHVtbiBhbmQgM3gzIGJveC4gTm93IGxvb2sgZm9yIGFueSAzeDMgYm94ZXMgd2hlcmUgdGhlcmUgaXMgb25seSBvbmUgcG9zc2libGUgcGxhY2VtZW50IGZvciB0aGUgbnVtYmVyIGFuZCBwbGFjZSBpdCB0aGVyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGltYWdlIGJlbG93IHNob3dzIGEgdmVyeSBzcGFyc2VseSBmaWxsZWQgaW4gU3Vkb2t1IGdyaWQuIEhvd2V2ZXIsIGV2ZW4gaW4gdGhpcyBncmlkIGl0IGlzIHBvc3NpYmxlIHRvIGRlZHVjZSB1c2luZyBjcm9zcy1oYXRjaGluZyB0aGF0IHRoZSBudW1iZXIgaW4gdGhlIHRvcCBsZWZ0IGNlbGwgaXMgNCwgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIHNlY29uZCBpbWFnZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZGsucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTc0cHg7IHdpZHRoOjQwN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgcGFydGlhbGx5IGZpbGxlZC1pbiBncmlkLiBZb3VyIHRhc2sgaXMgdG8gcmVwZWF0ZWRseSBhcHBseSB0aGUgY3Jvc3MtaGF0Y2hpbmcgbWV0aG9kIGZvciBkaWZmZXJlbnQgbnVtYmVycyB1bnRpbCBubyBtb3JlIGRlZHVjdGlvbnMgY2FuIGJlIG1hZGUgYWJvdXQgYW55IG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGluaXRpYWwgcGxhY2VtZW50IG9mIHRoZSBudW1iZXJzIGluIHRoZSBncmlkIG1heSBiZSBpbnZhbGlkLiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRoYXQgdGhlcmUgd2lsbCBiZSBubyBhdmFpbGFibGUgY2VsbCBmb3IgYSBudW1iZXIgaW4gYSAzeDMgYm94LiBJbiBib3RoIGNhc2VzLCB5b3UgYXJlIHRvIHJlcG9ydCBhbiBlcnJvcjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIDkgbGluZXMsIGVhY2ggY29udGFpbmluZyBleGFjdGx5IDkgY2hhcmFjdGVycy4gRWFjaCBjaGFyYWN0ZXIgd2lsbCBlaXRoZXIgYmUgYSBkaWdpdCBiZXR3ZWVuIDEgYW5kIDksIG9yIGEgcGVyaW9kICgmIzM5Oy4mIzM5OykgZGVub3RpbmcgYW4gZW1wdHkgY2VsbC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGUgaW5wdXQgaXMgdmFsaWQgYW5kIHRoZXJlIGlzIG5vIGNvbnRyYWRpY3Rpb24gd2hpbGUgc29sdmluZywgeW91IHNob3VsZCBvdXRwdXQgdGhlIGdyaWQgaW4gdGhlIHNhbWUgZm9ybWF0IGl0IHdhcyBnaXZlbiBpbiwgd2l0aCBjZWxscyBmaWxsZWQgaW4gaWYgdGhlaXIgdmFsdWUgY2FuIGJlIGRlZHVjZWQgdXNpbmcgY3Jvc3MtaGF0Y2hpbmcuIE90aGVyd2lzZSwgb3V0cHV0ICZxdW90O0VSUk9SJnF1b3Q7IChxdW90ZXMgZm9yIGNsYXJpdHkpLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==