Задачи на программирование
 

Придумалось несколько задач, скорее всего на программирование.
Найдите минимальное число N, при котором в числе 2^N...
1. будет встречаться последовательность 0123456789.
2. будет встречаться последовательность 9876543210.
3. будет встречаться последовательность 0123456789 не менее 10 раз.
4. будут встречаться последовательности 000, 111, .... 999 (в одном числе все последовательности сразу).
5. количество вхождений каждой цифры (0,1,2...9) не менее 100.

1. 244178
2. 283789
4. 2389
5. 3474

Первые две задачи считались по минуте, четвёртая и пятая — доли секунды. Решение третьей задачи не меньше 500000, а алгоритм умнее брутфорса, который, похоже, в разумное время не закончится, в голову не приходит.

Код, думаю, приводить бессмысленно: умножить на два число в памяти в десятичном представлении — невелика задача.

2^283789 - это 85 тыс. десятичных знаков, так?

Да, log_10(2) * N ≈ 0,3 * 283789 ≈ 85000.

После небольшой оптимизации и распараллеливания (в результате которых первые две задачи стали выполняться за 15 и 19 секунд соответственно), удалось за 40 с лишним минут проверить все N <= 3321927, т.е. числа до 1 млн. десятичных знаков. Среди них не нашлось ни одного, в котором последовательность 0..9 встречалась хотя бы два раза. Так что если к этой задаче нет какого-нибудь очень хитрого теоретико-числового подхода, то Герман нашёл, чем занять все земные компьютеры на ближайшую геологическую эпоху.

Тогда ещё задачка:
Есть натуральное число N. Если в двоичной записи числа N цифры прочесть задом-наперёд, то получится десятичная запись числа M. Каково минимальное значение N, при котором M больше N в полтора раза?
1. Если разрешается использовать нули в начале двоичной записи числа M (например N=110100, M=001011).
2. Если запрещается использовать нули в начале числа M (то есть двоичная запись числа N должна оканчиваться единицей).

Не знал куда лучше разместить, думаю здесь тоже пойдет.

Коллега изучает Visual basıc. В качестве задачи, поставил решение судоку. Т.е. Хочет написать прогу, которая будет решать судоку любой сложности. Проблема в том, что навыков программирования нет, поэтому подходит к решению проблемы методом тыка. Что ни есть гуд. Умные люди посоветовали ему для начала составить алгоритм решения и набросать блок схему. С чем, в принципе, он согласился. Но опять проблема - не получается это у него. Усилиями коллектива мы тоже не смогли составить правильный алгоритм решения задачи. Какие будут мнения?

у парня с английским если всё ок, то книга ему в помощь
http://nnm.ru/blogs/makumazan/programming_sudoku/
рассматривается процесс написания игры

а) Решать тупым полным перебором
б) Найти в нете готовые решения и разобраться
в) Выбрать задачу попроще, для которой он сможет составить алгоритм.

ЗЫ Басик - зло в чистом виде

DarkUser прав:
Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.

Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки

У каждого свои тараканы.

На второй строчке будет уже намного меньше. Плюс уже стоящие цифры, отсеют большое количество вариантов.

В том-то и дело, что не получается у него этот полный перебор организовать.

Это все так. Но не 729 же...

К автору задачи.
Для начала надо попробовать решить задачу без полного перебора. Пройдемся по всем 81 клеточкам (естественно, незанятым). Для каждой быстренько заводим массив из 9 целых чисел, заполняем его единичками. Потом проходим по всем остальным клеткам квадрата 3х3, в котором находится рассматриваемая клетка, если она не пустая и равна n, то заменяем n-й элемент массива ноликом. Потом то же самое делаем с той строкой, в которой находится текущая клетка, и со столбцом, соответственно. После этой операции суммируем массив, если его сумма равна единице, то вариантов заполнения этой клетки ровно 1, ищем единственный не равный нулю элемент массива и проставляем значение в клетку. Если сумма массива оказалась больше единицы, пропускаем эту клетку. И так проходим по всем 81 клеткам много раз до тех пор, пока алгоритм работает.
После того, как "очевидных" клеток не осталось, придется включать алгоритмы перебора, я в них никогда не был силен.

Криво посчитал.

Кстати из Википедии Там нет ссылки на доказательство и, я думаю, доказательство столь интересного факта само по себе интересно.

Как ни странно, но этот алгоритм при нормальном количестве данных чисел (обычно около 23 на разрешимую таблицу) с вероятностью близкой к 1 ни разу не даст ни одной "очевидной" циферки. Кто-нибудь попробует?

К утру попробую что нибудь придумать. Идея уже есть.

Представим судоку как двумерный массив a[0..2,0..2](большой 3х3 квадрат). Каждый элемент массива содержит двумерный массив b[0..2,0..2](маленький 3х3 квадрат). У нас получается 4мерный массив. a[r,t,x,y]
r: Row number. Номер строки на большом квадрате (0..2)
t: Column number. Номер колонки на большом массиве (0..2)
x: Х координата. Номер строки на маленьком квадрате (0..2)
y: У кородината. Номер колонки на маленьком массиве (0..2).
Для каждой пустой клетки находим доступные цифры которые не встречаются на колонке, на строке и на маленьком квадрате на которым находятся текущая клетка. (в нашем примере проверяемые клетки на строке/колонке/квадрате при наведение курсора выделяется розовым цветом, не проверяемые желтым)
У меня получился вот это: http://examplecodes.narod2.ru/html/sudoku/

Простая задачка:
Есть десятичное число n, его записали в двоичном виде. Есть число m такое, что его двоичная запись зеркальна двоичной записи числа n.
Например: n=13 (1101) m=11 (1011).
Найти минимальное n, при котором m будет больше n в 1.5 раза.
1. при условии, что оба числа необязательно должны начинаться с единицы. Например n=10 (1010) m=5 (0101).
2. при условии, что оба числа обязательно должны начинаться с единицы.

См. что она выдала на заведомо решаемую задачку.
https://img.uforum.uz/images/wvrleoy5431417.png
Ищите ошибку. Обычно решение не начинается сразу с заполнения 1-й клетки.

Да. Это слабое место алгоритма. Для каждой клетки находить ряд доступных цифр и выбирает первый из них. Если заметили когда кликните на клетку она показывает только доступные цифры. У кого нибудь есть идея?

Насколько мне известно, судоку в общем случае без перебора с откатом не решается. Если при распространении ограничений обнаружилась тупиковая конфигурация, надо возвращаться.

У JH была не плохая идея, точнее не полный алгоритм, только сначала обычно проверяют совместность одинаковых цифр, а несовместность цифры в данной ячейке.
Факт, что не все Судоку решаются без перебора, однако обычно таких переборов в глубину бывает не более одного или двух шагов в глубину даже для самых сложных Судоку (например то, на которой я ваше решение тестировал). Т.е. последовательный анализ должен давать значительную часть разрешимых и однозначных Судоку.

Могу предложить рекурсивный метод решения в лоб:
Создаётся трёхмерный массив - координаты клетки и возможные значения для этой клетки. Сначала забиваются исходные данные, затем анализируется каждая клетка и в массив заносятся все возможные значения. Если количество возможных значений равно одному, данная клетка помечается как решённая и алгоритм начинает выполняться заново.
Таким образом можно решить простые судоку.

Герман. Именно такая постановка не дает ни одного решения для большинства стандартных Судоку, когда известны только 23 числа, т.е. менее 30% на строку/столбец или менее 50% известных цифр на ячейку. Скорее всего алгоритм такой ничего не даст.

Если Вы решали Судоку, то первые циферки находятся исходя из того, что в каждой строке, столбце и соотв. клетке 3×3 ровно по одной цифре из набора 1..9.

Т.е. сначала, например, рассматриваются все единицы. Вычеркиваются все стобцы, строки, квадраты 3 × 3 в которых есть единицы, если вдруг в некотором квадрате, строке или столбце окажется, что вычернуты все неразрешенные клетки кроме одной, то в ней гарантированно - единица.

Например в примере сверху в двух последних строках есть пятерки. Вычеркиваем эти строки и замечаем, что в 7-й строке в третьей позиции должна быть пятерка.

Давно я не брал в руки шашки!
Спустя 15 лет обсуждение судоку сподвигло меня написать программу :) На старом добром любимом QBasic (только его я и помнил, оказывается, так что извините)
Программа решает уровни сложности Easy, Medium, Hard с сайта http://websudoku.com
С уровнем "Evil" (там на каком-то этапе нужно делать перебор вариантов) не справляется.

Кстати, Надир, в вашем примере через несколько ходов тоже не остается очевидных вариантов, надо перебирать.

Я выбирал заведомо сложный вариант.