Неархитектурная задачка

[vlad]

На будущее, чтоб не затерялось в исходниках, удачный алгоритм одним предложением выражается так:

В дереве поиска следующий шаг рекурсии делать в ветви с наименьшим количеством подветвей.

Да, такой подход хорошо работает (другие эвристики мне дали ускорение только в ~2 раза).
Аттачнутый вариант работает за ~0.09с. Ввод/вывод отдельно лень мерять.

[vlad]

На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?

[valexey]

На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?

Ну, я наверно на досуге свое решение еще попилю, но это не должно мешать публикации исходников :-) Я достаточно ленив чтобы не смотреть в ваши решения до тех пор пока не допилю свое :-)

[ilovb]

На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?

Погодите, погодите. Тут 1С вариант допиливается. 

p.s. Я нашел косяк

[valexey]

На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?

Погодите, погодите. Тут 1С вариант допиливается. 

p.s. Я нашел косяк

Вот он - истинный хоррор! И путь живые позавидуют мертвым... :-)

[ilovb]

В общем я выбрал неудачную стратегию. Закодил первое, что пришло в голову и не угадал Время решения растет экспоненциально сложности судоку.
Хотя иногда попадаются и быстро решаемые сложные. На средней сложности откатов почти нет, а вот  на вариантах vlad'a уходит в глубокий перебор. Время с большой точностью не мерил, но средние решаются меньше секунды (так как 1С интерпретатор, то более точно мерить смысла нет)

Почему вариант vlad'a не решается я понял, но с данной стратегией победить не получилось. Поэтому прикладываю пока этот первый вариант, и подумаю как сделать иначе.

[valexey]

В общем я выбрал неудачную стратегию. Закодил первое, что пришло в голову и не угадал Время решения растет экспоненциально сложности судоку.
Хотя иногда попадаются и быстро решаемые сложные. На средней сложности откатов почти нет, а вот  на вариантах vlad'a уходит в глубокий перебор. Время с большой точностью не мерил, но средние решаются меньше секунды (так как 1С интерпретатор, то более точно мерить смысла нет)

Почему вариант vlad'a не решается я понял, но с данной стратегией победить не получилось. Поэтому прикладываю пока этот первый вариант, и подумаю как сделать иначе.

Эмм.. А можно этого бинарного шайтана в текстовый вид перевести и запостить тут? А то под линуксом и макосью сложновато с 1С.

[ilovb]

Вот исходник

[ilovb]

прикладываю пока этот первый вариант

Да кстати, если кто скачал обработку, там на форме в таблице по умолчанию вариант vlad'a 
Не спешите давить на кнопку. Решения придется долго ждать.
Прервать можно сочетанием Ctrl+Break

[ilovb]

Вот исходник

Вот ведь.. Только запостил и тут же нашел ошибку в коде.
Прилагаю поправленное

[ilovb]

Генератор судоку для Excel
http://www.podzamkom.ru/games/gen_sudoku/tabl_sudoku.htm

[vlad]

Вот исходник

Круто! Я даже и не думал, что у нас будут столь экзотичные решения как 1С

[ilovb]

Если сегодня смогу выделить время, то закодю вторую версию. Моя ошибка была в том, что я для позиций ищу числа, а нужно наоборот. Т.е. мой алгоритм нужно наизнанку вывернуть.
Кстати я замерил время на решение варианта из первого сообщения - 7,5 минут (5 минут если удалить в байткоде указатели номеров строк исходного кода)

[Губанов Сергей Юрьевич]

Кстати, при выполнении вычислений длящихся менее 0.1 секунды разогнанный 3770K с настройками энергосбережения не считает нужным переключиться в турбо буст (на 4200 МГц), делает их на частоте холостого хода 1600 МГц. В результате показатели оказываются хуже, чем уже опубликованные. Отключать энергосбережение было в лом

[ilovb]

Решил прикинуть масштаб скорости 1С по отношению к КП 

код КП:

Код: [Выделить]

MODULE MyTime;
IMPORT Log;

PROCEDURE Do*;
VAR
a: ARRAY 100000 OF LONGINT;
i, j: LONGINT;
BEGIN
FOR j := 1 TO 100 DO
FOR i := 0 TO LEN(a) - 1 DO
a[i] := 123;
END;
END;
END Do;

BEGIN

END MyTime.Do
125 msec

код 1С:

Код: [Выделить]

Перем MSScriptControl;

Процедура КнопкаВыполнитьНажатие(Кнопка)

Массив = Новый Массив(100000);

Момент = ПолучитьВремяВМиллисекундах();

Для Счетчик = 1 По 100 Цикл
Для Индекс = 0 По Массив.Количество() - 1 Цикл
Массив[Индекс] = 123;
КонецЦикла;
КонецЦикла;

Сообщить(ПолучитьВремяВМиллисекундах() - Момент);

КонецПроцедуры

Функция ПолучитьВремяВМиллисекундах()
  Возврат MSScriptControl.Eval("new Date().getTime()");
КонецФункции

MSScriptControl = Новый COMОбъект("MSScriptControl.ScriptControl");
MSScriptControl.Language = "javascript";

71 469 msec