Добро пожаловать на сайт, посвященный популярной головоломке судоку.

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

Теперь вы можете решать головоломки не только на компьютере, но и на смартфонах и планшетах с Android, iOS и Windows Phone. Уникальный интерфейс запоминает все ваши “ходы” при решении, подстраивается под любой размер экрана и позволяет полностью сосредоточится на процессе игры.

ЕЖЕДНЕВНЫЕ ГОЛОВОЛОМКИ

Каждый день мы публикуем 4 классических судоку…

другие головоломки и разновидности судоку…

японскую мозаику, филиппинский кроссворд и японский кроссворд

“Черепашка”

СУДОКУ

Помимо классического варианта размером 9 на 9 клеток имеются в наличии и другие – от 4 на 4 до 25 на 25 клеток. Также есть варианты с дополнительными условиями в задании (или вообще не имеющие стандартного задания) и с блоками, форма которых отличается от квадратной.

Основное условие – все эти головоломки имеют блоки соответствующего размера.

  СУДОКУ

СУДОКУ Х

БОЛЬШЕ-МЕНЬШЕ

СУДОКУ-ТОЧКИ

ЧЕТ-НЕЧЕТ

СУДОКУ-ПАЗЛ

СУДОКУ-РАМА

ВОРДОКУ

ВИНДОКУ

СУДОКУ-АСТЕРИСК

СУДОКУ-СНЕЖИНКА

СУДОКУ-МОЗАИКА

СУДОКУ-АРГАЙЛ

ГОЛОВОЛОМКИ НА ОСНОВЕ СУДОКУ

Основное отличие от судоку и его разновидностей – отсутствие дополнительных блоков.

2D СУДОКУ

“СОСЕДИ”

“НЕБОСКРЕБЫ”

АЛФАВИТ

ФУТОШИКИ

КВАДРАТ ЭЙЛЕРА

КИРПИЧИ

ЧИСЛОБОЛ

МУЛЬТИСУДОКУ

Эти головоломки представляют собой комбинацию из нескольких судоку (имеющих общие блоки), которые невозможно решить по отдельности.

ДАБЛДОКУ

ТУДОКУ

СУДОКУ-СЭНСЭЙ

ТРИДОКУ

КРЫЛО-3

КРЫЛО-5

СУДОКУ-СОХЕЙ

СУДОКУ-БАБОЧКА

ЦВЕТОК-5

СУДОКУ-МЕЛЬНИЦА

САМУРАЙ СУДОКУ

СУДОКУ-МИКАДО

СУДОКУ-НИППОН

СУПЕР-САМУРАЙ

СУДОКУ-СЕГУН

ДРУГИЕ ГОЛОВОЛОМКИ

АРАФ

БУХТА

ВОЗДУХОВОД

ВОЛНОВОЙ ЭФФЕКТ

ВЫСТРЕЛ

ГОБЛИН

ДВОИЧНЫЙ КОД

ДОМИНИОН

ДОМИНО

ЗМЕЯ

ИНЬ-ЯН

КАКУРАСУ

КАКУРО

КВАДРАТЫ

КОМНАТЫ

КОРАЛЬ

КРИВАЯ ДОРОЖКА

КУРОМАСУ

КУРОТТО

ЛАГЕРЬ

ЛИНЕЙЩИК

МАЯКИ

МОСТЫ

МОЧИКОРО

НОРИ-НОРИ

НУРИКАБЕ

НУРИМИСАКИ

ОБЛАКА

ОЖЕРЕЛЬЕ

ПАСТБИЩЕ

ПЕТЛЯ

ПРОМЕЖУТКИ

САПЕР

СЛАЛОМ

СТЕНЫ

СТРИТ

СУКОРО

ТАТАМИ

ТЕРРИТОРИЯ

ТРОСТЬ

ФИЛИППИНСКИЕ КРОССВОРДЫ

ФИЛЛОМИНО

ФОБИДОШИ

ФОНАРИ

ХИДОКУ

ХИТОРИ

ЧИСЛОБУС

ЯПОНСКАЯ МОЗАИКА

ЯПОНСКИЕ КВАДРАТЫ

ЯПОНСКИЕ КРОССВОРДЫ

Как решать судоку: способы, методы и стратегия

Как решать судоку: способы, методы и стратегия

Поле судоку представляет собой таблицу 9х9 клеток. В каждую клетку заносится цифра от 1 до 9. Цель игры: расположить цифры таким образом, чтобы в каждой строке, в каждом столбце и в каждом блоке 3х3 не было повторений. Другими словами, в каждом столбце, строке и блоке должны быть все цифры от 1 до 9.

Для решения задачи в пустые клетки можно записывать кандидатов. Например, рассмотрим клетку 2-го столбца 4-ой строки: в столбце, в котором она находится, уже имеются цифры 7 и 8, в строке — цифры 1, 6, 9 и 4, в блоке — 1, 2, 8 и 9. Следовательно, из кандидатов в данной ячейке вычеркиваем 1, 2, 4, 6, 7, 8, 9, и у нас остается только два возможных кандидата – 3 и 5.

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

С кандидатами решать интереснее и можно применять различные логические методы. Далее мы рассмотрим некоторые из них.

Одиночки

Метод заключается в отыскании в таблице одиночек, т.е. ячеек, в которых возможна только одна цифра и никакая другая. Записываем эту цифру в данную ячейку и исключаем ее из других клеток этой строки, столбца и блока. Например: в данной таблице имеются три «одиночки» (они выделены желтым цветом).

Скрытые одиночки

Если в ячейке стоит несколько кандидатов, но один из них не встречается больше ни в одной другой ячейке данной строки (столбца или блока), то такой кандидат называется «скрытой одиночкой». В следующем примере кандидат «4» в зеленом блоке найден только в центральной ячейке. Значит, в этой ячейке обязательно будет «4». Заносим «4» в данную ячейку и вычеркиваем из других ячеек 2-го столбца и 5-ой строки. Аналогично, в желтом столбце кандидат «2» встречается один раз, следовательно, в данную ячейку заносим «2» и исключаем «2» из ячеек 7-ой строки и соответствующего блока.

Предыдущие два метода – это единственные методы, которые однозначно определяют содержимое ячейки. Следующие методы позволяют только уменьшать количество кандидатов в ячейках, что рано или поздно приведет к одиночкам или скрытым одиночкам.

Запертый кандидат

Бывают случаи, когда кандидат в пределах блока находится только в одном строке (или в одном столбце). В силу того, что одна из этих ячеек обязательно будет содержать этого кандидата, из всех остальных ячеек данной строки (столбца) этого кандидата можно исключить.

В примере ниже, центральный блок содержит кандидата «2» только в центральном столбце (желтые ячейки). Значит, одна из этих двух ячеек точно должна быть «2», и никакие другие ячейки в том ряду вне этого блока не могут быть «2». Поэтому «2» может быть исключен как кандидат из других ячеек этого столбца (ячейки зеленого цвета).

Открытые пары

Если две ячейки в группе (строке, столбце, блоке) содержат идентичную пару кандидатов и ничего более, то никакие другие ячейки этой группы не могут иметь значения этой пары. Эти 2 кандидата могут быть исключены из других ячеек в группе. В примере ниже, кандидаты «1» и «5» в колонках восемь и девять формируют Открытую Пару в пределах блока (желтые ячейки). Поэтому, так как одна из этих ячеек должна быть «1», а другая должны быть «5», кандидаты «1» и «5» исключаем из всех других ячеек этого блока (зеленые ячейки).

Тоже самое можно сформулировать для 3 и 4-х кандидатов, только участвует уже 3 и 4 ячейки, соответственно. Открытые тройки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета.

Открытые четверки: из ячеек зеленого цвета исключаем значения ячеек желтого цвета.

Скрытые пары

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

Аналогично, можно искать скрытые тройки и четверки.

x-wing

Если значение имеет только два возможных местоположения в какой-то строке (столбце), то оно обязательно должно быть назначено в одну из этих ячеек. Если же существует еще одна строка (столбец), где этот же кандидат также может быть только в двух ячейках и столбцы (строки) этих ячеек совпадают, то ни одна другая ячейка этих столбцов (строк) не может содержать данную цифру. Рассмотрим пример:

В 4-ой и 5-ой строках цифра «2» может быть только в двух ячейка желтого цвета, при чем эти ячейки находятся в одинаковых столбцах. Следовательно, цифра «2» может быть записана только двумя способами: 1) если «2» записать в 5-ый столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 7-ым столбцом.

2) если «2» записать в 7-ой столбец 4-ой строки, то из желтых ячеек «2» надо исключит и тогда в 5-ой строке положение «2» определяется однозначно 5-ым столбцом.

Следовательно, 5-ый и 7-ой столбец обязательно будут иметь цифру «2» либо в 4-ой строке, либо в 5-ой. Тогда из других ячеек данных столбцов цифру «2» можно исключить (зеленые клетки).

«Рыба Меч» (Swordfish)

Этот метод является вариацией метода «x-wing».

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

Алгоритм:

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

Эта же логика применима и в случае трех колонок, где кандидат ограничивается тремя строками.

Рассмотрим пример. В трех строчках (3, 5 и 7-ая) кандидат «5» встречается не более трех раз (ячейки выделены желтым цветом). При этом они принадлежат только трем столбцам: 3, 4 и 7-ому. Согласно методу «Рыба меч» из других ячеек этих столбцов кандидата «5» можно исключить (зеленые ячейки).

В примере, приведенном ниже, так же применяется метод «Рыба меч», но уже для случая трех колонок. Исключаем кандидата «1» из ячеек зеленого цвета.

«X-wing» и «Рыба меч» можно обобщить на случай четырех строк и четырех столбцов. Данный метод будет называться «Медуза».

Цвета

Бывают ситуации, когда кандидат встречается только два раза в группе (в строке, столбце или блоке). Тогда искомая цифра обязательно будет в одном из них. Стратегия метода «Цвета» заключается в том, чтобы просматривать эту взаимосвязь с использованием двух цветов, например, желтого и зеленого. При этом решение может быть в клеточках только какого-то одного цвета.

Выделяем все взаимосвязанные цепочки и принимаем решение:

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

В следующем примере применим метод «Цвета» для ячеек с кандидатом «9». Начинаем раскрашивать с ячейки в левом верхнем блоке (2 строка, 2 столбец), закрасим ее в желтый цвет. В своем блоке она имеет только одного соседа с «9», закрасим его в зеленый цвет. Также у нее только один сосед в столбце, закрашиваем и его в зеленый цвет.

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

Аналогичным образом работаем с остальными ячейками, содержащими цифру «9». Получаем:

Кандидат «9» может быть либо только во всех желтых ячейках, либо во всех зеленых. В правом среднем блоке встретились две ячейки одинакового цвета, следовательно, зеленый цвет неверный, так как в данном блоке получается две «9», что недопустимо. Исключаем, «9» из всех зеленых клеток.

Еще один пример на метод «Цвета». Пометим парные ячейки для кандидата «6».

Клетка с «6» в верхнем центральном блоке (выделим сиреневым цветом) имеет двух разноцветных кандидатов:

«6» обязательно будет или в желтой или в зеленой клетке, следовательно, из этой сиреневой клетки «6» можно исключить.

Пошаговое решение судоку: как разгадывать, заполнять, играть

Программа решения судоку с объяснениями (онлайн)

Описание:

Правила игры

Судоку — это игра-головоломка, где необходимо заполнить пустые клетки так, чтобы

1. каждая строка,
2. каждый столбец,
3. каждый малый квадрат 3×3

содержали все цифры от 1 до 9 (каждая цифра встречается только один раз).

Алгоритм заполнения ячеек судоку

Способ 1. «Скрытые одиночки»

В клетку строки заполняется цифра, если

1. она отсутствует в строке,
2. её можно вписать только в одну пустую клетку строки. Число становится кандидатом клетки, если этой цифры нет
   • в малом квадрате 3×3, который содержит клетку,
   • в столбце, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первой строке, а затем во всех строках.

В клетку столбца ставится цифра, если

1. она отсутствует в столбце,
2. её можно вписать только в одну пустую клетку столбца. Число становится кандидатом клетки, если этой цифры нет
   • в малом квадрате 3×3, который содержит клетку,
   • в строке, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первом столбце, а затем во всех столбцах.

В клетку малого квадрата 3×3 заполняется цифра, если

1. она отсутствует в малом квадрате 3×3,
2. её можно вписать только в одну пустую клетку малого квадрата 3×3. Число становится кандидатом клетки, если этой цифры нет
   • в столбце, который содержит клетку,
   • в строке, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первом малом квадрате 3×3, а затем во всех малых квадратах 3×3.

Способ 2. «Одиночки»

В клетку заносится цифра, если

1. в строке, которая содержит клетку,
2. в столбце, который содержит клетку,
3. в малом блоке 3×3, который содержит клетку

Таким образом проверяются все клетки.

Методы разгадывания судоку

Стратегия 1. Кандидат в двух-трёх клетках одного квадрата

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

1. 			3
   	6			8
   			9
   			5
   		6
   			4					9
   5	4	2		9	9	3	8
   6				4	5
   1		7			3			5

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

2. В клетке можно указать только цифру «2» (см. способ «Одиночки»), т.к. «6» и «9» должны располагаться в других клетках блока 3×3

   			3
   	6			8
   			9
   			5
   		6
   			4					9
   5	4	2	6	9	9	3	8
   6				4	5
   1		7	6	2	3			5

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

3. В клетке можно указать только цифру «2» (см. способ «Одиночки»), т.к. «4» и «5» должны располагаться в других клетках столбца

   			8	9	1
   	3			6	2
   					7
   			6	7	45
   			2	3	8
   			9	1	45

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

Если новые «скрытые одиночки» и «одиночки» обнаружены не были, то расписываются все возможные кандидаты для всех пустых клеток с учётом исключённых. А потом вычёркиваются те, что не подходят по причинам, описанным в Стратегии 2.

Стратегия 2. Группы кандидатов

Подсказка 2.1. Скрытые пары, тройки, четвёрки

Если две цифры-кандидата встречаются только в двух клетках одной строки/столбца/малого квадрата, то другие кандидаты в этих двух клетках удаляются

То же самое если три цифры-кандидата встречаются только в трёх клетках одной строки/столбца/малого квадрата.

Подсказка 2.2. Открытые пары, тройки, четвёрки

Если в двух клетках одной строки/столбца/малого квадрата используются только две одинаковые цифры-кандидата и ничего более, то те же кандидаты в других клетках этой строки/столбца/малого квадрата удаляются.

Пример «Открытые тройки» в 7-ом столбце из цифр «4», «6», «9»

Пример «Открытые четвёрки» в малом квадрате из цифр «4», «5», «7», «8»

Судоку в картинках. Раздача. — 86 ответов на Babyblog

Судоку — это логическая головоломка. Игра развивает логическое мышление, память и внимание.

Классическая игра судоку — с цифрами, цель которой расположить цифры на квадрате так, чтобы в каждом ряду и столбце не было повторений. Предлагаю вам попробовать поиграть в судоку с ребенком, используя квадраты с картинками вместо цифр. Мы начали играть в судоку в 2,7. Как играть писала тут.

Начинать желательно с квадрата 3х3 и только с одной пустой клеткой. По мере того, как малыш поймёт правила и суть игры, размер квадрата и количество пустых клеток можно увеличить.
В нашем комплекте 8 листов судоку с квадратами разного размера: 3х3 и 4х4 с одной-двумя-тремя пустыми клеточками.

Комплект бесплатный. Чтобы получить его, необходимо быть подписчиком моего блога, сделать репост (нажать внизу на значок В), в комментариях — спасибо и адрес своей электронной почты. Буду благодарна за отзывы и Бесплатная раздача материала может быть завершена в любой момент!

P.S.: Все предлагаемые материалы изготовлены мной самостоятельно и исходя из интересов собственного ребенка. Поэтому мы сначала занимаемся сами, и только после удачного «тестирования» я предлагаю материал для занятий другим на платной либо бесплатной основе. Каким будет материал (платным или бесплатным) зависит от объёма работы, её сложности и количества затраченных часов собственного времени. Все рисунки, сопровождающие каждое задание, выбираются мной очень тщательно, я эстет, люблю когда всё ровно и красиво)

ВАЖНО!!! Все мои материалы изготовлены исключительно в целях личного пользования! Если вы приобрели у меня комплект, пожалуйста, не выкладывайте его в сеть и не дарите третьим лицам! Пожалуйста, уважайте чужой труд! Также прошу делать ссылку на мой блог, если вы выкладываете фото или видео с фрагментами занятий по моим материалам.

Благодарю за внимание! Играйте и занимайтесь с удовольствием! 🙂

Математики придумали формулу для решения cудоку

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

Но для тех, кому разгадывание судоку стоит слишком больших усилий, это может быть буквально идеальным решением.

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

Исследователи комплексных сетей Золтан Торожкай и Мария Эркси-Раваз из Университета Нотр-Дама также смогли объяснить, почему некоторые загадки судоку более сложные, чем другие. Единственный недостаток в том, что для того, чтобы понять, что они предлагают, нужна степень доктора математики.

Вы можете решить эту головоломку? Она создана математиком Арто Инкалой, и, как утверждают, это самая сложная судоку в мире. Фото с сайта nature.com

Торожкай и Эркси-Раваз начали анализировать судоку как часть своего исследования теории оптимизации и вычислительной сложности. Они говорят, что большинство любителей судоку используют для решения этих задач подход «грубой силы», основанный на технике предположения. Таким образом, любители судоку вооружаются карандашом и пробуют все возможные комбинации чисел, пока не будет найден правильный ответ. Этот метод неизбежно приведет к успеху, но он трудоемок и занимает много времени.

Вместо этого Торожкай и Эркси-Раваз предложили универсальный аналоговый алгоритм, который абсолютно детерминирован (не использует предположение или перебор) и всегда находит правильное решение задачи, причем довольно быстро.

Исследователи использовали «детерминированный аналоговый решатель», чтобы заполнить эту судоку. Фото с сайта nature.com

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

Они создали шкалу от 1 до 4, где 1 – «легко», 2 – «средняя степень сложности», 3 – «сложно», 4 – «очень сложно». Для решения головоломки с рейтингом 2 требуется в среднем в 10 раз больше времени, чем для задачки с рейтингом 1. Согласно этой системе, самая сложная загадка из известных до сих пор имеет рейтинг 3.6; более сложные задачи судоку пока неизвестны.

Теория начинается с картографии вероятностей для каждого отдельного квадрата. Фото с сайта nature.com

«Я не интересовался судоку, пока мы не начали работать над более общим классом выполнимости Булевых проблем, – говорит Торожкай. – Так как судоку – часть этого класса, латинский квадрат 9-го порядка оказался для нас хорошим полем для испытаний, так я с ними и познакомился. Меня и многих исследователей, изучающих такие проблемы, захватывает вопрос, как далеко мы, люди, способны зайти в решении судоку, детерминировано, без перебора, который является выбором наугад, и, если догадка не верна, нужно вернуться на шаг или на несколько шагов назад и начать сначала. Наша аналоговая модель решения детерминирована: в динамике нет никакого случайного выбора или возвращения».

Теория хаоса: степень сложности загадок показывается здесь как хаотическая динамика. Фото с сайта nature.com

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

Опыт исследования также сделал Торожкая большим любителем судоку.

«У моей жены и у меня есть несколько приложений судоку на наших iPhone, и мы, должно быть, сыграли уже тысячи раз, соревнуясь за меньшее время на каждом уровне, – говорит он. – Она часто интуитивно видит комбинации паттернов, которых я не замечаю. Я должен их выводить. Для меня становится невозможным решить многие головоломки, которые наша шкала категоризирует как трудные или очень трудные, без того, чтобы записывать вероятности карандашом».

Методология Торожкая и Эркси-Раваз была впервые опубликована в журнале Nature Physics, а затем – в журнале Nature Scientific Reports.

изобретение великого математика :: Hi-tech :: Дни.ру

Как много вы знаете игр, которые положительно влияют на работу мозга? «Судоку» как раз является одной из них. Эта числовая головоломка помогает практиковать логическое мышление и развивает концентрацию. А самостоятельное решение игры может принести вам чувство удовлетворения.

Название головоломки пришло из Страны восходящего солнца. Оно состоит двух японских символов: SU – число и DOKU – единственный. Изначально игра имела длинное название «Suuji wa dokushin ni kagiru», которое означало, что числа должны встречаться только один раз, но вскоре его решили сократить до «Su Doku». 

Любопытно, что родиной головоломки является не Япония, а Швейцария. Праобраз «Судоку» придумал швейцарский математик Леонард Эйлер, который жил в XVIII веке. Свое изобретение он назвал «Греко-римские квадраты» или «Латинские квадраты». Игровое поле имело 4 строки и 4 столбца. Вместо цифр использовались буквы греческого и латинского алфавитов. Первые четыре буквы греческого алфавита объединялись с первыми буквами латинского алфавита. Каждый из символов не должен был повторяться ни в строке, ни в столбце. 

Лишь спустя два столетия игра была модернизирована американским архитектором Говардом Гарнсом. Он разбил сетку на девять блоков размером три на три, в каждом из которых теперь должно было стоять число, а не буква. Эти изменения значительно усложнили головоломку. Гарнс назвал такую игру «Number Place». Впервые она появилась в 1979 году в американском журнале «Dell Puzzle Magazine». Однако в то время читатели не заметили новую головоломку.

В 1984 году одно японское издание опубликовало «Судоку», и новая игра мгновенно приобрела невероятную популярность. Стали выпускаться отдельные сборники этой головоломки. В 2004 году игра впервые появилась в английской газете, и с тех пор головоломка распространилась по всему миру.

Игровое поле представляет собой квадрат, разделенный на девять небольших квадратов размером три на три. Каждый квадрат необходимо заполнить цифрами от 1 до 9 так, чтобы ни в строке, ни в столбике, ни в отдельном квадрате цифры не повторялись. У игроков заранее есть подсказки – в некоторых ячейках уже проставлены цифры. Чем их больше – тем уровень легче.

На сайте Dni.ru вы можете сыграть в «Судоку» абсолютно бесплатно. Сначала вам необходимо выбрать уровень сложности: «легко», «нормально», «сложно» или «жутко». В правом верхнем углу находится таймер, на котором вы увидите, сколько времени вы потратили на решении головоломки. Также вы можете проверить правильность всех цифр, очистить поле или даже сдаться. Есть также возможность напечатать игру. Посмотрим, сможете ли вы пройти самый сложный (жуткий) уровень в игре «Судоку» на нашем сайте? 

ЧИТАЙТЕ «ДНИ.РУ» В «ТЕЛЕГРАМЕ» – ИНТЕРЕСНЫЕ НОВОСТИ И ПОДАРКИ

Создание приложения для решения судоку с компьютерным зрением и поиском с возвратом | by Youness Mansar

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

Судоку — это логическая головоломка, которая обычно представлена ​​в виде сетки 9×9 и подсеток 3×3 от 1 до 9 цифр. Условием для правильного решения этой головоломки является то, что никакая цифра не используется дважды в любой строке, столбце или подсетке 3×3.

Количество возможных сеток 9×9 — 6.21, поэтому поиск решения иногда может быть сложной задачей в зависимости от первоначальной головоломки. В этом проекте мы создадим приложение Streamlit, которое может автоматически решать головоломки судоку, используя снимок экрана с одной из них.

Сначала мы построим модель распознавания символов объекта, которая может извлекать цифры из изображения сетки судоку, а затем поработаем над подходом с возвратом для ее решения. Окончательное приложение будет доступно через простое в использовании приложение Streamlit.

Представление Sudoku в Python и первая версия решателя в основном были взяты и изменены из этого репо: https: // github.com / RutledgePaulV / sudoku-generator

Когда у нас есть изображение головоломки, нам нужно извлечь все цифры, которые там написаны, а также их положение. .

Для этого мы обучим модель детектора цифр, а затем модель распознавателя цифр. Первый сообщит нам, где на изображении появляется цифра, а второй сообщит нам, что это за цифра. Мы также получим набор данных для обеих этих задач.

Модель детектора

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

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

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

Модель распознавателя

Роль модели распознавателя состоит в том, чтобы принять в качестве входных данных одну цифру и предсказать, какая она из набора {1, 2, 3, 4, 5, 6, 7, 8 9}. Это в основном сверточная сеть, но на выходе получается полностью связанный слой с активацией softmax.

Data-set

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

Чтобы получить реалистичный набор данных, мы используем несколько типов шрифтов, размеров, цветов фона, элементов сетки …

Поскольку мы генерируем эти примеры с нуля, мы можем получить все подробности о позиции и классе каждой цифры на изображении.

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

В случае судоку мы сделаем это следующим образом:

• Для каждой ячейки мы вычисляем возможные значения, которые можно использовать для ее заполнения с учетом состояния сетки. Мы можем сделать это очень легко путем исключения.
• Мы сортируем ячейки по количеству возможных значений, от наименьшего к наибольшему.
• Мы проходим первую незаполненную ячейку и присваиваем ей одно из возможных значений, затем следующее и т. Д.
• , если мы заканчиваем, мы получаем возможное решение, мы возвращаем его, иначе мы возвращаемся к последней ячейке, которую мы присвоил значение и изменил его состояние на другое возможное значение. Что-то вроде поиска по дереву в глубину.

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

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

Реализация (некоторые операции, такие как сортировка, выполняются в классе Board):

 def backtracking_solve (board): 
 # Изменено с https://github.com/RutledgePaulV/sudoku-generator/blob/master/ Судоку / Solver.py 
 set_initially_available (board.ячейки) 
 to_be_filled = board.get_unused_cells () 
 index = 0 
 n_iter = 0 
 while -1  current = to_be_filled [index] 
 flag = False 
 possible_values ​​= board.get_possibles (current) 
 my_range = range (current.value + 1, 10) 
 для x в my_range: 
 если x в возможных_values: 
 n_iter + = 1 
 current.value = x 
 flag = True 
 break 
 if not flag: 
 current. value = 0 
 index - = 1 
 else: 
 index + = 1 
 if len (to_be_filled) == 0: 
 return n_iter, False 
 else: 
 return n_iter, index == len (to_be_filled) 

Мы строим приложение с помощью Streamlit.Приложение должно позволять нам загружать изображение, решать судоку и отображать результаты.

Загрузка файла:

Streamlit обеспечивает простой способ создания виджета загрузки файлов с помощью st.file_uploader.

 file = st.file_uploader ("Загрузить изображение судоку", type = ["jpg", "png"]) 

OCR:

Мы применяем модель детектора и распознавателя для создания сетки.

 grid = img_to_grid (img, Detector_model, распознаватель_модель, plot_path = None, print_result = False) 

Решение:

Мы используем отслеживание с возвратом для решения судоку.

 n_iter, _ = backtracking_solve (to_solve_board) 

Отображение результатов:

Мы отображаем результаты в красивой таблице Html / Css, указав unsafe_allow_html = True.

 html_board.markdown ("" + to_solve_board.html () + "", unsafe_allow_html = True) 

Окончательный результат:

нейронная сеть для автоматического решения головоломок судоку

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

Программы для решения головоломок Судоку обычно требуют пользователь может вручную ввести начальные числа. Теперь, используя метод, разработанный Нирамитрой Редди, студенткой факультета компьютерных наук и инженерии Национального технологического института Карнатаки (город Мангалор, штат Карнатаке, Индия; нитк.ac.in ), игрок в судоку, застрявший в тупике, может просто сфотографировать головоломку, а все остальное сделает техника обработки изображений и нейронные сети.

Редди создал свое решение для решения судоку с графическим интерфейсом в свободном доступе на Github ( bit.ly/VSDSUD ). Программное обеспечение включает в себя пользовательский интерфейс для просмотра вручную в случае неправильного распознавания номера программой обработки изображений. Однако, по словам Редди, коэффициент нераспознавания программного обеспечения на тестовых наборах оценивается только в 3%.

После того, как будет сделан снимок головоломка, программа размывает изображение с помощью функции Гаусса для уменьшения шума. Адаптивная пороговая обработка по Гауссу устанавливает для всех пикселей изображения черный или белый цвет, заменяя степень потери деталей. Затем программа инвертирует изображение так, чтобы цифры и линии головоломки были белыми. Расширение изображения с последующим заливкой определяет линии доски. Затем метод извлечения элемента «Преобразование линии Хафа» определяет внешние края платы, и программа вырезает их.

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

Программа может работать как сверточный нейронная сеть или k-ближайшие соседи.Модели обучаются с помощью набора данных рукописных цифр MNIST ( bit.ly/VSD-MNS ).

python — как получить ячейки сетки судоку с помощью OpenCV?

Шагов:

1. Предварительная обработка изображения (операция закрытия)
2. Поиск квадрата судоку и создание изображения маски
3. Поиск вертикальных линий
4. Поиск горизонтальных линий
5. Поиск точек сетки
6. Устранение дефектов
7. Извлечение цифр из каждой ячейки

Код:

  # ========== импортировать необходимые пакеты ============
импорт imutils
импортировать numpy как np
импорт cv2
из преобразования импорта four_point_transform
из PIL импорта изображения
импорт pytesseract
импортная математика
из скимэджа.фильтры импорт threshold_local

# =============== Для трансформации ==============
def order_points (баллы):
    "" "инициализируйте список координат, которые будут упорядочены
    так что первая запись в списке находится в верхнем левом углу,
    вторая запись находится справа вверху, третья -
    нижний правый, а четвертый - нижний левый "" "

    rect = np.zeros ((4, 2), dtype = "float32")
 
    # в верхней левой точке будет наименьшая сумма, тогда как
    # в правой нижней точке будет наибольшая сумма
    s = баллысумма (ось = 1)
    rect [0] = pts [np.argmin (s)]
    rect [2] = pts [np.argmax (s)]
 
    # теперь вычислим разницу между точками,
    # верхняя правая точка будет иметь наименьшее различие,
    # тогда как в нижнем левом углу будет наибольшая разница
    diff = np.diff (точки, ось = 1)
    rect [1] = pts [np.argmin (diff)]
    rect [3] = pts [np.argmax (diff)]
 
    # возвращаем упорядоченные координаты
    return rect


def four_point_transform (изображение, точки):
    # получить согласованный порядок точек и распаковать их
    # индивидуально
    rect = order_points (баллы)
    (tl, tr, br, bl) = rect
 
    # вычисляем ширину нового изображения, которая будет
    # максимальное расстояние между нижним правым и нижним левым
    # x-координаты или верхняя правая и верхняя левая x-координаты
    widthA = np.sqrt ((((br [0] - bl [0]) ** 2) + ((br [1] - bl [1]) ** 2))
    widthB = np.sqrt (((tr [0] - tl [0]) ** 2) + ((tr [1] - tl [1]) ** 2))
    maxWidth = max (int (ширинаA), int (ширинаB))
 
    # вычисляем высоту нового изображения, которая будет
    # максимальное расстояние между правым верхом и правым нижним
    # y-координаты или верхняя левая и нижняя левая координаты y
    heightA = np.sqrt (((tr [0] - br [0]) ** 2) + ((tr [1] - br [1]) ** 2))
    heightB = np.sqrt (((tl [0] - bl [0]) ** 2) + ((tl [1] - bl [1]) ** 2))
    maxHeight = max (int (высотаA), int (высотаB))
 
    # теперь, когда у нас есть размеры нового изображения, построим
    # набор точек назначения для просмотра "с высоты птичьего полета",
    # (я.е. вид сверху вниз) изображения, снова указывая точки
    # в верхнем левом, верхнем правом, нижнем правом и нижнем левом
    # порядок
    dst = np.array ([
        [0, 0],
        [maxWidth - 1, 0],
        [maxWidth - 1, maxHeight - 1],
        [0, maxHeight - 1]], dtype = "float32")
 
    # вычисляем матрицу перспективного преобразования и затем применяем ее
    M = cv2.getPerspectiveTransform (rect, dst)
    warped = cv2.warpPerspective (изображение, M, (maxWidth, maxHeight))
 
    # вернуть деформированное изображение
    возвращение искривлено

############## Чтобы показать изображение ##############
def show_image (img, title):
    cv2.imshow (название, img)
    cv2.waitKey (0)
    cv2.destroyAllWindows ()


def find_largest_feature (inp_img, scan_tl = None, scan_br = None):
    "" "
    Использует тот факт, что функция `floodFill` возвращает ограничивающую рамку области, которую она залила, чтобы найти самый большой
    связная пиксельная структура изображения. Заполняет эту структуру белым цветом, остальное уменьшая до черного.
    "" "
    img = inp_img.copy () # Копируем изображение, оставляя оригинал нетронутым
    высота, ширина = img.shape [: 2]

    max_area = 0
    seed_point = (Нет, Нет)

    если scan_tl - Нет:
        scan_tl = [0, 0]

    если scan_br - Нет:
        scan_br = [ширина, высота]

    # Прокрутите изображение
    для x в диапазоне (scan_tl [0], scan_br [0]):
        для y в диапазоне (scan_tl [1], scan_br [1]):
            # Работайте только на светлых или белых квадратах
            если img.item (y, x) == 255 и x  max_area: # Получает максимальную граничную область, которая должна быть сеткой
                    max_area = площадь [0]
                    seed_point = (х, у)

    # Раскрасьте все в серый цвет (компенсирует функции, выходящие за пределы нашего среднего диапазона сканирования
    для x в диапазоне (ширина):
        для y в диапазоне (высота):
            если img.item (y, x) == 255 и x <ширина и y <высота:
                cv2.floodFill (img, Нет, (x, y), 64)

    mask = np.zeros ((height + 2, width + 2), np.uint8) # Маска на 2 пикселя больше изображения

    # Выделите главную особенность
    если все ([p не равно None для p в seed_point]):
        cv2.floodFill (img, mask, seed_point, 255)

    

    для x в диапазоне (ширина):
        для y в диапазоне (высота):
            if img.item (y, x) == 64: # Скрыть все, что не является основной функцией
                cv2.floodFill (img, маска, (x, y), 0)
    
    вернуть img


################# Предварительная обработка изображения судоку ###############
def препроцесс (изображение, случай):
    ratio = image.shape [0] / 500,0
    orig = image.copy ()
    image = imutils.resize (изображение, высота = 500)

    если case == True:
    
        серый = cv2.GaussianBlur (изображение, (5,5), 0)
        серый = cv2.cvtColor (серый, cv2.COLOR_BGR2GRAY)
        маска = np.zeros ((gray.shape), np.uint8)
        ядро1 = cv2.getStructuringElement (cv2.MORPH_ELLIPSE, (11,11))

        закрыть = cv2.morphologyEx (серый, cv2.MORPH_CLOSE, kernel1)
        div = np.float32 (серый) / (закрыть)
        res = np.uint8 (cv2.normalize (div, div, 0,255, cv2.NORM_MINMAX))
        res2 = cv2.cvtColor (res, cv2.COLOR_GRAY2BGR)
        edged = cv2.Canny (res, 75, 200)
    
        cnts = cv2.findContours (edged.copy (), cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
        cnts = cnts [0] if imutils.is_cv2 () else cnts [1]
        cnts = sorted (cnts, key = cv2.contourArea, reverse = True) [: 5]
 
        # перебрать контуры
        для c в центрах:
            # аппроксимируем контур
            rect = cv2.boundingRect (c)
            area = cv2.contourArea (c)

            cv2.rectangle (edged.copy (), (rect [0], rect [1]), (rect [2] + rect [0], rect [3] + rect [1]), (0,0,0) ), 2)
            пери = cv2.arcLength (c, Истина)
            приблизительно = cv2.approxPolyDP (c, 0,02 * пери, True)
 
            # если наш приближенный контур состоит из четырех точек, то мы
            # можно предположить, что мы нашли наш экран
            если len (приблизительно) == 4:
                screenCnt = приблизительно
                #print (screenCnt)
                перемена
         
        # показать контур (очертание) листка бумаги
        #print (screenCnt)
        cv2.drawContours (изображение, [screenCnt], -1, (0, 255, 0), 2)
    
        # применяем четырехточечное преобразование для получения нисходящего
        # просмотр исходного изображения
        warped = four_point_transform (orig, screenCnt.reshape (4, 2) * соотношение)
        warped1 = cv2.resize (деформированный, (610,610))
        warp = cv2.cvtColor (деформированный, cv2.COLOR_BGR2GRAY)
        T = threshold_local (деформация, 11, смещение = 10, метод = "гауссовский")
        warp = (warp> T) .astype ("uint8") * 255
        th4 = cv2.adaptiveThreshold (warp, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, \
            cv2.THRESH_BINARY_INV, 11,2)
        ядро = np.ones ((5,5), np.uint8)
        дилатация = cv2.GaussianBlur (th4, (5,5), 0)

    еще :
        
        деформировано = изображение
        warped1 = cv2.resize (деформированный, (610,610))
        warp = cv2.cvtColor (деформированный, cv2.COLOR_BGR2GRAY)
        T = threshold_local (деформация, 11, смещение = 10, метод = "гауссовский")
        warp = (warp> T) .astype ("uint8") * 255
        th4 = cv2.adaptiveThreshold (warp, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, \
            cv2.THRESH_BINARY_INV, 11,2)

    #show_image (warped1, "предварительно обработанный")

    возврат th4, warped1, warped

def сетки (img, warped2):
    #print ("im:", img.shape)
    img2 = img.copy ()
    img = np.zeros ((500,500,3), np.uint8)

    ratio2 = 3
    kernel_size = 3
    lowThreshold = 30

    frame = img

    img = cv2.resize (кадр, (610,610))

    для i в диапазоне (10):
        cv2.line (img, (0, (img.shape [0] // 9) * i), (img.shape [1], (img.shape [0] // 9) * i), (255, 255, 255), 3, 1)
        cv2.line (warped2, (0, (img.shape [0] // 9) * i), (img.shape [1], (img.shape [0] // 9) * i), (125, 0, 55), 3, 1)
    
    для j в диапазоне (10):
        cv2.line (img, ((img.shape [1] // 9) * j, 0), ((img.shape [1] // 9) * j, img.shape [0]), (255, 255, 255), 3, 1)
        cv2.line (warped2, ((img.shape [1] // 9) * j, 0), ((img.shape [1] // 9) * j, img.shape [0]), (125, 0, 55), 3, 1)
  
    #show_image (warped2, "сетки")
    вернуть img

############### Определение точек пересечения для получения сеток #########
def grid_points (img, warped2):
    img1 = img.copy ()
    kernelx = cv2.getStructuringElement (cv2.MORPH_RECT, (2,10))

    dx = cv2.Sobel (img, cv2.CV_16S, 1,0)
    dx = cv2.convertScaleAbs (dx)
    c = cv2.normalize (dx, dx, 0,255, cv2.NORM_MINMAX)
    c = cv2.morphologyEx (c, cv2.MORPH_DILATE, kernelx, итерации = 1)
    cy = cv2.cvtColor (c, cv2.COLOR_BGR2GRAY)
    closex = cv2.morphologyEx (cy, cv2.MORPH_DILATE, kernelx, итерации = 1)

    kernely = cv2.getStructuringElement (cv2.MORPH_RECT, (10,2))
    dy = cv2.Sobel (img, cv2.CV_16S, 0,2)
    dy = cv2.convertScaleAbs (dy)
    c = cv2.normalize (dy, dy, 0,255, cv2.NORM_MINMAX)
    c = cv2.morphologyEx (c, cv2.MORPH_DILATE, kernely, итерации = 1)
    cy = cv2.cvtColor (c, cv2.COLOR_BGR2GRAY)
    closey = cv2.morphologyEx (cy, cv2.MORPH_DILATE, kernelx, итерации = 1)

    res = cv2.bitwise_and (близко, близко)
    #gray = cv2.cvtColor (img, cv2.COLOR_BGR2GRAY)
    ret, thresh = cv2.threshold (res, 0,255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)

    ядро = np.ones ((6,6), np.uint8)


    # Выполнить морфологию
    se = np.ones ((8,8), dtype = 'uint8')
    image_close = cv2.morphologyEx (порог, cv2.MORPH_CLOSE, se)
    image_close = cv2.morphologyEx (image_close, cv2.MORPH_OPEN, ядро)

    contour, hier = cv2.findContours (image_close, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
    cnts = sorted (contour, key = cv2.contourArea, reverse = True) [: 100]
    центроиды = []
    для cnt в cnts:
    
        мама = cv2.moments (cnt)
        (x, y) = int (мама ['m10'] / мама ['m00']), int (мама ['m01'] / мама ['m00'])
        cv2.circle (img1, (x, y), 4, (0,255,0), - 1)
        cv2.circle (warped2, (x, y), 4, (0,255,0), - 1)
        центроиды.добавить ((x, y))

    #show_image (warped2, "grid_points")


    Точки = np.array (центроиды, dtype = np.float32)
    c = Points.reshape ((100,2))
    c2 = c [np.argsort (c [:, 1])]

    b = np.vstack ([c2 [i * 10: (i + 1) * 10] [np.argsort (c2 [i * 10: (i + 1) * 10,0])] для i в диапазоне (10 )])
    bm = b.reshape ((10,10,2))

    возврат c2, bm, cnts

############ Распознавать цифровые изображения по номеру #############
def image_to_num (c2):
    img = 255-c2
    text = pytesseract.image_to_string (img, lang = "eng", config = '- psm 6 --oem 3') # builder = builder)
    список возврата (текст) [0]

###### Чтобы получить цифру в определенной ячейке #############
def get_digit (c2, bm, warped1, cnts):
    число = []
    centroidx = np.пустой ((9, 9))
    centroidy = np.empty ((9, 9))
    глобальный список_изображений
    list_images = []
    для i в диапазоне (0,9):
        для j в диапазоне (0,9):

            x1, y1 = bm [i] [j] # bm [0] row1
            x2, y2 = bm [i + 1] [j + 1]
            
            Координаты x = ((x1 + x2) // 2)
            координата = ((y1 + y2) // 2)
            centroidx [i] [j] = correx
            centroidy [i] [j] = корди
            урожай = warped1 [int (x1): int (x2), int (y1): int (y2)]
            обрезка = imutils.resize (обрезка, высота = 69, ширина = 67)
            c2 = cv2.cvtColor (урожай, cv2.COLOR_BGR2GRAY)
            c2 = cv2.adaptiveThreshold (c2,255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, \
                cv2.THRESH_BINARY_INV, 11,2)
            ядро = np.ones ((2,2), np.uint8)
            # c2 = cv2.morphologyEx (c2, cv2.MORPH_OPEN, ядро)
            c2 = cv2.copyMakeBorder (c2,5,5,5,5, cv2.BORDER_CONSTANT, значение = (0,0,0))
            нет = 0
            shape = c2.shape
            w = форма [1]
            h = форма [0]
            мама = cv2.moments (c2)
            (x, y) = int (мама ['m10'] / мама ['m00']), int (мама ['m01'] / мама ['m00'])
            c2 = c2 [14: 70,15: 62]
            контур, hier = cv2.findContours (c2, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
            если cnts не равно None:
                cnts = sorted (contour, key = cv2.contourArea, reverse = True) [: 1]

            для cnt в cnts:
                x, y, w, h = cv2.boundingRect (cnt)
                аспект_ratio = ш / ч
# печать (соотношение сторон)
                area = cv2.contourArea (cnt)
                #print (площадь)
                если area> 120 и cnt.shape [0]> 15 и aspect_ratio> 0,2 и aspect_ratio <= 0,9:
                    #print ("площадь:", площадь)
                    c2 = find_largest_feature (c2)
                    #show_image (c2, "box2")
                    контур, hier = cv2.findContours (c2, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
                    cnts = sorted (contour, key = cv2.contourArea, reverse = True) [: 1]
                    для cnt в cnts:
                        rect = cv2.boundingRect (cnt)
                        # cv2.rectangle (c2, (rect [0], rect [1]), (rect [2] + rect [0], rect [3] + rect [1]), (255,255,255), 2).
                        c2 = c2 [rect [1]: rect [3] + rect [1], rect [0]: rect [2] + rect [0]]
                        c2 = cv2.copyMakeBorder (c2,5,5,5,5, cv2.BORDER_CONSTANT, значение = (0,0,0))
                        list_images.добавить (c2)
                    #show_image (c2, "коробка")
                    no = image_to_num (c2)
            num.append (нет)
    centroidx = np.transpose (centroidx)
    centroidy = np.transpose (центроид)
    вернуть c2, num, centroidx, centroidy

######## Создание матрицы и номера заполнения существуют в исходном изображении #######
def sudoku_matrix (число):
    с = 0
    сетка = np.empty ((9, 9))
    для i в диапазоне (9):
        для j в диапазоне (9):
            сетка [i] [j] = int (num [c])
            
            с + = 1
    сетка = np.транспонировать (сетка)
    возвратная сетка

######## Создание доски для отображения результата головоломки в терминале ##############
доска def (обр):
    для i в диапазоне (9):
    
        если я% 3 == 0:
                печать ("+", конец = "")
                печать ("------- +" * 3)
                
        для j в диапазоне (9):
            если j% 3 == 0:
                print ("", конец = "|")
            print (int (arr [i] [j]), end = "")
      
        print ("", конец = "|")
        Распечатать()
      
    печать ("+", конец = "")
    печать ("------- +" * 3)
    возврат
   
def check_col (arr, num, col):
    если все ([num! = arr [i] [col] для i в диапазоне (9)]):
        вернуть True
    вернуть ложь
    

def check_row (arr, num, row):
    если все ([num! = arr [row] [i] for i in range (9)]):
        вернуть True
    вернуть ложь


def check_cell (arr, num, row, col):
    sectopx = 3 * (строка // 3)
    sectopy = 3 * (столбец // 3)
          
    для i в диапазоне (sectopx, sectopx + 3):
        для j в диапазоне (sectopy, sectopy + 3):
            если arr [i] [j] == num:
                вернуть True
    вернуть ложь


def empty_loc (arr, l):
    для i в диапазоне (9):
        для j в диапазоне (9):
            если arr [i] [j] == 0:
                l [0] = я
                l [1] = j
                вернуть True
    вернуть ложь

#### Решение судоку с помощью обратного отслеживания ############
def судоку (аранжировка):
    l = [0,0]

    если не empty_loc (arr, l):
        вернуть True
    
    row = l [0]
    col = l [1]
                
    для числа в диапазоне (1,10):
        если check_row (arr, num, row) и check_col (arr, num, col), а не check_cell (arr, num, row, col):
            arr [строка] [col] = int (число)
            
            если (судоку (арр)):
                вернуть True
 
            # ошибка, отключить и повторить попытку
            arr [row] [col] = 0
                    
    вернуть ложь

def overlay (arr, num, img, cx, cy):
    нет = -1
    для i в диапазоне (9):
        для j в диапазоне (9):
            нет + = 1
            # cv2.putText (img, str (нет), (int (cx [i] [j]), int (cy [i] [j])), cv2.FONT_HERSHEY_SIMPLEX, 0.5, (0, 0, 0), 2)
            если num [no] == 0:
                
                cv2.putText (img, str (int (arr [j] [i])), (int (cx [i] [j] -4), int (cy [i] [j]) + 8), cv2. FONT_HERSHEY_SIMPLEX, 1, (0, 255, 0), 4)
                
    cv2.imshow ("Судоку", img)
    cv2.waitKey (0)
  

  case = "False" # Если требуется преобразование, установите True
image = cv2.imread ("QupKb.png")

th4, warped1, warped = препроцесс (изображение, случай)
warped2 = warped1.копия ()
img = сетки (деформированные, деформированные2)
c2, bm, cnts = grid_points (img, warped2)
c2, число, cx, cy = get_digit (c2, bm, warped1, cnts)
сетка = Sudoku_matrix (число)
если (судоку (сетка)):
    arr = доска (сетка)
    наложение (arr, num, warped1, cx, cy)

еще:
    print («Нет решения»)
  

деформированный:

тх4:

деформированный2:

судоку результат:

Все извлеченные цифры:

  ########## Для просмотра всех извлеченных цифр ###############
_, axs = plt.подзаголовки (1, len (list_images), figsize = (24, 24))
axs = axs.flatten ()
для img, топор в zip (list_images, axs):
    ax.imshow (cv2.resize (img, (64,64)))
plt.show ()
  

Артикул:

простых судоку с возвратом. Статья, посвященная возврату… | Бен | Стартап

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

Эта статья надеется стать тем недостающим элементом, который позволит вам использовать реальный пример с простыми объяснениями, чтобы вы могли быстро вернуться к подготовке к собеседованию, или использовать обратный поиск в своей собственной программе, чтобы сделать что-нибудь интересное!

Примечание. Если вы уже знакомы с правилами Содоку, не стесняйтесь переходить к разделу «Отслеживание с возвратом».

В этой статье мы исследуем принцип обратного отслеживания, используя его для решения игры в судоку. Если вы никогда раньше не слышали о судоку, это логическая игра-головоломка, в которой вам нужно объединить числа, чтобы полностью заполнить доску. Задача состоит в том, чтобы заполнить сетку 9x9 так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3x3, составляющих сетку, содержали все цифры от 1 до 9. При запуске некоторые сетки частично заполняются.Вот пример стартовой доски.

И вот решение вышеприведенной доски. Обратите внимание, что в каждой строке и каждом столбце есть цифры от 1 до 9.

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

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

До сих пор я довольно часто упоминал термин «возврат», но что это, черт возьми? Отслеживание с возвратом - это общий алгоритм поиска всех (или некоторых) решений проблемы, который постепенно создает кандидатов для решения. Как только он определяет, что кандидат не может быть решением проблемы, он отказывается от него («возвращается»).

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

Восемь ферзей (N-ферзей) и другие задачи

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

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

Я не буду углубляться в N-Queens, потому что это довольно теоретически, и цель этой статьи - использовать простые примеры из реальных слов, но если вы хотите узнать больше, вот фантастическая статья от Сачина Малхотры, которая углубляется в это.

Другие распространенные проблемы, о которых вы, вероятно, уже слышали в отношении обратного отслеживания, - это его использование в кроссвордах, словесной арифметике и поиск пути через лабиринт. Это также наиболее удобный (если не самый эффективный) метод анализа комбинаторных задач оптимизации задачи о рюкзаке. Это также основа так называемых языков «логического программирования», таких как Prolog, Icon и Planner.

Дополнительные сведения об алгоритме

Помимо исходной проблемы и конечной цели, обратное отслеживание обычно имеет набор ограничений, которым программа также должна следовать, чтобы быть эффективной.

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

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

Ограничения

Помните, что ограничения для проекта определяются путем проверки каждого отдельного кандидата. Кандидат в судоку считается действительным, если выполняются следующие ограничения.

• Каждая строка имеет уникальные номера от 1 до 9 или пустые места.
• Каждый столбец имеет уникальные номера от 1 до 9 или пустые места.
• Каждая подсетка 1–9 имеет числа 1–9 или пустые места.

Цель и условия завершения

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

• Введите числа от 1 до 9 ровно один раз в каждую строку, столбец и область 3x3.

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

• Плата уже заполнена, то есть пустого пространства нет.
• Больше не осталось пустых мест для проверки алгоритмом, и текущий кандидат не достигает нашей цели.

Код

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

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

Я хотел бы поблагодарить https://www.101computing.net/ за их красивую визуализацию и основу для кода, приведенного выше. Я просто внес некоторые изменения, чтобы облегчить чтение и понимание происходящего.

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

• N-Queens: Более теоретический, но общий вопрос собеседования. Я упоминал об этом ранее, но отличную статью по этой конкретной проблеме можно найти здесь.
• Решение лабиринта: Еще один практичный, забавный пример, который также может решить обратный поиск. Мой одноклассник написал об этом хорошую статью, которую можно найти здесь.Если вы хотите проверить алгоритм сейчас, вот отличная визуализация, которую я нашел.

Если вы хотите узнать больше об отслеживании с возвратом и его вариантах использования, вот несколько различных статей, которые помогут вам глубже понять.

Спасибо за внимание. Я надеюсь, что теперь у вас есть более глубокое понимание того, как найти полезный случай для этого!

Если вы хотите проверить другие вещи, которые я сделал, зайдите на Github.

Решатель судоку OpenCV и распознавание текста

Получите доступ к коду этого руководства и всех других более чем 400 руководств по PyImageSearch

Введите свой адрес электронной почты ниже, чтобы узнать больше о PyImageSearch University (включая информацию о том, как загрузить исходный код в этот пост):

Что входит в PyImageSearch University?

• Легкий доступ к коду, наборам данных и предварительно обученным моделям для всех 400+ руководств в блоге PyImageSearch
• Высококачественный, хорошо документированный исходный код с построчными пояснениями (гарантируя, что вы точно знаете, что делает код)
• Jupyter Notebooks , которые предварительно настроены для работы в Google Colab одним щелчком мыши
• Запускайте все примеры кода в своем веб-браузере - конфигурация среды разработки не требуется!

• Поддержка всех основных операционных систем (Windows, macOS, Linux и Raspbian)
• Полный доступ к курсам PyImageSearch University
• Подробные видеоуроки к каждому уроку
• Свидетельства об окончании за все курсы
• Новые курсы добавляются по каждый месяц! - оставайтесь в курсе последних тенденций в области компьютерного зрения и глубокого обучения

PyImageSearch University - действительно лучшая степень магистра компьютерного видения, которую я хотел бы получить, когда только начинал. Возможность получить доступ ко всем руководствам Адриана на одной проиндексированной странице и возможность начать играть с кодом, не переживая кошмар настройки всего, - это просто потрясающе. 10/10 рекомендую.

Саньям Бутани Инженер по машинному обучению и 2 мастера Kaggle

Получите

Или перейдите на годовую за 59 долларов.40 / год и сэкономьте 15%!

• Доступ к централизованным репозиториям кода для все 400+ руководств на PyImageSearch
• Простой код доступа для все новых руководств , которые публикуются каждый понедельник в 10:00 EST
• Простая загрузка в один клик для кода, моделей, наборов данных и т. Д.

PyImageSearch University - действительно лучшая степень магистра компьютерного видения, которую я хотел бы получить, когда только начинал. Возможность получить доступ ко всем руководствам Адриана на одной проиндексированной странице и возможность начать играть с кодом, не переживая кошмар настройки всего, - это просто потрясающе. 10/10 рекомендую.

Саньям Бутани Инженер по машинному обучению и 2 мастера Kaggle

Решатель судоку с OpenCV 3.2 и Go

Пару недель назад мне очень хотелось начать изучать Go… и OpenCV. Я решил избавиться от этого зуда, работая над веб-приложением для решения головоломок судоку на базе OpenCV и Go с небольшим машинным обучением для загрузки.Идея была достаточно простой:

• Загрузите изображение и «проанализируйте» головоломку с помощью OpenCV, например. найти сетку и цифры
• Используйте тестовый набор цифр из примеров головоломок, чтобы обучить модель машинного обучения определять цифры
• Решите головоломку, используя некоторые алгоритмы распространения ограничений, которые я изучил во время работы с программой Udacity AI nanodegree

Along Кстати, погружение в OpenCV привело к тому, что я порезал зубы на C ++, потратив немало времени на понимание CGO (мост между Go и C / C ++) и нескольких новых самородков знаний о Docker.Вот краткая демонстрация того, как это закончилось:

Прочтите, как это произошло…

«Разбор» изображений судоку с помощью OpenCV

Текущая версия 3.x OpenCV предоставляет C ++ API, поэтому я установил C / C ++ Плагин Tools для Visual Studio Code и начал читать образец кода OpenCV. Я хотел иметь возможность обнаруживать как изображения «цифровой головоломки», такие как изображение слева, так и изображения головоломок, которые могут иметь некоторый перекос и плохое освещение, как в примере справа.

В итоге я выполнил следующие шаги обработки изображений:

Преобразовать в оттенки серого и изменить размер - Последующие шаги не зависят от цвета и, предполагая постоянный размер, некоторые из последующих этапов обработки упрощаются

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

Эти шаги подготавливают алгоритм обнаружения контуров Canny (документация OpenCV), который дополнительно сокращает информацию в изображении до контуров объектов, таких как сетка, за которой мы следим.

Теперь мы можем использовать алгоритм OpenCV findContours для обнаружения форм на изображении; режим RETR_EXTERNAL используется для ограничения поиска только крайними внешними контурами , пропуская любые, которые лежат внутри других контуров.

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

Эти углы затем используются для «деформации» участка сетки изображения с помощью OpenCV getPerspectiveTransform и warpPerspective .Хотя в «цифровой головоломке» мало что изменилось, теперь наша газетная фотография и изображение «цифровой головоломки» находятся в более равном положении для последующей обработки.

Устранение линий сетки - Прежде чем искать области цифр изображения, полезно избавиться от линий сетки. Элемент структурирования (я использовал горизонтальное и вертикальное ядра размером 1 пиксель) передается на erode и dilate , чтобы очистить линии сетки. findContours снова используется, но на этот раз контуры фильтруются по соотношению сторон только до тех, которые приблизительно соответствуют горизонтальным и вертикальным линиям.

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

Поиск цифр - Наконец, пришло время обнаружить области цифр на изображении.Снова используется findContours , за которым следует другой фильтр соотношения сторон, вдохновленный статьей моего друга Кевина Казмерчака. Этот фильтр позволяет пропустить контуры некоторых горизонтальных артефактов, оставшихся на изображении газеты справа.

Машинное обучение с OpenCV

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

Затем каждое изображение образца было пропущено через логику «синтаксического анализа», описанную ранее, чтобы найти области цифр.Центр каждой области цифр был сопоставлен с ближайшей центральной точкой сетки 9x9, наложенной на изображение, а затем присвоено цифровое значение на основе данных в файле .csv. Затем каждая цифра была изменена до согласованного размера и объединена в общее «обучающее» изображение, где верхняя строка содержит все изображения «1», вторая строка содержит все изображения «2» и т. Д. Это становится нашими необработанными данными для обучения модель машинного обучения.

Существует множество руководств по распознаванию цифр, но я нашел, что Сатья Маллик особенно ценен благодаря ясному и подробному объяснению.Я адаптировал его подход к этому проекту. Чтобы быстро подвести итог, дескриптор гистограммы градиентов (см. Также замечательное объяснение дескриптора HOG Сатья Сатьей) вычисляется для каждой цифры изображения. 80% этих дескрипторов вместе с цифровой меткой (выведенной из строки в нашем обучающем изображении) затем передаются в качестве наших «наблюдений» в класс OpenCV SVM для обучения модели. Затем обученная модель SVM используется для прогнозирования соответствующей цифры для оставшихся 20% цифр.

Я создал небольшой инструмент C ++ CLI для запуска процесса обучения и в итоге получил 97.73% точности на , хотя и ограниченный набор образцов головоломок , который я собрал. Обученная модель SVM сохраняется и загружается позже для использования при решении новых головоломок.

OpenCV 3.x Интеграция C ++ с Go через CGO

Вся работа до сих пор была сделана с C ++ (, если вы посмотрите на , код будьте осторожны, я новичок в C ++ на момент написания этой статьи ) . Вызвать это из Go оказалось сложнее, чем я ожидал, , а не , простой сценарий для моей первой работы в Go.

cgo позволяет Go вызывать код C, используя специальный комментарий, называемый преамбулой к конкретному импорту пакета «C» (этот импорт должен быть в отдельной строке), как это. Обратите внимание, что преамбула поддерживает значения, зависящие от платформы, для поддержки кросс-компиляции безопасной кодовой базы на разных платформах, например. darwin (моя локальная установка) и linux (контейнер докеров, созданный для запуска этого приложения).

Цитата из документации (выделено мной):

Когда инструмент Go обнаруживает, что один или несколько файлов Go используют специальный импорт «C», он будет искать другие файлы , отличные от Go, в каталоге и компилировать их как часть пакета Go.Любые файлы .c, .s или .S будут скомпилированы компилятором C. Любые файлы .cc, .cpp или .cxx будут скомпилированы с помощью компилятора C ++ .

Это казалось достаточно простым, но я потерял время из-за пары моментов, которые я подчеркнул выше:

• CGO позвольте вам вызывать код C (а не код C ++) - Так в чем же дело с упоминанием .cpp файлов компилируются с помощью компилятора C ++? Что ж, как новичку в C / C ++ мне потребовалось некоторое время, чтобы понять, что cgo будет компилировать C ++, на который ссылается из импортируемого кода C .Однако вы не можете напрямую импортировать код C ++, что означает, что типы C ++, такие как string и vector , должны быть преобразованы в их эквивалентные типы C.
• CGO компилирует файлы ТОЛЬКО в одном каталоге. - Мой исходный код разбора головоломки C ++ Sudoku был организован в каталоги src / и include /, а моя преамбула cgo пыталась включить заголовок C из подкаталога. Это не сработало.

В итоге я получил следующую структуру каталогов, чтобы получить cgo , правильно компилирующий и связывающий мой код C ++ OpenCV с импортированным пакетом «C»

Было еще несколько заметных ошибок:

• Отладка с CGO - Delve, отладчик Go потрясающий.Однако я не смог заставить его работать, когда начал использовать cgo . Я не мог сказать, действительно ли он поддерживался, или у меня просто были проблемы. Мне было проще запускать и отлаживать код C ++ отдельно
• Watch Your Pointers! - Раньше я возвращал строку из C ++, которая представляла «проанализированную» головоломку судоку и периодически получал странные результаты мусора. Я закончил тем, что заранее выделил память C и передал указатели в код C, позволяя ему читать / писать из этой выделенной памяти.Go defer и C.free () гарантируют, что мы освободим его, когда мы закончим. См. Пример ниже.

Результатом этого вызова является просто строка из 81 символа, идентифицирующая цифры, которые были обнаружены на изображении:

Решение головоломки судоку

Рассмотрение того, как решить головоломку судоку, учитывая, что цифры , а не , являются основным фокусом этой статьи; Если это то, что вам нужно, ознакомьтесь с подходом и объяснениями Питера Норвига. Тем не менее, я просто отмечу, что основной метод - это распространение ограничений, когда мы, по сути, используем ограничения в проблемной области, чтобы ограничить количество вариантов поиска.Если мы наивно представим себе доску судоку как сетку 9x9, в которой каждая ячейка может принимать значение от 1 до 9, то мы имеем 9⁸¹ возможных состояний доски (более 3 миллиардов). Конечно, мы знаем, что существует множество ограничений, которые ограничивают пространство поиска:

• Известные начальные цифры
• Каждая строка должна содержать все цифры 1–9
• Каждый столбец должен содержать все цифры 1–9
• и т. Д.

Применяя эти ограничения, мы можем резко сократить возможное пространство поиска.Как только ограничение применяется для сужения пространства поиска, мы можем повторно оценить другие ограничения, чтобы итеративно сузить допустимые значения для каждой ячейки в головоломке. В сочетании с алгоритмом поиска для случаев, когда ограничения не исключают всех возможностей, большинство головоломок можно решить за несколько секунд или меньше. Посетите sudokuboard.go , чтобы узнать о реализации Go, использованной в этом проекте.

В дополнение к коду решения судоку, часть проекта Go содержит некоторый ничем не примечательный код для обслуживания статического каталога веб-контента, в котором находится пользовательский интерфейс проекта, и принятия многостраничной загрузки файлов, в которую отправляются изображения головоломок судоку.Он также использует обработчик NY Times Gzip для сжатия ответов.

Развертывание Docker

Итак, у нас есть код OpenCV для «синтаксического анализа» изображения головоломки (переданного в виде массива байтов), мы интегрировали его с простым веб-приложением Go, которое принимает изображение головоломки, передает его off для анализа OpenCV, а затем решает недостающие цифры. Большой! Но где его развернуть?

Зависимость от OpenCV означает, что у нас нет автономного двоичного файла, и исключает что-то вроде стандартной среды Go на облачной платформе Google.Следующим логичным выбором было контейнерное решение, поэтому отказался от DockerHub…

Go image? ✔

Изображение OpenCV? Их много!

Перейти и OpenCV 3.x? ☹

… так что я собрал свой первый вклад в DockerHub, образ на базе Alpine Linux с библиотеками Go 1.8.3 и OpenCV 3, которые, к счастью, доступны в Alpine Linux Edge. Здесь было несколько трудностей, таких как настройка символических ссылок на библиотеки opencv, зависящие от версии, но в конечном итоге этот контейнер, а также специфическая для платформы преамбула cgo , замеченная ранее, позволили мне успешно создать приложение внутри контейнера докеров.

Прочитав статью Келси Хайтауэр о крошечных контейнерах Docker для приложений Go, я осознал, что, хотя я могу запускать свое приложение из этого образа, оно будет раздуто, потому что все инструменты Go все еще присутствуют. К счастью для меня, команда Docker добавила многоэтапные сборки в Docker 17.05 с тех пор, как Келси написал свою статью, и теперь в единственном файле Dockerfile я могу собрать приложение, удалить образ сборки с помощью инструментов SDK и т. Д. и скопировать Перейдите с предыдущего этапа в двоичный код к чистому, более легкому изображению! Отличная работа, команда Docker!

Спасибо ребятам из Hyper.sh за предоставление бесплатного уровня для чрезвычайно простого размещения контейнера докеров.

Заключение

Если вы так долго продержались… спасибо! Надеюсь, для вас было что-то ценное. Решатель ни в коем случае не надежен; у него все еще есть проблемы с некоторыми изображениями, и он либо не сможет их проанализировать, либо проанализирует их неправильно, что приведет к невозможности их решения (потому что он мог быть проанализирован как недопустимая головоломка). Целью, конечно же, было развитие некоторых новых технологий, и с этой точки зрения проект был ценным.

Решатель находится в рабочем состоянии (на момент написания этой статьи) на http://gosudoku.jander.me/, а исходный код находится на GitHub, если вам интересно. Напишите мне, если сочтете это полезным или у вас возникнут дополнительные вопросы. Спасибо!

Связанные

Теги