문제
바다에서 수학을 좋아하기로 유명한 오징어의 취미는 스도쿠이다. 스도쿠는 9*9칸으로 이루어져 있으며, 3*3칸에 1~9까지가 1번씩, 각각의 가로줄에도 1번씩, 세로줄에도 1번씩 들어가게 만드는 게임이다.
오징어는 하루를 스도쿠와 함께 시작한다. 스도쿠를 푸는 오징어가 멋있어 보였던 새우는 오징어에게 문제지를 하나만 달라고 요청하였고, 오징어는 문제지를 복사해 주었다.
새우는 오징어보다 스도쿠를 먼저 풀어서 자랑하기 위해 프로그래밍으로 스도쿠를 풀어보려고 한다.
위의 모습 처럼 생긴 스도쿠가 있다면, 숫자는 숫자로, 빈 칸은 0으로 주어진다.
스도쿠를 입력받아 스도쿠를 푸는 프로그램을 작성하시오
출력
규칙을 지키면서 스도쿠를 풀 수 없는 경우에는
Could not complete this grid.
를 출력한다.
스도쿠를 풀 수 있는 경우에는 입력 형식대로 스도쿠를 9개 줄에 걸쳐서 출력한다.
각 테스트케이스 사이에는 빈 줄을 출력하며, 스도쿠를 풀 수 있는 경우에는 항상 정답이 유일한 것만 입력으로 주어진다.
예제 출력 1
481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371
Could not complete this grid.
W3sicHJvYmxlbV9pZCI6IjQwNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTQtXHVjMmE0LVx1YzJhNFx1YjNjNFx1Y2ZlMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzE0XHViMmU0XHVjNWQwXHVjMTFjIFx1YzIxOFx1ZDU1OVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWFlMzBcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzYyNFx1YzlkNVx1YzViNFx1Yzc1OCBcdWNkZThcdWJiZjhcdWIyOTQgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzc0XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgOSo5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIDMqM1x1Y2U3OFx1YzVkMCAxfjlcdWFlNGNcdWM5YzBcdWFjMDAgMVx1YmM4OFx1YzUyOSwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWMwMFx1Yjg1Y1x1YzkwNFx1YzVkMFx1YjNjNCAxXHViYzg4XHVjNTI5LCBcdWMxMzhcdWI4NWNcdWM5MDRcdWM1ZDBcdWIzYzQgMVx1YmM4OFx1YzUyOSBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjOGMgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHVjOWQ1XHVjNWI0XHViMjk0IFx1ZDU1OFx1YjhlOFx1Yjk3YyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM2NDAgXHVkNTY4XHVhZWQ4IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ3OFx1YjI5NCBcdWM2MjRcdWM5ZDVcdWM1YjRcdWFjMDAgXHViYTRiXHVjNzg4XHVjNWI0IFx1YmNmNFx1YzYwMFx1YjM1OCBcdWMwYzhcdWM2YjBcdWIyOTQgXHVjNjI0XHVjOWQ1XHVjNWI0XHVjNWQwXHVhYzhjIFx1YmIzOFx1YzgxY1x1YzljMFx1Yjk3YyBcdWQ1NThcdWIwOThcdWI5Y2MgXHViMmVjXHViNzdjXHVhY2UwIFx1YzY5NFx1Y2NhZFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHVjNjI0XHVjOWQ1XHVjNWI0XHViMjk0IFx1YmIzOFx1YzgxY1x1YzljMFx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NzQgXHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzhcdWM2YjBcdWIyOTQgXHVjNjI0XHVjOWQ1XHVjNWI0XHViY2Y0XHViMmU0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWJhM2NcdWM4MDAgXHVkNDgwXHVjNWI0XHVjMTFjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkXHVjNzNjXHViODVjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0ODBcdWM1YjRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdXN1c3Vkb2t1LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHViYWE4XHVjMmI1IFx1Y2M5OFx1YjdmYyBcdWMwZGRcdWFlMzQgXHVjMmE0XHViM2M0XHVjZmUwXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjg1YywgXHViZTQ4IFx1Y2U3OFx1Yzc0MCAwXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NCBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgOVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWM3NzQgNVx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbkNvdWxkIG5vdCBjb21wbGV0ZSB0aGlzIGdyaWQuPFwvcHJlPlxyXG5cclxuPHA+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjUgXHVkNjE1XHVjMmRkXHViMzAwXHViODVjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyA5XHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjODE1XHViMmY1XHVjNzc0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjODNcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0MDU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3UtU3UtU3Vkb2t1IiwiZGVzY3JpcHRpb24iOiI8cD5CeSBub3csIGV2ZXJ5b25lIGhhcyBwbGF5ZWQgU3Vkb2t1OiB5b3UmcnNxdW87cmUgZ2l2ZW4gYSA5LWJ5LTkgZ3JpZCBvZiBib3hlcyB3aGljaCB5b3UgYXJlIHRvIGZpbGwgaW4gd2l0aCB0aGUgZGlnaXRzIDEgdGhyb3VnaCA5IHNvIHRoYXQgMSkgZXZlcnkgcm93IGhhcyBhbGwgbmluZSBkaWdpdHMsIDIpIGV2ZXJ5IGNvbHVtbiBoYXMgYWxsIG5pbmUgZGlnaXRzLCBhbmQgMykgYWxsIG5pbmUgMy1ieS0zIHN1YmdyaWRzIGhhdmUgYWxsIG5pbmUgZGlnaXRzLiBUbyBzdGFydCB0aGUgZ2FtZSB5b3UgYXJlIGdpdmVuIGEgcGFydGlhbGx5IGNvbXBsZXRlZCBncmlkIGFuZCBhcmUgYXNrZWQgdG8gZmlsbCBpbiB0aGUgcmVtYWluZGVyIG9mIHRoZSBib3hlcy4gT25lIHN1Y2ggcHV6emxlIGlzIHNob3duIGJlbG93LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdXN1c3Vkb2t1LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5NHB4OyB3aWR0aDoyMzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGJlIGdpdmVuIFN1ZG9rdSBncmlkcyB3aGljaCB5b3UgaGF2ZSBuZWFybHkgY29tcGxldGVkOyBpbmRlZWQgeW91JnJzcXVvO3ZlIGZpbGxlZCBpbiBldmVyeSBib3ggZXhjZXB0IGZpdmUuIFlvdSBhcmUgYXNrZWQgdG8gY29tcGxldGUgdGhlIGdyaWQsIG9yIGRldGVybWluZSB0aGF0IGl0JnJzcXVvO3MgaW1wb3NzaWJsZS4gKFlvdSBtaWdodCBoYXZlIGFscmVhZHkgbWFkZSBhbiBlcnJvciEpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZSBhIG5lYXJseSBjb21wbGV0ZWQgU3Vkb2t1IGdyaWQgY29uc2lzdGluZyBvZiA5IGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgOSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNldCBvZiBkaWdpdHMgMCB0aHJvdWdoIDkuIFRoZXJlIHdpbGwgYmUgZXhhY3RseSBmaXZlIDAmcnNxdW87cyBpbiBlYWNoIHRlc3QgY2FzZSwgaW5kaWNhdGluZyB0aGUgZml2ZSB1bmZpbGxlZCBib3hlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHNob3VsZCBiZSBlaXRoZXI8XC9wPlxyXG5cclxuPHByZT5cclxuQ291bGQgbm90IGNvbXBsZXRlIHRoaXMgZ3JpZC48XC9wcmU+XHJcblxyXG48cD5pZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGNvbXBsZXRlIHRoZSBncmlkIGFjY29yZGluZyB0byB0aGUgcnVsZXMgb2YgdGhlIGdhbWUsIG9yIHRoZSBjb21wbGV0ZWQgZ3JpZCwgaW4gdGhlIGZvcm0gZ2l2ZW4gYmVsb3cuIChUaGVyZSBhcmUgbm8gYmxhbmsgc3BhY2VzIGluIHRoZSBvdXRwdXQuKSBJZiB0aGVyZSBpcyBhIHdheSB0byBjb21wbGV0ZSB0aGUgZ3JpZCwgaXQgd2lsbCBiZSB1bmlxdWUuIFNlcGFyYXRlIHRlc3QgY2FzZXMgd2l0aCBhIGJsYW5rIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==