sudoku@vtaiwan, Решаем головоломку sudoku Налаштування

[nikelong]

Проект "sudoku@vtaiwan"

----------------------------------------------------------------------------------------------------------

• Официальный сайт
• Официальная страница команды "Ukraine"
• Официальная статистика по команде "Ukraine"
• Статистика на Free-DC
• Статистика на Free-DC по команде "Ukraine"
• Статистика BoincStats по команде "Ukraine"
• Статус серверов проекта
• Процент завершения проекта!
• Примерное время завершения проекта!
  
• Статистика в Формула БОИНК!

----------------------------------------------------------------------------------------------------------

Что такое Supercomputer "Ukraine"

----------------------------------------------------------------------------------------------------------
ТОП-20 участников:

(Show/Hide)

1 rpisarev 7,163,183
2 and_km 736,208
3 Andrey Fenchenko 632,520
4 tiss 554,432
5 Alexis Kravtchenko 551,486
6 SmaiL 369,526
7 re_SET 314,043
8 LSA 264,036
9 rrappee 212,125
10 Death[Kiev] 204,978
11 tyoma 201,162
12 r0b1n 178,145
13 smile 159,288
14 Sergyg 140,112
15 w.olk.a 113,705
16 Vvolodymyr 85,102
17 Igor 79,584
18 Lamer@fools.ua 78,661
19 alblackcat 72,882
20 treestar 67,317
на 18.08.2013

----------------------------------------------------------------------------------------------------------
Дата основания команды - 20.09.2010 Капитан - Irish Republican
----------------------------------------------------------------------------------------------------------
Для присоединения к команде Украины:
1. Загрузите BOINC менеджер (Если его у Вас еще нет!)
2. Перейдите в "расширенный вид"
3. Выберите сервис ---> добавить проект
4. Введите адрес проекта http://sudoku.nctu.edu.tw/
5. Введите свои регистрационные данные.
6. Найдите нашу команду. Она называется Ukraine и адрес ее статистики вы могли видеть выше.
7. Если есть доступные для загрузки задания Вы их получите и начнете расчеты.
----------------------------------------------------------------------------------------------------------
Новичкам: статья со скриншотами, как поставить и настроить BOINC-менеджер
----------------------------------------------------------------------------------------------------------
Полезная информация:
Для идентификации пользователя в BOINC могут служить 2 вещи:
1) пара e-mail/пароль
2) межпроектный идентификационный ID (Cross-project ID) - 32значное шестнадцатиричное число.

Если Вы пожелаете подключится ещё и к другому BOINC-проекту, то помните: чтобы не плодить новых аккаунтов при подключении к новому проекту или команде, нужно обязательно везде регистрироваться с одним и тем же Именем и EMAIL. если при регистрации в проекте указать другой e-mail , BOINC создаст новый аккаунт с тем же именем! В этом случае рекомендуется зайти во все ваши аккаунты и во все проекты и где надо поменять емейл на нужный. Через некоторое время ваши аккаунты сольются в один с одним cross-project-id.
----------------------------------------------------------------------------------------------------------

О проекте:
"Судоку - очень популярная головоломка, у которой всегда существует решение, и это решение должно быть уникальным. В обыкновенных судоку приблизительно 25-30 исходных чисел. Обычно судоку тем сложнее, чем меньше исходных чисел. Но это не универсальное правило: есть сложные судоку со многими исходными числами, и лёгкие только с несколькими исходными числами.
Интересный вопрос - насколько мало исходных чисел достаточно для того, чтобы судоку имело уникальное решение? Тривиальная нижняя граница - 8: предположим, что даны только 7 чисел. Тогда в любом решении вы можете поменять все вхождения двух не исходных цифр, и таким образом, есть всегда как минимум два различных решения. Поразительно, но до сих пор математическими рассуждениями не было найдено лучшей нижней границы. Все известные минимальные судокус уникальным решением имеют 17 исходных чисел. Таким образом, текущий диапазон для наименьшего числа ключей (исходных чисел), который головоломка судоку (с одним уникальным решением) может иметь - от 8 до 17.
Цель проекта состоит в том, чтобы закрыть этот промежуток. С этой целью мы начинаем с 92248 наборов с 8 первичными исходными числами (цифры 1-8, представляющие все комбинации со ссылкой на симметрию, перенумерацию и т.д.), расширяем их, добавляя больше исходных чисел, и проверяем на уникальность.
В течение первой фазы оценки нашей программы мы были в состоянии показать, что должно быть, по крайней мере, 11 исходных чисел. Таким образом, текущий диапазон - 11..17. Используя распределённые вычисления, наш метод будет шаг за шагом увеличивать нижнюю границу до тех пор, пока или кто-то найдёт новый минимальный пример, или мы сможем показать, что таких примеров нет для числа исходных чисел до 16 включительно. "

Ссылки по теме:
http://www.bc-team.org/viewtopic.php?t=599

График ППД команды "Ukraine"

(Show/Hide)

TROUBLESHOOTING
Для работы приложения может потребоваться пакет Microsoft Visual C++ 2008 Redistributable Package (x86)
Даже в том случае, если у вас х64 ОС и установлен соответствующий пакет Microsoft Visual C++ х64!!!

Це повідомлення відредагував rpisarev: Aug 18 2013, 13:33

[Waterfall]

http://idle.slashdot.org/story/12/01/08/18...+%28Slashdot%29

Не знаю, в тему чи ні, але публікується повідомлення, що математики вирішили задачу про підказки в судоку... Це про теж саме?
Повністю http://lenta.ru/news/2012/01/09/sudoku/
Препринт Cornell University Library http://arxiv.org/abs/1201.0749

[rpisarev]

Угу, та же новость. Вычисления были на суперкомпьютере. И они оказались быстрее тайваньского boinc-проекта. Хотя обычно гриды опережали суперкомпы...

[rpisarev]

В любом случае, чтобы подтвердить результат ирландца о том, что нет уникальных решений судоку с 16-ю ключами (а значит 17 ключей - наименьшее), надо независимо просчитать. Чем данный проект и занимается.

[Death]

Вычисления были на суперкомпьютере. И они оказались быстрее тайваньского boinc-проекта.

да ну?
почитайте пдфку. очень интересно

6.3 The Actual Computation
The entire computation took about 7.1 million core hours on the Stokes machine. Stokes is an SGI Altix ICE 8200EX cluster with 320 compute nodes. Each node has two Intel (Westmere) Xeon E5650 hex-core processors and 24GB of RAM. We divided the computation up into several hundred jobs. We started running jobs in January 2011, and we finished in December 2011.

тупо год считали.

причем они знали про тайвань.

2.2 PreviousWork by Others
• In Japan, sudoku was introduced by the publisher Nikoli in the 1980s. Japanese puzzle creators have made puzzles with 17 clues, and have surely wondered whether 16 clues are possible. Nikoli have a rule that none of their puzzles will have more than 32 clues.
• Over the past several years, people have collected almost 50,000 solution grids containing one or more 17-clue puzzles. These can be found on Gordon Royle’s website [1]. Most of them were found by Royle, who compiled this list of 17-clue puzzles while searching for a 16-clue puzzle. There is constant discussion about the minimum number of clues problem (including a number of false proofs) in the relevant online discussion boards [4]. This is where we became aware of a completed grid found by Royle which contains twenty-nine different 17-clue puzzles (see Section 5.3.1). This was considered a likely grid to contain a 16-clue puzzle, and initially we started work on checker to solve this particular problem. Referring to the minimum number of clues problem, Royle states (January 3rd, 2011) on his 6 blog: ”Doing the numbers suggests that something clever will be needed to solve this; even projected computer advances won’t be enough to resolve it in my lifetime ... ”
• The sudoku minimum number of clues problem has been mentioned in several journal publications [6, 7, 8, 9]. The last reference is an article entitled The Science behind Sudoku and written by the French Computer Science Professor J.-P. Delahaye, which appeared in the June 2006 issue of the Scientific American. This article quotes one of the authors (Gary McGuire) in conjunction with the sudoku minimum number of clues problem.
• In 2008 an eighteen-year-old girl submitted a proof of the nonexistence of a 16-clue sudoku puzzle as her entry to the German national science competition for highschool students (”Jugend forscht”), and she also published two papers (in German) in the journal ”JungeWissenschaft”. However, Sascha Kurz, a mathematician at the University of Bayreuth later had a project proposal for a Master’s thesis, that indicates he had found mistakes in the proof. That Master’s project was to summarize the state of the art of the minimum number of clues problem, and then to solve part of the problem. The proposal specifically mentions the above project, and cites the two respective papers, saying: ”Unfortunately, the main arguments in the proof are not correct, so that the problem is still open.”
• A paper in the Notices of the American Mathematical Society [8] by Herzberg and Murty states on the first page: ”For anyone trying to solve a Sudoku puzzle, several questions arise naturally. For a given puzzle, does a solution exist? If the solution exists, is it unique? [...] What is the minimum number of entries that can be specified in a single puzzle in order to ensure a unique solution?”
• A quick Internet search reveals that the sudoku minimum number of clues problem has been subject of, or at least mentioned in, quite a few talks in seminars/colloquia in mathematics and computer science department around the world. For example, a researcher in mathematics from the University of St. Andrews, Max NeunhЁoffer, gave a talk Is there a Sudoku puzzle with 16 clues? at the University of Aberdeen, outlining the very strategy we used for solving the minimum number of clues problem [10].
• Mladen Dobrichev, who appears to be a very competent programmer, has written a tool named GridChecker [17]. This programme basically does the same thing as our open-source version of checker, although it is considerably faster. In fact the 7 readme file for GridChecker mentions our original checker and even provides the URL of its homepage, saying: ”The idea [of GridChecker] is based on the similar tool named checker (http://www.math.ie/checker.html).”
• In 2009, a team at the University of Graz in Austria verified, also using a computer search, that no proper sudoku puzzle can exist with fewer than 12 clues, and apparently they had also most of the computations finished that showed that in fact at least 13 clues are necessary. Their stated aim was build up to proving that no 16-clue sudoku exists, although that project appears not to be active anymore.
• A group of computer scientists at the National Chiao Tung University in Taiwan led by Professor I-Chen Wu in November 2010 published the paper Solving the Minimum Sudoku Problem [18]. In this article, which refers to one of the authors (Gary McGuire) and checker, they describe some of the techniques they used to speed up our original version of checker by a factor of 129. ProfessorWu also gave a talk about this at the 2010 International Conference on Technologies and Applications of Artificial Intelligence. Around this time the Taiwanese research group started a distributed search over the Internet using BOINC, to search all inequivalent sudoku grids for a 16-clue puzzle. According to the project’s website, as of December 31st, 2011 they have checked 1,453,000,000 grids.
• Two research students at the University of Glamorgan in Wales, Sian Jones and Jemma Williams, are studying aspects of sudoku, see [5].

[Rilian]

Спасібо, інтересно

[rpisarev]

Читал. Потому и сказал. Ведь все суперкомпьютеры сейчас по сути кластеры. И уж они точно не были распределёнными )

[rpisarev]

25-е место. Вскоре 24 :-)

[Death]

а время окончания так и не приделали.

там 10 минут работы. вот ленивые студни.

[rpisarev]

Ну может это неверная оценка и потом пойдут тяжелые wu?

[Death]

никто не говорит точно сказать до минуты.
по формуле шо я писал - примерное время.

на дистрибутед.нет для огр-27 есть примерное время окончания по разному среднему времени - по дню, неделе и месяцу.

ву там тоже нормально разнятся.

зато хотябы примерно понятно.

[egorio]

Значит это им не нужно

[Death]

просто ленивые студенты.

да и ещё ирландцы подкололи - уже пощитали все 16-ки...

[rpisarev]

Ну всё равно надо результат проверить. Зато, если верно, то не надо будет 15-ти искать

[x3mEn]

Останнім часом помітив, що інколи 1 завдання відгризає більше 1 ядра. Фактично з'їдаючи весь вільний ЦПУ час.
Та й так, що не залишає ЦПУ для РОЕМ. Вимушений поки пригальмувати цей проект.
Мені такий розклад не подобається. З якого це часу клієнт став мультиядерним?

P.S.: В мене, правда, зараз <ncpus>1</ncpus>. І Boinc 7.07.
Щось я не пам'ятаю такого, щоб при дозволеному 1 ядрі боїнк раніше дозволяв використовувати більше 1 ядра...
Можливо це приколи 7.07.
Просто sudoku вижерає всі ЦПУ ресурси під 0. І таке враження, що далеко не з Idle приоритетом.
Тому що все починає гальмувати неймовірно.
Не тільки РОЕМ. Просто браузер і той страждає.

P.P.S.: Я просто включив NRG замість sudoku, так він так само з'їв більше 1 ядра. Але залишає системі достатньо ЦПУ і його присутність не відчутна.

[rpisarev]

Скорее всего из-за тестовой версии клиента. Пользуюсь стабильными 6.* - с приоритетом +19 выполняется. Даже слабый ноут не тормозит при расчётах