ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 2 из 20
  2  все
Пятничная задачка для ума за 1 миллион $
    #39515367
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм... фракталы на loveorigami не могут красиво заполнить поле 1000х1000.

Приведен пример для квадрата 20x20 и 25х25. Он не кратен 1000х1000.

Нужно брать или 400х400 или 625Х625 или другие кратные.
...
Рейтинг: 0 / 0
04.09.2017, 22:18
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515379
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот как-то так. 1280 ферзей фракталом. Ну и всякие производные расстановки. Зеркально. Там. Поворот. Еще добавят штук 8 или 12 вариантов.

 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
/**
 * @author mayton
 *
 * @see "http://www.forum.loveorigami.info/viewtopic.php?f=21&t=564&start=30"
 */
public class Queen1000problem {

    public static int SIZE = 1280;

    public static int maxLevel = 0;

    public static int queens = 0;
    
    public static void setQueen(BufferedImage img,int x, int y){
        img.setRGB(x,y, 0xFF_00_00_FF);
        queens++;
    }

    public static void recurse5to5(BufferedImage img, int x, int y, int size, int level) {
        maxLevel = max(maxLevel, level);
        if (size > 5) {
            //System.out.printf("(%d,%d,%d)\n",x,y,size);
            int quarter = size / 4;
            recurse5to5(img, x + quarter,     y,               quarter, level + 1);
            recurse5to5(img, x + 3 * quarter, y + quarter,     quarter, level + 1);
            recurse5to5(img, x,               y + 2 * quarter, quarter, level + 1);
            recurse5to5(img, x + 2 * quarter, y + 3 * quarter, quarter, level + 1);
        } else {            
            setQueen(img,x + 1, y);
            setQueen(img,x + 4, y + 1);
            setQueen(img,x + 2, y + 2);
            setQueen(img,x,     y + 3);
            setQueen(img,x + 3, y + 4);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedImage img = new BufferedImage(SIZE, SIZE, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = img.createGraphics();
        g.setColor(Color.WHITE);
        g.fillRect(0,0,SIZE, SIZE);
        recurse5to5(img, 0, 0, SIZE, 0);
        ImageIO.write(img, "PNG", Files.newOutputStream(Paths.get(String.format("queen-solution-%dx%d.png",SIZE,SIZE))));
        System.out.printf("There are %d queens, with max level %d of recursion", queens, maxLevel);
    }

}

...
Рейтинг: 0 / 0
04.09.2017, 22:39
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515431
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonХм... фракталы на loveorigami не могут красиво заполнить поле 1000х1000.

Приведен пример для квадрата 20x20 и 25х25. Он не кратен 1000х1000.

Нужно брать или 400х400 или 625Х625 или другие кратные.

1000 = 10 * 10 * 10, сам автор по фрактальному методу и говорит, что нужно бить на простые множители. Кроме того это всё равно не избавляет от проверок диагоналей

По ссылкам, в оригинальной статье есть разбор существующих методов
...
Рейтинг: 0 / 0
05.09.2017, 06:45
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515439
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Оптимальный алгоритм для 8*8 разработан давно
Задаче 30лет точно.(Была включена в сборник олимпиадных задач по программированию 1980г)
Чем алгоритм для 8*8 может отличаться от алгоритма 10000*10000 ?.
...
Рейтинг: 0 / 0
05.09.2017, 08:01
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515448
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
982183, ты явно не в теме.
...
Рейтинг: 0 / 0
05.09.2017, 08:24
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515455
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
совершенно не в теме.
...
Рейтинг: 0 / 0
05.09.2017, 08:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515457
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
982183, алгоритм о котором ты говоришь - это поиск в глубину с возвратом
как мы уже выяснили имеет экспоненциальную сложность.

Для оптимизации на доске не ищутся не все клетки а заводится специальная
биткарта по вертикалям горизонталям и диагоналям. (Возможно это решение
и спрашивают на олимпиадах).

Но этот алгоритм не нравится Британским ботанам и они ищут другой.
...
Рейтинг: 0 / 0
05.09.2017, 08:44
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515471
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovСуществует 3 варианта задачи:
1 найти любое расположение, при котором ферзи не бьют друг друга,
2 найти все такие расположения,
3 найти количество таких расположений.

Какой из вариантов им нужен?
Им надо "быстро" решить задачу. Что значит быстро? За полиномиальное время? Время на одно расположение или на полное решение?
Что значит решить? Алгоритм? Или дать развернутый ответ? )

Оказывается, они решают другую задачу:

n-Queens Completion problemGiven an nn chessboard on which some queens are already
placed, can you place a queen in every remaining row so that no two queens attack each
other?
...
Рейтинг: 0 / 0
05.09.2017, 09:03
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515475
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не думаю что это другая задача.
...
Рейтинг: 0 / 0
05.09.2017, 09:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515487
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonЯ не думаю что это другая задача.

Ну, формулировки-то не совпадают.
Понятно, что это подзадача BackTracking, но от этого проще не становится, ибо там экспонента.
...
Рейтинг: 0 / 0
05.09.2017, 09:20
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515535
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
maytonЯ не думаю что это другая задача.
Конкретно эта задача может и не иметь решения.
А ранее описанные три - имеют.
...
Рейтинг: 0 / 0
05.09.2017, 10:31
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515548
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
maytonНу что-же - миллион у нас уже в кармане. Осталось только написать письмо
Британским ботанам.

Но смущает что мы читаем какой-то репост на mail.ru где плохо описаны
условия того что надо собственно сделать. Найти первую попавшуюся
расстановку? - Фракталы рулят. Найти все? - Ну это ждать пока солнце не погаснет.

Вобщем нужен оригинал этой новости.
https://www.google.ru/search?num=30&newwindow=1&safe=off&source=hp&q=queens problem algorithm
...
Рейтинг: 0 / 0
05.09.2017, 11:03
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515549
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
05.09.2017, 11:06
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515554
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
если скажем 100х100 клеток и у тебя 10000 ферзей, надо воткнуть максимальное кол-во ферзей максимально эффективно так, чтобы они друг-друга не ели
...
Рейтинг: 0 / 0
05.09.2017, 11:15
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515601
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Более 100 не получится.
...
Рейтинг: 0 / 0
05.09.2017, 12:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515649
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Интересно, что для 5, 7, 11, 13 существуют "фрактальные" решения (проверил все доски до 16х16).
...
Рейтинг: 0 / 0
05.09.2017, 13:28
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
tip78если скажем 100х100 клеток и у тебя 10000 ферзей, надо воткнуть максимальное кол-во ферзей максимально эффективно так, чтобы они друг-друга не ели
Ты слышал про принцип Дирихле?
...
Рейтинг: 0 / 0
05.09.2017, 13:47
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515671
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Aleksandr SharahovИнтересно, что для 5, 7, 11, 13 существуют "фрактальные" решения (проверил все доски до 16х16).
Простые числа однако.
...
Рейтинг: 0 / 0
05.09.2017, 13:49
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515697
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovИнтересно, что для 5, 7, 11, 13 существуют "фрактальные" решения (проверил все доски до 16х16).

Проверил 17, 19, 23 - тоже фрактальные.
...
Рейтинг: 0 / 0
05.09.2017, 14:16
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515940
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Aleksandr SharahovИнтересно, что для 5, 7, 11, 13 существуют "фрактальные" решения (проверил все доски до 16х16).в каком плане? есть их процент от общего количества решений?
...
Рейтинг: 0 / 0
05.09.2017, 18:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515956
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
maytontip78если скажем 100х100 клеток и у тебя 10000 ферзей, надо воткнуть максимальное кол-во ферзей максимально эффективно так, чтобы они друг-друга не ели
Ты слышал про принцип Дирихле?
нет, но эту задачу (2000x2000 клеток) мой скрипт решает за 10сек
выглядит как это поле, только 2000
Код: html
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
1       @···································································································
2       ··@·································································································
3       ····@·······························································································
4       ·@··································································································
5       ···@································································································
6       ········@···························································································
7       ··········@·························································································
8       ············@·······················································································
9       ··············@·····················································································
10      ·····@······························································································
11      ·······@····························································································
12      ··················@·················································································
13      ······@·····························································································
14      ·····················@··············································································
15      ·········@··························································································
16      ························@···········································································
17      ··························@·········································································
18      ····························@·······································································
19      ······························@·····································································
20      ···········@························································································
21      ·············@······················································································
22      ··································@·································································
23      ····································@·······························································
24      ······································@·····························································
25      ········································@···························································
26      ···············@····················································································
27      ·················@··················································································
28      ············································@·······················································
29      ················@···················································································
30      ···············································@····················································
31      ···················@················································································
32      ··················································@·················································
33      ····················································@···············································
34      ····················@···············································································
35      ·······················································@············································
36      ·························································@··········································
37      ···························································@········································
38      ······················@·············································································
39      ······························································@·····································
40      ·······················@············································································
41      ·································································@··································
42      ···························@········································································
43      ·························@··········································································
44      ·····································································@······························
45      ·······································································@····························
46      ·········································································@··························
47      ···········································································@························
48      ·············································································@······················
49      ·····························@······································································
50      ·······························@····································································
51      ·················································································@··················
52      ···················································································@················
53      ·····················································································@··············
54      ································@···································································
55      ························································································@···········
56      ·································@··································································
57      ···························································································@········
58      ·····································@······························································
59      ···································@································································
60      ·······························································································@····
61      ·································································································@··
62      ···································································································@
63      ····································································································
64      ·······································@····························································
65      ····································································································
66      ····································································································
67      ·········································@··························································
68      ····································································································
69      ··········································@·························································
70      ····································································································
71      ···········································@························································
72      ····································································································
73      ····································································································
74      ····································································································
75      ·············································@······················································
76      ····································································································
77      ··············································@·····················································
78      ·················································@··················································
79      ····································································································
80      ················································@···················································
81      ····································································································
82      ····································································································
83      ····································································································
84      ····································································································
85      ···················································@················································
86      ·····················································@··············································
87      ····································································································
88      ····································································································
89      ····································································································
90      ······················································@·············································
91      ························································@···········································
92      ····································································································
93      ····································································································
94      ····································································································
95      ··························································@·········································
96      ····································································································
97      ····································································································
98      ····································································································
99      ····························································@·······································
100     ····································································································
...
Рейтинг: 0 / 0
05.09.2017, 18:46
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515962
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kealon(Ruslan)Aleksandr SharahovИнтересно, что для 5, 7, 11, 13 существуют "фрактальные" решения (проверил все доски до 16х16).в каком плане? есть их процент от общего количества решений?

В том смысле, что "фрактальное" решение для доски NxN
позволяет построить решение для любой доски (M*N)x(M*N),
используя произвольное решение для доски MxM.
В частности для них можно построить решения (N^2)*(N^2).

Проценты:
5x5: 10 из 10
7x7: 28 из 40
11x11: 88 из 2680
13x13: 4524 из 73712

Проверил простые до 43 - для всех есть "фрактальные".

P.S. Если будете читать статью, то имейте в виду, что они
"фрактальные" решения называют "модулярными". Это одно и то же.
...
Рейтинг: 0 / 0
05.09.2017, 18:54
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515964
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
tip78эту задачу (2000x2000 клеток) мой скрипт решает за 10сек
выглядит как это поле, только 2000

Найти одно решение для любой доски можно вообще за 0 сек.
Строим фрактальное заведомо большей площади и откусываем, сколько надо.
Проблема не в этом.
...
Рейтинг: 0 / 0
05.09.2017, 19:00
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515969
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Aleksandr Sharahovtip78эту задачу (2000x2000 клеток) мой скрипт решает за 10сек
выглядит как это поле, только 2000

Найти одно решение для любой доски можно вообще за 0 сек.
Строим фрактальное заведомо большей площади и откусываем, сколько надо.
Проблема не в этом.

всмысле одно? как угодно можно начальные фигуры воткнуть, время не изменится
а за 0 сек 2000 клеток и супер-комп не исполнит, не надо ляля )
и вообще:
авторНе известно ни одно более эффективное решение проблемы, чем простой перебор. Так, для n=27 в 2016 году использовался масштабный параллельный поиск на FPGA.

В то же время, если компьютер начнёт перебор возможных положений ферзей на доске 1000×1000 клеток, то он загрузится этой задачей навечно. По мнению учёных, если некто найдёт действительно быстрый и эффективный способ решения, то сможет извлечь из этого гораздо бóльшую выгоду, чем один миллион долларов от Математического института Клэя. «Если вы напишете программу, которая может решить проблему действительно быстро, вы могли бы адаптировать её для решения многих важных задач, с которыми мы сталкиваемся ежедневно, — говорит профессор информатики Ян Гент (Ian Gent), один из авторов научной работы.
или я чего-то не понимаю, или учёные мельчают...
...
Рейтинг: 0 / 0
05.09.2017, 19:09
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39515994
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
tip78или я чего-то не понимаю, или учёные мельчают...под решением предполагается нахождение всех вариантов - 20770319
...
Рейтинг: 0 / 0
05.09.2017, 20:05
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 2 из 20
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]