시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 321 25 18 32.143%

문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?

이 문제는 N>3인 경우에 경우의 수가 적어도 1개 라는 것이 증명되어 있다. 예를 들어, N=26인 경우에 22317699616364044가지 방법이 있다.

N이 주어졌을 때, N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한가지 경우를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다.

출력

N개의 줄을 출력해야 한다. i번재 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다.

예제 입력 1

8

예제 출력 1

3
6
8
1
4
7
5
2
W3sicHJvYmxlbV9pZCI6IjMzNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOLVF1ZWVuIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQ4KjggXHVjY2I0XHVjMmE0XHViY2Y0XHViNGRjXHVjNWQwIDhcdWFjMWNcdWM3NTggXHVkMDM4XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFjZjVcdWFjYTlcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTU4XHVhYzhjIFx1YjE5M1x1YjI5NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjNzk4IFx1YzU0Y1x1YjgyNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LiBcdWQwMzhcdWM3NDAgXHVhYzE5XHVjNzQwIFx1ZDU4OSwgXHVjNWY0LCBcdWI2MTBcdWIyOTQgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViOWQwXHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1ZDU1Y1x1YWMwMFx1YzljMCBcdWM4MTVcdWIyZjVcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnF1ZWVuLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE0OHB4OyBoZWlnaHQ6IDE1MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWUwOCBcdWIzNTQgXHVjNzdjXHViYzE4XHVkNjU0XHViNDFjIFx1YmIzOFx1YzgxY1x1YjI5NCBGcmFueiBOYXVja1x1Yzc3NCAxODUwXHViMTQ0XHVjNWQwIFx1YzgxY1x1YWUzMFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0TipOIFx1YmNmNFx1YjRkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1ZDAzOFx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWQwMzhcdWM3NzQgXHVhY2Y1XHVhY2E5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWIxOTNcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWJhODcgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1YmIzOFx1YzgxY1x1YjI5NCBOJmd0OzNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWMgXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM5OWRcdWJhODVcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBOPTI2XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCAyMjMxNzY5OTYxNjM2NDA0NFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE4qTiBcdWJjZjRcdWI0ZGNcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWQwMzhcdWM3NDQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVkMDM4XHVjNzc0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWFjOGMgXHViMTkzXHViMjk0IFx1ZDU1Y1x1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIDgsIDI2LCAyMTMsIDIwMTIsIDk5OTkxLCA5OTk5OVx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0Tlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gaVx1YmM4OFx1YzdhYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IGlcdWJjODhcdWM5ZjggXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQwMzhcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik4gUXVlZW5zIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25xdWVlbi5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTUxcHg7IHdpZHRoOjE0OHB4XCIgXC8+VGhlcmUgaXMgd2VsbFx1MjAxMGtub3duIHRhc2sgdG8gcGxhY2UgOCBjaGVzcyBxdWVlbnMgb24gdGhlIG9yaWdpbmFsIDgmdGltZXM7OCBjaGVzc2JvYXJkIGluIGEgd2F5IHRoYXQgbm8gdHdvIG9mIHRoZW0gYXR0YWNrIGVhY2ggb3RoZXIuIEEgcXVlZW4gYXR0YWNrcyBhbGwgY2VsbHN0aGF0IGFyZSBpbiB0aGUgc2FtZSByb3csIHNhbWUgY29sdW1uIG9yIHNhbWUgZGlhZ29uYWwgd2l0aCBpdC4gT25lIG9mIHRoZSBzb2x1dGlvbnMgaXMgc2hvd24gb24gdGhlIGZpZ3VyZS48XC9wPlxyXG5cclxuPHA+VGhlIGdlbmVyYWxpc2VkIHByb2JsZW0gd2FzIHBvc2VkIGJ5IEZyYW56IE5hdWNrIGluIDE4NTAgYW5kIGFza3NpbiBob3cgbWFueSB3YXlzIE4gcXVlZW5zIGNhbiBiZSBwbGFjZWQgb24gYW4gTiZ0aW1lcztOIGJvYXJkIHNvIHRoYXQgbm8gdHdvIHF1ZWVucyBhdHRhY2sgZWFjaCBvdGhlci4gSXQgaGFzIGJlZW4gcHJvdmVuIHRoYXQgZm9yIE4mZ3Q7MyB0aGVyZSBhbHdheXMgZXhpc3RzIGF0IGxlYXN0IG9uZSBzb2x1dGlvbi4gRm9yIGV4YW1wbGUsIGZvciBOPTI2IHRoZXJlIGFyZSAyMjMxNzY5OTYxNjM2NDA0NCBkaWZmZXJlbnQgc29sdXRpb25zLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGFza2VkIHRvIHNvbHZlIGEgc2xpZ2h0bHkgZGlmZmVyZW50IHRhc2sgJm5kYXNoOyBmaW5kIGFueSBvbmUgc29sdXRpb24gKGNvcnJlY3QgcGxhY2VtZW50IG9mIE4gcXVlZW5zIG9uIGFuIE4mdGltZXM7TiBib2FyZCkgZm9yIGZpdmUgZ2l2ZW4gdmFsdWVzIG9mIE4gYW5kIHN1Ym1pdCBhbiBvdXRwdXQgZmlsZSBmb3IgZWFjaCBzb2x1dGlvbjo8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk4gPSA4LCAyNiwgMjEzLCAyMDEyLCA5OTk5MSwgOTk5OTk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgdGV4dCBmaWxlIHdpdGggdGhlIHNwZWNpZmllZCBuYW1lIHRoZXJlIG11c3QgYmUgTiByb3dzLiBGb3IgZWFjaCBpKDEgJmxlOyBpICZsZTsgTikgdGhlIGlcdTIwMTB0aCByb3cgb2YgdGhlIGZpbGUgbXVzdCBjb250YWluIGV4YWN0bHkgb25lIGludGVnZXIgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIHRoZSBjb2x1bW4gd2hlcmUgdGhlIHF1ZWVuIGluIHRoZSBpXHUyMDEwdGggcm93IGlzIHBsYWNlZC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHlvdSB3b3VsZCBiZSBhc2tlZCB0byBzdWJtaXQgYSBzb2x1dGlvbiBmb3IgZWlnaHQgcXVlZW5zLCB0aGVuIGEgdmFsaWQgb3V0cHV0IGZpbGUgY29udGVudCBtaWdodCBiZSAoY29ycmVzcG9uZHMgdG8gdGhlIHBpY3R1cmUgYWJvdmU7IHJvd3MgYXJlIG51bWJlcmVkIGZyb210b3AgdG8gYm90dG9tLCBjb2x1bW5zIGFyZSBudW1iZXJlZCBmcm9tbGVmdHRvIHJpZ2h0KTo8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 P2번