Эмулятор судоку [ПОСМОТРЕТЬ]

Что эмуляция машинного кода говорит нам о том, как игроки-люди решают судоку, и почему для победы машине не обязательно быть удачливым?

«Я МНОГО играю в судоку и использую всевозможные методы, перескакивая с одного на другое, как того требует головоломка, вместо того, чтобы работать систематически. Было бы интересно, если бы вы могли изложить процесс своего кода на английском языке. Я мог бы попробовать этот метод и посмотреть, бывают ли моменты, когда человеческий разум воспринимает кратчайший путь.».

Судоку — это увлекательная игра, которую нужно разгадывать, и когда человеческий разум находит кратчайший путь — и ему везет — мы знаем, что шанс и удача тоже играют роль. Но всегда ли программный код чувствителен к интуиции: может ли машинному коду повезти — он может заметить что-то важное и применить это — как кратчайший путь?

Алгоритм Sudoku Emulation Engine применяет всевозможные методы — и перескакивает с одного на другой по мере прохождения головоломки. Эти методы закодированы в виде иерархии подпрограмм. Дизайн каждой подпрограммы основывается на внимательном наблюдении за поведением человека-игрока. Каждая подпрограмма предназначена для имитации определенного вида человеческой деятельности.

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

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

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

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

Доска судоку

Доска судоку показывает матрицу из 81 ячейки в сетке 9 х 9. Доска состоит из девяти рядов, девяти столбцов и девяти полей. Эти строки, столбцы и поля называются Блоками.

Обычно исходное состояние действительной доски судоку показывает частично заполненную сетку — обычно не менее 17 ячеек. Каждая из этих ячеек содержит одно целое число в диапазоне 1 2 3 4 5 6 7 8 9. Все остальные ячейки пусты. Это доска — и на каждой доске есть только одно решение.

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

Головоломка решается применением трех правил. Правила применяются одинаково ко всем блокам. Новичку в судоку эти правила могут показаться пугающими, потому что решение судоку требует применения математических знаний. Это не так. Не нужны и арифметические способности. Решение любой игры судоку определяется только дедукцией и исключением. Этот факт делает его идеальным для алгоритмического решения [*].

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

Игрок-человек

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

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

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

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

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

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

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

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

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

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

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

Машинный игрок

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

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

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

Подпрограмма SEE Markup многократно используется для повторного заполнения пустых ячеек и сохранения этих значений на виртуальной доске. Аналогичным образом подпрограммы Fetch Unique Integer и Fetch Hidden Integer повторяются до тех пор, пока флаги поиска и поиска одного целого не перестанут меняться.

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

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

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

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

Процедуры глубокой структуры

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

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

Подпрограммы SEE Single Block Purge и Pair Block Purge ищут и находят пары целых чисел в заполненных ячейках; удалить эти целые числа из всех других заполненных ячеек и обновить виртуальную доску.

Опять же, подпрограмма SEE Markup повторно заполняет пустые ячейки; Подпрограммы Fetch Unique Integer и Fetch Hidden Integer повторяются. Подпрограммы Single Block Purge и Pair Block Purge развернуты повторно.

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

Подпрограмма SEE Triple Block Purge находит целые тройки в заполненных ячейках; удалить эти целые числа из всех других заполненных ячеек и обновить виртуальную доску.

Еще раз, подпрограммы SEE Markup; Подпрограммы Fetch Unique Integer и Fetch Hidden Integer повторяются до повторного развертывания подпрограмм Block Purge. Этот цикл продолжается до тех пор, пока не будут известны все уникальные целые числа. Это условие является решением всех трудных и жестких игр.

SEE применяет различные процедуры много раз, чтобы получить одно целое число и привести к решению. Каждая дополнительная подпрограмма SEE погружается глубже в структуру дизайна доски, чтобы систематически устранять лишние целые числа, пока головоломка не будет решена [**]. В противном случае программа объявляет головоломку недействительной, поскольку в ней содержится встроенная логическая ошибка [***].

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

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

Преподавание и обучение › Обобщенность и эксперимент

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

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

Универсальность кода Sudoku Emulation Engine дает простор для экспериментов с изменением размеров доски — от стандартной матрицы девять раз девять из 81 ячейки — до досок с блоками из шестнадцати символов и 256 ячеек; или двадцать пять символов и 625 ячеек.

Расширенная доска с блоками буквенно-цифровых символов — в диапазоне 0 1 2 3 4 5 6 7 8 9 A B C D E F — сохраняет целостность уникального формата доски Sudoko. На этой доске показаны каждая строка, столбец и поле с 16 ячейками и общим количеством ячеек 256. Это шестнадцатеричная доска.

Код может быть доработан для работы с двадцатью пятью символами. Эта доска также сохраняет целостность формата Судоко и показывает шрифт в верхнем регистре — в диапазоне A B C D E F G H I J K L M N P Q R S T U V W X Y Z без буквы ‘O’. На доске показаны каждая строка, столбец и поле с 25 символами и общим количеством ячеек 625. Это алфавит доска.

Преподавание и обучение › Эмуляция и расширение возможностей

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

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

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

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

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

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

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

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

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

автор: popadog

Эмулятор судоку

[* Ссылка:‘Ключевой стратегией решения судоку является устранение данных, а не опыт принятия решений. Вот как — Опубликовано на платформе Medium 2019].

[** Глубина погружения обеспечивает дополнительный показатель сложности игры. Специально разработанные игры включают в себя две диагонали по девять клеток. SEE не предназначен для решения таких досок.]

[*** Это крайне редко встречается с головоломками в национальных газетах, качественных журналах и большинстве сборников головоломок, но ведутся споры о том, что считается действительной головоломкой судоку — может ли она иметь два или более решений или включать догадку. Дьявольские игры включают двойные или множественные решения и некоторые догадки. Это не действительные доски. Алгоритм SEE решает все допустимые головоломки Судоко, но не включает подпрограмму угадай.]

ТЕГИ›

компьютерный код, обучение, судоку, логика, наделение полномочиями, интуиция, удача, случайность,