* Засичащи се фигури
Публикувано на 19 февруари 2009 в раздел Математика.
В тази публикация ще ви дам две класически и една не чак толкова класическа задачи.
1. Осемте царици:
Вземете шахматна дъска и подредете осем царици така, че да не се „бият“ една друга.
2. N-те царици:
Напишете алгоритъм, по който да може с „n“ на брой итерации да се подредят „n“ на брой царици върху шахматна дъска с размери „n x n“. Както в първата задача, цариците не трябва да се поставят в поле, което е „бито“ от друга царица.
3. Четирите четворки фигури:
Нека имаме шахматна дъска с размери 4×4. Нека имаме четири пъти фигурата A, четири пъти фигурата B, четири пъти фигурата C и четири пъти фигурата D. Поставете всички фигури на дъската така, че да няма повтарящи се фигури по хоризонтала, вертикала и по двата главни диагонала.
Су До Ку
Е, не е точно судоку, но прилича :)
3
A B C D
C D A B
D C B A
B A D C
Много старомодни задачи: 8 царици!!! Дрън-дрън!
Че и да се бият. Я сложи по-добре 8 манекенки с прашки на подиума по-добре.
3 1 2 4
2 4 3 1
4 2 1 3
1 3 4 2
сигурно не е единствено решение
втора задача е некоректна – например за n=2 или n=3 няма решение
По втората точка ми е интересно само какво разбираш под „n“ на брой итерации. Защото повечето алгоритми, които решават тази задача са с рекурсия. Там итерации дефакто няма, освен ако всяко връщане назад в рекурсията не се смята за итерация. Хайде давай решението :)
Мертол – Не е некоректна. Това, което си открил е част от решението.
Светльо Антонов – Връщането от рекурсията определено си е итерация в рекурсивния алгоритъм. Въпросът е да напишете алгоритъм със сложност „n“ (решението, което всеки може да измисли веднага е със сложност n^2).
Hint: Започнете от малки дъски и постепенно ги увеличавайте. Намерете някаква зависимост между позициите, на които поставяте цариците и числото n… Аз лично когато писах такава програма си рисувах на ръка :)
айде давай решението със сложност n
1. При n=1 е ясно, че има само една царица и има решение.
2. При n=2 очевидно няма решение.
3. При n=3 също няма решение
4. При n=4 има (даже не единствено). Аз ще взема само едното от тях:
Виждате, че по колони поставих царица на 2ра и 4та позиция и на 1ва и 3та позиция. Нека продължим напред…
5. При n=5 решението е следното:
По колони сложих на 2ра, 4та, 1ва, 3та и 5та позиции. Изключително много прилича на предишното решение, не е ли така?
6. При n=6 правя следното:
Отново е много близко решение – 2ра, 4та, 6та, 1ва, 3та и 5та позиции. Ще проверя още веднъж и ще се опитам да направя заключение по индукция.
7. При n=7:
Изключителна прилика – 2ра, 4та, 6та, 1ва, 3та, 5та и 7ма…
Така смело бих обобщил алгоритъм – като се местите по редове, слагайте по една царица през две позиции надолу (2ра, 4та, 6та, 8ма,…) докато не стигнете края на дъската. След това се върнете в началото и започвайки от 1ва позиция слагайте отново през две надолу (1ва, 3та, 5та, 7ма, 9та, …) и така до достигане на последната колона.
Трудността на алгоритъма е точно „n“, защото се извършват точно „n“ на брой поставяния на царица. Тук обаче по стар спомен мисля, че може би имаше и частен случай. Пробвайте го на компютър и намерете дали няма изключителна ситуация при определени числа „n“. Не съм убеден – просто проверете и споделете…
Ами алгоритъмът ти се дъни още на първия случай който не си разгледал. При n = 8
0 0 0 0 x 0 0 0
x 0 0 0 0 0 0 0
0 0 0 0 0 x 0 0
0 x 0 0 0 0 0 0
0 0 0 0 0 0 x 0
0 0 x 0 0 0 0 0
0 0 0 0 0 0 0 x
0 0 0 x 0 0 0 0
По второстепенния диагонал две царици се засичат.
Не се заяждам, но без доказателство че си намерил решение, само по интуиция, не може да се смята че е верен алгоритъм. Аз например се опитвах точно с този метод да го решавам още от първия път, но за класическата шахматна дъска с 8х8, и веднага знам че по този начин не става. Подобна задача е например „Да се обходи стандартна шахматна дъска с ход на коня без да се повтаря два пъти нито едно поле“.
Относно рекурсията, в уикипедия има много обстойна статия как се решава тази задача, и какви оптимизации могат да се правят. Но според мен, така както го дефинираш, рекурсията не е решение от n-ти ред. Там разглеждат случая за n царици. Но алгоритъм с толкова ниска стойност като че ли никой досега не е намерил :)
Светослав Антонов – не случайно казах, че има частен случай – получава се при n = k.8, k=1,2,3… При него има друго – сходно алтернативно решение…
venelin – ще отговоря със задача – аз съм точно на два пъти повече години, отколкото си ти :)
po na kolko godini ste shtoto as sam na 13 i ot vas mai razbrah nqkolko dumi kakvo uzna4avat blagodarq vi vse pak
Задачата за н-те царици няма обща формула на броя на решенията, но пък може да се атакува с много разнообрани подходи – backtracking, constraint programming, рекурсии и т.н. Аз я използвах за тренирова, когато се учех на базовите елементи на програмирането
Лъчезар П. Томов – Пак казвам – тук не се търси изчерпване на решенията, а просто едно решение. Вече съм го описал по-горе.