시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 308 21 17 30.909%

문제

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+XHJcblx0TipOIFx1YmNmNFx1YjRkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1ZDAzOFx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWQwMzhcdWM3NzQgXHVhY2Y1XHVhY2E5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWIxOTNcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWJhODdcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IE4mZ3Q7M1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxYyBcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Yzk5ZFx1YmE4NVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIE49MjZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIDIyMzE3Njk5NjE2MzY0MDQ0XHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgTipOIFx1YmNmNFx1YjRkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1ZDAzOFx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWQwMzhcdWM3NzQgXHVhY2Y1XHVhY2E5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWIxOTNcdWIyOTQgXHVkNTVjXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgOCwgMjYsIDIxMywgMjAxMiwgOTk5OTEsIDk5OTk5XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHROXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBpXHViYzg4XHVjN2FjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWQ1ODlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDAzOFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTiBRdWVlbnMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnF1ZWVuLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxNTFweDsgd2lkdGg6MTQ4cHhcIiBcLz5UaGVyZSBpcyB3ZWxsXHUyMDEwa25vd24gdGFzayB0byBwbGFjZSA4IGNoZXNzIHF1ZWVucyBvbiB0aGUgb3JpZ2luYWwgOCZ0aW1lczs4IGNoZXNzYm9hcmQgaW4gYSB3YXkgdGhhdCBubyB0d28gb2YgdGhlbSBhdHRhY2sgZWFjaCBvdGhlci4gQSBxdWVlbiBhdHRhY2tzIGFsbCBjZWxsc3RoYXQgYXJlIGluIHRoZSBzYW1lIHJvdywgc2FtZSBjb2x1bW4gb3Igc2FtZSBkaWFnb25hbCB3aXRoIGl0LiBPbmUgb2YgdGhlIHNvbHV0aW9ucyBpcyBzaG93biBvbiB0aGUgZmlndXJlLjxcL3A+XHJcblxyXG48cD5UaGUgZ2VuZXJhbGlzZWQgcHJvYmxlbSB3YXMgcG9zZWQgYnkgRnJhbnogTmF1Y2sgaW4gMTg1MCBhbmQgYXNrc2luIGhvdyBtYW55IHdheXMgTiBxdWVlbnMgY2FuIGJlIHBsYWNlZCBvbiBhbiBOJnRpbWVzO04gYm9hcmQgc28gdGhhdCBubyB0d28gcXVlZW5zIGF0dGFjayBlYWNoIG90aGVyLiBJdCBoYXMgYmVlbiBwcm92ZW4gdGhhdCBmb3IgTiZndDszIHRoZXJlIGFsd2F5cyBleGlzdHMgYXQgbGVhc3Qgb25lIHNvbHV0aW9uLiBGb3IgZXhhbXBsZSwgZm9yIE49MjYgdGhlcmUgYXJlIDIyMzE3Njk5NjE2MzY0MDQ0IGRpZmZlcmVudCBzb2x1dGlvbnMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgYXNrZWQgdG8gc29sdmUgYSBzbGlnaHRseSBkaWZmZXJlbnQgdGFzayAmbmRhc2g7IGZpbmQgYW55IG9uZSBzb2x1dGlvbiAoY29ycmVjdCBwbGFjZW1lbnQgb2YgTiBxdWVlbnMgb24gYW4gTiZ0aW1lcztOIGJvYXJkKSBmb3IgZml2ZSBnaXZlbiB2YWx1ZXMgb2YgTiBhbmQgc3VibWl0IGFuIG91dHB1dCBmaWxlIGZvciBlYWNoIHNvbHV0aW9uOjxcL3A+XHJcbiIsImlucHV0IjoiPHA+TiA9IDgsIDI2LCAyMTMsIDIwMTIsIDk5OTkxLCA5OTk5OTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSB0ZXh0IGZpbGUgd2l0aCB0aGUgc3BlY2lmaWVkIG5hbWUgdGhlcmUgbXVzdCBiZSBOIHJvd3MuIEZvciBlYWNoIGkoMSAmbGU7IGkgJmxlOyBOKSB0aGUgaVx1MjAxMHRoIHJvdyBvZiB0aGUgZmlsZSBtdXN0IGNvbnRhaW4gZXhhY3RseSBvbmUgaW50ZWdlciAmbmRhc2g7IHRoZSBudW1iZXIgb2YgdGhlIGNvbHVtbiB3aGVyZSB0aGUgcXVlZW4gaW4gdGhlIGlcdTIwMTB0aCByb3cgaXMgcGxhY2VkLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgeW91IHdvdWxkIGJlIGFza2VkIHRvIHN1Ym1pdCBhIHNvbHV0aW9uIGZvciBlaWdodCBxdWVlbnMsIHRoZW4gYSB2YWxpZCBvdXRwdXQgZmlsZSBjb250ZW50IG1pZ2h0IGJlIChjb3JyZXNwb25kcyB0byB0aGUgcGljdHVyZSBhYm92ZTsgcm93cyBhcmUgbnVtYmVyZWQgZnJvbXRvcCB0byBib3R0b20sIGNvbHVtbnMgYXJlIG51bWJlcmVkIGZyb21sZWZ0dG8gcmlnaHQpOjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 P2번