Кубик Рубика имеет сложную конструкцию, для игры в шахматы нужны фигурки и доска, для многочисленных карточных игр необходимы колоды карт разного объёма, для древнейшей игры в кости требуются аккуратно изготовленные кубики. И только для игры в судоку не нужно ничего, кроме листа бумаги и карандаша.
В этой статье рассмотрим "Алгоритм X" Кнута и его применение для решения судоку. Прелесть алгоритма в том, что судоку при этом решается быстро без программирования каких-то продвинутых техник решения.
Многие из вас наверняка знакомы с такой головоломкой, как судоку. Возможно, даже реализовывали программу для автоматического решения. На хабре тема судоку обсуждалась уже множество раз, и, как показывает практика, практически любой способ автоматического нахождения ответа в итоге сводится к направленному перебору. И это вполне естественно, ведь даже ручные решения придерживаются тех же принципов. Но что, если поступить иначе?
В данной статье я рассмотрю один очень занятный метод, предложенный в 2012 году, основанный на строго математическом подходе. Программная реализация прилагается.
Привет! Это вторая часть перевода статьи про подсчет различных судоку.
В этой части мы погрузимся в теорию групп, начиная с самых основ, но затрагивая только то, что нам пригодится для ответа на вопрос: а сколько же есть действительно различных судоку — без всяких повторов в виде поворотов, отражений и т.п. Те, кто довольно хорошо знаком с теорией групп — вероятно, найдут тут мало что интересного. Для остальных же почитать очень даже полезно. На всякий случай: я себя специалистом по теории групп не считаю, при переводе статьи я сам по сути изучал ее почти с нуля. То есть, вполне могут быть косяки — пишите мне о них в личку. С другой стороны — я для большинства определений лазил в википедию, а все численные результаты подтвердил собственноручно написанной программой. Так что, по идее, количество косяков должно стремиться к нулю. Но мало ли.
Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.
Читать полностью »
Привет!
Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).
К сожалению, оригинал данной статьи написан для дебилов очень широкого круга читателей, в том плане, что тема рассматривается не очень глубоко, но довольно подробно. При этом поясняется только общий подход к решению задачи, без технических деталей, и, фактически, обрывается на самом интересном месте формулировкой «ну а дальше они посчитали на компьютере». В итоге я немного дополнил изложение своими комментариями: они либо отмечены курсивом, либо спрятаны под спойлеры. В них раскрываются некоторые технические моменты более подробно. Возможно, пост вместе с этими комментариями суммарно тянет на полноценную статью, нежели чем на просто перевод, но я решил оставить все как есть (на самом деле, я не нашел кнопки перевода перевода обратно в обычную статью, а создавать новую публикацию только ради этого было лень).
Читать полностью »
Среди национальных лидеров различных стран не так много тех, кто хорошо разбирается в современных технологиях. И еще меньше тех, кто может самостоятельно написать какую-либо программу. Похоже, Сингапуру очень повезло со своим премьер-министром — кроме решения важных государственных проблем, Ли Сяньлун может писать программы на C++. На днях Сяньлун выложил в общий доступ свою решалку Судоку, плюс исходный код программы.
Об этой программе премьер-министр упомянул в своем обращении к представителям ИТ-индустрии от 20 апреля. Стоит отметить, что саму программу он написал несколько лет назад, теперь на это у премьер-министра просто нет времени.
Читать полностью »
В предыдущей статье я рассказал как разработать судоку для windows 8.1, в этой расскажу как портировать приложение на Windows Phone 8 и локализовать его на несколько языков.
Доброго времени суток!
Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».
Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.
Большинство из нас, читателей, знает, что такое судоку. Не буду рассказывать про правила, а сразу перейду к методикам.
Для решения головоломки, не важно сложной или простой, изначально ищутся ячейки очевидные для заполнения.
Читать полностью »
