시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52 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+XHJcblxyXG48cD5cclxuXHRcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzVkMFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzkxMSBcdWQ1NWNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzQwIENyb3NzLWhhdGNoaW5nXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRDcm9zcy1oYXRjaGluZ1x1YmMyOVx1YmM5NVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWJhM2NcdWM4MDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWFjZThcdWI3N2NcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjAgXHViNGE0XHVjNWQwLCBcdWFkZjggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWI4NWNcdWM5MDRcdWM3NzRcdWIwOTggXHVjMTM4XHViODVjXHVjOTA0IFx1YjYxMFx1YjI5NCAzKjMgXHViYzE1XHVjMmE0XHVjNWQwIFx1YzEyMFx1Yzc0NCBcdWFlMGJcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMxMjBcdWM3NDQgXHVhZGY4XHVjNWM4XHVjNzQ0IFx1YjU0YywgMyozXHViYzE1XHVjMmE0XHVjNWQwIFx1YWNlMFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0IFx1ZDU1YyBcdWNlNzhcdWM3N2MgXHViNTRjLCBcdWFkZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmMgXHVjOTExIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViOWU0XHVjNmIwIFx1Yzg3MFx1YWUwOFx1YjljYyBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjYzQ0XHVjNmNjXHVjOWM0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBjcm9zcy1oYXRjaGluZyBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIDRcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzQ0IFx1Y2MzZVx1Yzc0MCBcdWQ1NWNcdWFjMDBcdWM5YzAgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Nkay5wbmdcIiBzdHlsZT1cIndpZHRoOiA0MDdweDsgaGVpZ2h0OiAxNzRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViZDgwXHViZDg0XHVjODAxXHVjNzNjXHViODVjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWNjNDRcdWM2Y2NcdWM5YzQgXHVjMmE0XHViM2M0XHVjZmUwIFx1ZDM3Y1x1Yzk5MFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBjcm9zcy1oYXRjaGluZ1x1YmMyOVx1YmM5NVx1YjljY1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIzNTRcdWM3NzRcdWMwYzEgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWM3NDQgXHViNTRjIFx1YWU0Y1x1YzljMCBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDgwXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzYwOCwgXHVkNTVjIFx1YWMwMFx1Yjg1Y1x1YzkwNFx1YzVkMCAxXHVjNzc0IDJcdWFjMWMgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCwgXHVjMjJiXHVjNzkwIDFcdWM3NzQgXHVjNWI0XHViNWE0IFx1YWMwMFx1Yjg1Y1x1YzkwNCwgMyozXHViYzE1XHVjMmE0LCBcdWMxMzhcdWI4NWNcdWM5MDRcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzc0IFx1YzgwNFx1ZDYwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwKSBcdWM3NzRcdWI3ZjAgXHVhY2JkXHVjNmIwXHViM2M0IFx1ZDMxMFx1YmNjNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgOVx1YWMxY1x1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM5MDRcdWM3NDAgOVx1YWMxYyBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYjM4XHVjNzkwXHViMjk0IDF+OSBcdWMyMmJcdWM3OTAgXHViNjEwXHViMjk0ICYjMzk7LiYjMzk7XHVjNzc0XHViMmU0LiBcdWI5YzhcdWNlNjhcdWQ0NWNcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjNjJjXHViYzE0XHViOTc4IFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NzRcdWFjZTAsIFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0LCBcdWM3ODVcdWI4MjVcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBjcm9zcy1oYXRjaGluZ1x1YjljY1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkNDdjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgJnF1b3Q7RVJST1ImcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjMzBkXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNST1NTIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZ2FtZSBvZiBTdWRva3UsIHRoZSBvYmplY3RpdmUgaXMgdG8gcGxhY2UgaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCA5IChpbmNsdXNpdmUpIGludG8gYSA5eDkgZ3JpZCBzbyB0aGF0IGVhY2ggcm93LCBlYWNoIGNvbHVtbiwgYW5kIGVhY2ggb2YgdGhlIG5pbmUgM3gzIGJveGVzIGNvbnRhaW5zIGFsbCBuaW5lIG51bWJlcnMuIFRoZSBzdGFydGluZyBib2FyZCBpcyBwYXJ0aWFsbHkgZmlsbGVkIGluIHNvIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gbG9naWNhbGx5IGRlZHVjZSB0aGUgdmFsdWVzIG9mIHRoZSBvdGhlciBjZWxscy4gU3Vkb2t1IHB1enpsZXMgcmFuZ2UgaW4gZGlmZmljdWx0eSwgYW5kIGNvbXBsZXggYW5hbHlzaXMgbWV0aG9kcyBhcmUgcmVxdWlyZWQgdG8gc29sdmUgdGhlIGhhcmRlc3QgcHV6emxlcy4gSW4gdGhpcyBwcm9ibGVtLCBob3dldmVyLCB5b3Ugd2lsbCBpbXBsZW1lbnQgb25lIG9mIHRoZSBzaW1wbGVzdCBtZXRob2RzLCBjcm9zcy1oYXRjaGluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gY3Jvc3MtaGF0Y2hpbmcsIHdlIHNlbGVjdCBvbmUgb2YgdGhlIG5pbmUgbnVtYmVycyBhbmQsIGZvciBlYWNoIG9mIGl0cyBvY2N1cnJlbmNlcyBpbiB0aGUgZ3JpZCwgY3Jvc3Mgb3V0IHRoZSBjb3JyZXNwb25kaW5nIHJvdywgY29sdW1uIGFuZCAzeDMgYm94LiBOb3cgbG9vayBmb3IgYW55IDN4MyBib3hlcyB3aGVyZSB0aGVyZSBpcyBvbmx5IG9uZSBwb3NzaWJsZSBwbGFjZW1lbnQgZm9yIHRoZSBudW1iZXIgYW5kIHBsYWNlIGl0IHRoZXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgaW1hZ2UgYmVsb3cgc2hvd3MgYSB2ZXJ5IHNwYXJzZWx5IGZpbGxlZCBpbiBTdWRva3UgZ3JpZC4gSG93ZXZlciwgZXZlbiBpbiB0aGlzIGdyaWQgaXQgaXMgcG9zc2libGUgdG8gZGVkdWNlIHVzaW5nIGNyb3NzLWhhdGNoaW5nIHRoYXQgdGhlIG51bWJlciBpbiB0aGUgdG9wIGxlZnQgY2VsbCBpcyA0LCBhcyBpbGx1c3RyYXRlZCBpbiB0aGUgc2Vjb25kIGltYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Nkay5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzRweDsgd2lkdGg6NDA3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gYSBwYXJ0aWFsbHkgZmlsbGVkLWluIGdyaWQuIFlvdXIgdGFzayBpcyB0byByZXBlYXRlZGx5IGFwcGx5IHRoZSBjcm9zcy1oYXRjaGluZyBtZXRob2QgZm9yIGRpZmZlcmVudCBudW1iZXJzIHVudGlsIG5vIG1vcmUgZGVkdWN0aW9ucyBjYW4gYmUgbWFkZSBhYm91dCBhbnkgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5pdGlhbCBwbGFjZW1lbnQgb2YgdGhlIG51bWJlcnMgaW4gdGhlIGdyaWQgbWF5IGJlIGludmFsaWQuIEl0IGlzIGFsc28gcG9zc2libGUgdGhhdCB0aGVyZSB3aWxsIGJlIG5vIGF2YWlsYWJsZSBjZWxsIGZvciBhIG51bWJlciBpbiBhIDN4MyBib3guIEluIGJvdGggY2FzZXMsIHlvdSBhcmUgdG8gcmVwb3J0IGFuIGVycm9yPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2YgOSBsaW5lcywgZWFjaCBjb250YWluaW5nIGV4YWN0bHkgOSBjaGFyYWN0ZXJzLiBFYWNoIGNoYXJhY3RlciB3aWxsIGVpdGhlciBiZSBhIGRpZ2l0IGJldHdlZW4gMSBhbmQgOSwgb3IgYSBwZXJpb2QgKCYjMzk7LiYjMzk7KSBkZW5vdGluZyBhbiBlbXB0eSBjZWxsLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZSBpbnB1dCBpcyB2YWxpZCBhbmQgdGhlcmUgaXMgbm8gY29udHJhZGljdGlvbiB3aGlsZSBzb2x2aW5nLCB5b3Ugc2hvdWxkIG91dHB1dCB0aGUgZ3JpZCBpbiB0aGUgc2FtZSBmb3JtYXQgaXQgd2FzIGdpdmVuIGluLCB3aXRoIGNlbGxzIGZpbGxlZCBpbiBpZiB0aGVpciB2YWx1ZSBjYW4gYmUgZGVkdWNlZCB1c2luZyBjcm9zcy1oYXRjaGluZy4gT3RoZXJ3aXNlLCBvdXRwdXQgJnF1b3Q7RVJST1ImcXVvdDsgKHF1b3RlcyBmb3IgY2xhcml0eSkuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d