Телефон со встроенной игрой судоку. Почему стоит скачать Судоку на андроид? Перемешиваем значения и считаем предположения

Начал я конечно же с алгоритма. Решая очередную и очень простую Sudoku, я пытался определить те шаги, которые должна предпринять машина, чтобы достичь результата. Дабы не лить много воды, сразу перечислю те ходы, которые позволяют решить простую Sudoku:

Можете попробовать: взять простую Sudoku (например, отсюда) и решить ее с помощью описанного алгоритма. Согласен, что для человека можно использовать более простой и логичный алгоритм, для машины же представленный алгоритм достаточно легко реализуем.

Хорошо, с этим разобрались. Это была простая Sudoku. Однако, зачастую, в процессе решения возникает такая ситуация, когда однозначное продолжение отсутствует.

Что делать, когда однозначное продолжение отсутствует?

Рассмотрим следующую, достаточно сложную Sudoku , в которой с самого начала отсутствуют единственные и уникальные значения в контейнерах возможных значений. Именно на этой Sudoku я отрабатывал те шаги алгоритма, которые описаны далее.

Это отступление я сделал для того, чтобы объяснить, как реализован механизм нахождения предполагаемого продолжения поиска. После нахождения ячейки с минимальным количеством возможных значений, формируем массив значений типа int, размерностью 9х9, в который записываем значения открытых ячеек. В этом массиве, ячейка, с которой мы только что "поработали", уже имеет определенное значение (первое значение из контейнера возможных значений). Этот массив является входным параметром для конструктора класса Core. На основании значений из этого массива создаются все, необходимые для нахождения решения, объекты перечисленных классов. Для всех неоткрытых ячеек заполняются контейнеры возможных значений, при этом, для той ячейки, для которой мы сделали предположение, значение уже установлено. У объекта класса Core есть метод getSolution(). Именно в этом методе реализован описанный механизм нахождения предполагаемого продолжения и создания, на основании этого предположения, нового объекта класса Core. Т.о. мы подошли к формулировке следующего пункта алгоритма, а именно:

5. Если, в результате очередной итерации цикла поиска единичных и уникальных значений, таковых не найдено, то:

• найти ячейку с минимальным количеством значений в контейнере возможных значений;
• на основании значений открытых ячеек, а также первого значения из контейнера возможных значений ячейки, найденной в предыдущем подпункте, сформировать массив "предположение" значений типа int, размерностью 9х9;
• на основании массива "предположения" создать новый объект класса Core, от имени которого вызвать метод getSolution() (фактически, запустить механизм рекурсивного поиска).

Т.е. еще раз. В методе getSolution() запускается цикл поиска единичных и уникальных значений (пункты 2, 3, 4). Если в результате итерации этого цикла не было найдено ни одного нового значения, то запускается пункт 5. В результате работы этого пункта запускается новый цикл, но уже от имени нового созданного объекта класса Core. Так происходит до тех пор, пока метод getSolution() не вернет решение в виде массива значений типа int, размерностью 9х9.

Вы конечно же спросите, а если предположение/я было неверно, что тогда? А тогда, метод getSolution() вернет null, что является признаком того, что при установке значения какой-то ячейки произошла ошибка. А именно, это значение уже установлено для одной из "родственных" ячеек. В этом случае, мы делаем шаг назад в механизме рекурсивного поиска и делаем следующее по-порядку предположение. И так, до тех пор, пока getSolution() не вернет решение.

Вот собственно и всё. Казалось бы всё, ан нет. Когда в написании программы я дошел до этого места, я испытал пару-тройку десятков различных Sudoku. Везде решение находилось в течение 10-20 милисекунд. И вот я наткнулся на ту Sudoku, которую мы рассматривали в качестве сложной. При первом запуске программа потратила на поиск решения 11,5 минут. После этого я сделал небольшой рефакторинг: в основном добавил условия в тех местах, которые в какой-то момент можно было бы не выполнять. На всё про всё, я потратил около одного дня и смог ускорить решение на 3 минуты, т.е. до 8,5 минут. Вроде неплохо, но недопустимо для окончательного решения.

В этом месте я сильно призадумался, был небольшой ступор. Т.е, что получается? Программа быстро решала порядка 95-98% раскладов Sudoku, а на оставшихся серьезно зависала. Сначала я хотел "подключить" многопоточность. Ведь действительно, если, например, есть только 2 ячейки, содержащих по 2 возможных значения, то мы имеем всего 4 возможных комбинации. Запускаем каждую из этих комбинаций в отдельном потоке. Поток, нашедший решение "сообщает" об этом. Выполнение других потоков прерывается, а поток, нашедший решение возвращает его. Казалось бы все логично и правильно. А если ячеек, содержащих минимальное количество возможных значений не 2, а 10 и значений в этих контейнерах не 2, а 3, то мы получаем уже порядка 50 тыс. возможных комбинаций и, соответсвенно, потоков, а это уже никуда не годится. У меня была такая Sudoku. Именно по этой причине я отказался от многопоточности в данном разрезе. (На самом деле многопоточность можно применить. Как? Расскажу в ). Однако размышление над решением, основанном на многопоточности натолкнуло меня на суть проблемы и возможное ее решение.

Перемешиваем значения и считаем предположения

Что же получается, когда решение находится в течение 8,5 минут? А получается следующее. Предполагаемое продолжение поиска делается на основании последовательного перебора (от первого до последнего) значений в контейнерах возможных значений неоткрытых ячеек. Т.е. мы делаем предположение, затем ещё одно, и ещё, и ещё ... А потом оказывается, что первое предположение ошибочно, но чтобы понять это приходится пройти цепочки предположений (сотни, тысячи, а то и десятки тысяч). Потом делается второе предположение, которое тоже может оказаться ошибочным и на всё это тратится то драгоценное время, которое выливается, в конечном итоге, в 8,5 минут. Поняв всё это, как бы Вы поступили?

Правильно! И я так же. Для пробы сил, попробуем перебирать значения в контейнерах возможных значений начиная не с первого, а с последнего. Я попробовал, и 8,5 минут превратились в 15 милисекунд. Суровая разница, не правда ли? Но, как Вы понимаете, это половинчатое решение, потому как, рано или поздно, мы наткнемся на такую Sudoku, значения в контейнерах которой лучше перебирать не с конца, а с начала. Что же делать? Уверен, Вы уже догадались.

Правильно! После формирования контейнера возможных значений неоткрытой ячейки, значения необходимо, случайным образом, перемешать. Теперь не важно, в каком направлении перебирать значения в контейнере: результат, в большинстве случаев, будет одинаков (или близок к этому). После того, как это было реализовано в программе, я перепробовал множество Sudoku и все были решены в течение 30 милисекунд.

Однако я понимал, что когда-нибудь значения будут перемешаны таким образом, что решение опять будет искаться очень долго. В доказательство этому предположению я стал запускать на выполнение только сложный вариант Sudoku, который мы и рассматриваем. Так вот, примерно 1 раз на 50 запусков программа опять уходила в ступор. Это было неприятно, но вероятность решения уже сильно возросла. Т.е. если взять за основу, что наша сложная Sudoku попадает в 3%, на которых программа сильно "задумывается", то после перемешивания значений в контейнерах, 3% превращаются в 0,06%. Т.е. программа быстро решает 99,94% всех Sudoku. Что бы Вы сделали (на данном этапе), чтобы довести эту цифру до 100%?

На самом деле решение на поверхности. Окончательная "примочка", которая позволяет решить любую по-сложности Sudoku, следующая. Как определить, что мы попали на расклад, который будет долго перебираться? По количеству сделанных предположений! Обычно, для сложных Sudoku, достаточно 10-15 предположений, в крайнем случае до 30-ти. Это выявлено на практике. Однако, для пустого расклада, когда не задано ни одного значения, количество предположений может достигнуть 50-ти. Что я сделал, чтобы контролировать это? Я добавил класс, инкапсулирующий в себе статическую переменную типа int, которая хранит количество сделанных в процессе поиска предположений (количество созданных новых объектов класса Core). Как только значение этого счетчика становится больше 100, поиск решения для текущего рассклада прекращается. Все созданные до этого момента объекты класса Core заканчивают свою работу и уничтожаются. Затем счетчик предположений сбрасывается в 0 и поиск начинается с начала, но уже со значениями в контейнере, которые перемешаны по-новому.

Собственно всё. Программа работает быстро. Я доволен. Нашел вот эту Sudoku , которая анонсируется, как самая сложная. Ну, не знаю, возможно, я в живую ее не решал. Я попробовал эту Sudoku на своей программе ни одну сотню раз. Да, действительно, при некоторых раскладах она задумывается на 60 милисекунд, но не более. В подавляющем же большинстве случаев, она находит решение менее, чем за 15 милисекунд.

Блок-схема алгоритма

Для завершения рассказа об алгоритме, приведу его блок-схему.

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

Почему стоит скачать Судоку на андроид?

«Судоку» оснащена красочными визуальными эффектами и плавными переходами, которые порадуют глаз любого игрока. Если вы не знаете, как дальше действовать, то современная система подсказок даст вам полезный совет как действовать дальше, либо укажет на ошибку, которую вы допустили ранее с отображением пояснительного текста почему должно быть именно так, а не иначе.

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

тремя вариантами игры в судоку (волнистый, режим Х и Color);

попробуйте все восемь доступных уровней сложности игры;

общая таблица лидеров игрового процесса с анализом достижений с помощью глобальной сети Интернет;

приложение постоянно обновляется разработчиками, при этом исправляются найденные ошибки и постоянно добавляются новые судоку;

всего уже в игре насчитывается свыше 15 тысяч головоломок.

В ходе игрового процесса вы сможете делать пометки, используя карандаш. Для того чтобы удалить неправильную цифру, достаточно просто кликнуть дважды на нее мышью. И так отменять ходы можно неограниченное количество раз.

Своими достижениями в игре можно делиться с друзьями через социальную сеть Facebook или в Twitter. Автоматическое сохранение игрового процесса позволит вам выключить приложение без страха потери данных. И при новом его открытии вы сможете продолжить игру на том же месте.

Скачать Судоку на Андроид можно напрямую с помощью магазина приложений Google Play или загрузив с нашего сайта.

Все знают о такой классической стандартной игре как Судоку и многие не однократно принимали в ней участие. Лучше всего, конечно же, скачать Судоку на андроид и попробовать сыграть со своего мобильного устройства, потому что в таком случае вы можете в любое время проходить соревнования по этому стилю и узнавать о популярности. Игра полностью оптимизирована для всех устройств на мобильных платформах, что снимает ограничения по ее использованию полностью. Вам необходимо обучиться игровому процессу в популярной игре, если раньше в нее играть не приходилось или сразу же приступить к прохождению этих головоломок.Когда сможете скачать Судоку на андроид начинайте изучать абсолютно новые методы игры и стратегии, чтобы пользоваться ими в совершенстве. Вам обязательно понравится классический геймплей и интерфейс, которым удобно управлять. Вся игровая система создана для облегченного понимания даже новичками в играх такого жанра. Когда вам попадется особенно сложная головоломка, можете попробовать использовать одну из подсказок и с ее помощью уже узнать пути выходы из этого. В правилах головоломки есть примеры в виде анимации и довольно понятные картинки, так что сложностей с обучением у игрока точно не появится.

Понятные правила в Судоку для новичка

Режимы игры

Правила игры Sudoku

Управление