| [ QuizWit ] in KIDS 글 쓴 이(By): pomp (위풍당당) 날 짜 (Date): 1997년11월29일(토) 21시28분39초 ROK 제 목(Title): [문제] generalized 8 Queens 1. 다들 아는 문제부터... 8x8 짜리 체스판 위에 퀸을 늘어 놓아, 어느 것도 다른 퀸을 공격하지 못하게 하려고 합니다. 최고 몇 개의 퀸을 놓을 수 있을까요? 2. 이걸 일반화해서... 8x8 짜리 체스판 위에 퀸을 늘어 놓아, 어느 것도 딱 n 개의 퀸만을 공격할 수 있게 하려고 합니다. 최고 몇 개의 퀸을 놓을 수 있을까요? 아직 일반적인 풀이는 없는 걸로 알고 있습니다만, n=1일 때는 10 개, n=2일 때는 14 개라는 건 증명이 되어 있습니다. n=3일 때를 해 보세요. 누가 최고 기록을 세울까요? 자신있는 분은 n=1,2일 때의 풀이도 한 번 생각해 보시구요. n=4일 때도 해 보세요. 21 개가 최고 기록입니다. 그리고, 8x8이 아닌 mxm 체스판에 대해서도 한 번. n=1,2에 대해서는 좋은 upper bound가 주어져 있습니다. 이 문제들은 _Inversion_이란 책으로 유명한, 한국계 미국인 Scott Kim의 작품입니다. 이 사람 홈페이지가 아마 http://www.best.com/~scottkim일 겁니다. 한번 구경 가 보세요. 재미있을 겁니다. ... & circumstance |