Алгоритм решения судоку.

Игровое поле – квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. Требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

Глобальные переменные.

Эти глобальные переменные доступны всем процедурам и функциям программы.

Нумерация полей.

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

Заполнение массива x[i, j]. где i – номер столбца, а j – номер строки. 0 ? i ? 8; 0 ? j ? 8;

Заполнение двумерного массива m[k, mc[k]].

Для каждого поля, имеющего номер k = x[i, j]. 1?k?81. находящегося в столбцe i и строке j. находятся 20 полей m[k, mc[k]]. где 1? mc[k] ?20. каждое из которых находится в столбцe i0 и строке j0. Каждое из этих 20 полей находится либо в той же самой строке, либо в том же самом столбце, либо в том же самом блоке размера 3x3, что и поле k.

Для этого в цикле, где i меняется от 1 до 8, j меняется от 0 до 8, i0 меняется от 0 до 8, j0 меняется от 0 до 8, для двух номеров полей x[i, j] и x[i0, j0]. если их номера столбцов совпадают, и при этом их номера строк не совпадают; или их номера строк совадают, и при этом их номера столбцов не совпадают; или их номера стобцов не совпадают, и их номера строк не совпадают, и при этом они принадлежат одной и той же ячейке размера 3x3, что означает равноство целочисленного делания на 3 номера строки и номера столбца, то mc[x[i, j]] увеличивается на единицу, а x[i0, j0] записывается в массив m[x[i, j], mc[x[i, j]]. соостветствующее номеру k=x[i, j]. В конце этой процедуры для любого k. 1?k?81. все значения mc[k]=20. и для каждого поля k, 1?k?81. будет найдено 20 полей m[k,L], 1?L?20. для которых либо номер столбца m[k, L] совпадает с номером столбца поля k. а номер строки m[k,L] не совпадает с номером строки поля k ; либо номер строки m[k,L] совпадает с номером строки поля k. а номер столбца m[k,L] не совпадает с номером столбца поля k ; либо номер столбца m[k,L] не совпадает с номером столбца поля k. номер строки m[k,L] не совпадает с номером строки поля k. а частное от целосчиленного деления на 3 номера столбца m[k,L] совпадает с частным от целочисленного деления на 3 номера стоблца k. и частное от целосчиленного деления на 3 номера строки m[k,L] совпадает с частным от целочисленного деления на 3 номера строки k.

Ввод исходных данных. Заполнение глобальных массивов z[k, 0], s[k], p[k], 1?k?81

В ячейке z[k,0] будет храниться исходная задача. Если поле c номером k пустое, то в z[k,0] записывается нуль, а если в этом поле есть цифра, то в z[k,0] записывается эта цифра. Затем элементам массива s[k] присваивается значение z[k,0] .

Логический массив p[k] заполняется следующим образом: если поле c номером k пустое, то p[k] присваивается значение false. а если оно не пустое, то p[k] присваивается значение true. В следующих рекурсивных функциях значение s[k] не будет меняться для тех полей, для которых p[k]=true .

Если выбрана опция «Перебор всех цифр», то значение переменной frugal присваиваеися значение 0. Если выбрана опция «Поиск одиночек», то переменной frugal присваивается значение 1. Если выбрана опция «Поиск скрытых одиночек», то переменной frugal присваивается значение 2 .

Проверка судоку на наличие ошибок.

Функция control проверяет, нет ли двух одинаковых цифр, отличных от нуля, в строке, столбце или блоке 3x3. Если таких цифр нет, то значение функции true. а если в какой либо строке, столбце или блоке 3x3 найдeтся две одинаковые цифры, то значение функции равно false .

Присваивается значение локальной переменной q := true ; для всех полей k с номерами от 1 до 81, и для всех mc[k]=20 полей, находящихся с полем k в том же столбце или в той же строке или в том же блоке 3x3, если цифры совпадают и отличны от нуля, то q := false. Функции control присваивается значение локальной переменной q .

Рекурсивная процедура неэкономного решения судоку.

Процедура rec(k, g) вызывается тогда, когда флажок «Экономно» на форме снят. Рекурсивная процедура rec(k, g) ставит в поле с номером k цифру t. которой нет ни в в одном из 20 полей, имеющих с полем k либо тот же самый номер столбца, либо тот же самый номер строки, либо тот же самый блок размером 3x3. Процедура имеет два параметра. Параметр k – это номер поля, в который ставится цифра. Параметр g – это количество решений, которые надо найти.

Если в начале поле с номером k было непустым, то цифра, стоящая в нём, не может быть изменена, p[k] = true. В этом случае происходит переход к следующему полю с номером k+1. то есть происходит вызов рекурсивной процедуры с параметрамиrec(k+1, g) .

Если в начале поле с номером k было пустым, то есть p[k] = false. то для поля с номером k ищется какая либо цифра от 1 до 9, которой нет в 20 полях, имеющих с полем k либо тот же самый номер столбца, либо тот же самый номер строки, либо тот же самый блок размером 3x3. Если найдётся такая цифра t. то она ставится в поле с номером k. то есть s[k] присваивается значение t ; число ходов c увеличивается на единицу; после этого происходит переход к следующему полю с номером k+1. то есть происходит вызов рекурсивной процедуры rec(k+1, g). Если все 9 цифр перебраны, и ни одну цифру нельзя поставить в поле k. так как каждая цифра стоит хотя бы в одном из 20 полей, имеющих с полем k либо тот же самый номер столбца, либо тот же самый номер строки, либо тот же самый блок размером 3x3, то в поле с номером k ставится 0. то есть s[k] присваивается нулевое значение. Этот процес продолжается до тех пор, пока номер поля не провосходит количества полей то есть k?81. пока количество найденных решений u меньше заданного в качетсве второго параметра процедуры значения g. и пока польозватель не нажмёт кнопку «Стоп».

Как только будет вызвана процедура rec(k, g) с номером k=82. превышающим количество полей, количество решений u увеличивается на единицу, в массив z[k, u] записывается решение s[k]. то есть для всех полей с номером k от 1 до 81 элементу массива z[k, u] присваивается значение s[k] .

На решение судоку уходит иногда до 5 секунд. Но если судоку решений не имеет, и при этом снят флажок «Экономно», то поиск решения неэкономным методом перебора может продолжаться очень много часов, и поэтому активирована кнопка «Стоп» Процедура Application.ProcessMessages; в Лазарусе предотвращает зависание программы.

Подготовка к экономному решению судоку.

Процедура possible для каждого поля с номером k определяет, какое число w[k] возможных цифр может быть поставлено в каждое такое поле с номером k. и записывает все эти цифры в массив b[k, j]. где второй индекс j пробегает значения от 1 до w[k] .

Если для какого то поля с номером k значение w[k]=0. то эта судоку не имеет решений, локальной переменной det присваивается значение false. Если для какого то поля с номером k значение w[k]=1. то в это поле с номером k ставится данная единственно возможная цифра, то есть значению s[k] присваивается значение b[k, 1]. после чего функция ingress повторно проверяет все поля с номерами k от 1 до 81 (переменной rep присваивается значение true ). Цикл звершается тогда, когда либо для какого-то поля k количество возможных цифр оказалось нулевым, то есть w[k] = 0. и судоку решений не имеет; либо когда для всех полей с номерами k от 1 до 81 значение w[k]>1 (при этом значение переменной rep равно false ).

Процедура possible. таким образом, находит всех кандидатов для каждой пустой ячейки c номером k. записывает их в массив b[k, j]. а количество этих кандидатов записывает в массив w[k]. После этого в таблице отыскиваются всен одиночки, т.е. ячейки, в которых возможна только одна цифра и никакая другая, то есть находятсмя все такие ячейки, для которых w[k]=1. В эти ячейки записывается данный единственный кандидат b[k, 1] .

Поиск скрытых одиночек.

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

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

В начале ищутся «скрытые одиночки», равные цифре t в каждом блоке с номером от 0 до 8, где номер блока равен li+3*lj. а li – частное от целочисленного деления на 3 номера столбца i. а lj – частное от целочисленного деления на 3 номера строки j .

Массив onel[li+3*lj, t] будет содержать количество кандидатов, равных цифре t и содержащихся в блоке с номером li+3*lj .

Если для какого-то блока onel[li+3*lj, t] = 1. то находится ячейка, стоящая в столбце с номером i и в строке с номерм j. в которой есть цифра t. и если эта ячейка пустая, то в неё записывается цифра t. а счётчик cp записанных предварительно цифр увеличивается на 1.

После этого проверяется, нет ли среди девяти блоков с номероами от 0 до 8 такого блока с номером onel[li+3*lj, t]. для которого для какой-то цифры t значение onel[li+3*lj, t] = 0. Если такой блок найдётся, то судоку решений не имеет, переменной det присваивается значение false. управление передаётся на метку ending. и функция завершает работу с результатом false

После этого ищутся «скрытые одиночки», равные цифре t в каждом столбце i с номером от 0 до 8. Массив onei[i, t] будет содержать количество кандидатов, равных цифре t и содержащихся в столбце с номером i .

Если для какого-то столбца с номером i значение onei[i, t] = 1. то находится ячейка, находящаяся в строке с номером j. в которой есть цифра t. и если эта ячейка пустая, то в неё записывается цифра t. а счётчик cp записанных предварительно цифр увеличивается на 1.

После этого проверяется, нет ли среди девяти столбцов с номероами от 0 до 8 такого столбца с номером i. для которого для какой-то цифры t значение onei[i, t] = 0. Если такой столбец найдётся, то судоку решений не имеет, переменной det присваивается значение false. управление передаётся на метку ending. и функция завершает работу с результатом false

После этого ищутся «скрытые одиночки», равные цифре t в каждой строке j с номером от 0 до 8. Массив onej[j, t] будет содержать количество кандидатов, равных цифре t и содержащихся в строке с номером j .

Если для какой-то строки с номером j значение onej[j, t] = 1. то находится ячейка, находящаяся в столбце с номером ш. в которой есть цифра t. и если эта ячейка пустая, то в неё записывается цифра t. а счётчик cp записанных предварительно цифр увеличивается на 1.

После этого проверяется, нет ли среди девяти строк с номероами от 0 до 8 такой строки с номером j. для которой для какой-то цифры t значение onej[j, t] = 0. Если такая строка найдётся, то судоку решений не имеет, переменной det присваивается значение false. управление передаётся на метку ending. и функция завершает работу с результатом false

после всякой записи в пустую ячейку цифры переменной rep присваивается значение true. что означает то, что цикл будет повторен, будет неайдены сначала все кандидаты для каждой ячейки при помощи процедуры possible, при помощи той же процедуры possible ищутся и записываются в пустые ячейки « одиночки», а затем ищутся «скрытые одиночки» функцией ingress. Цикл завершится либо тогда, когда не останется «скрытых одиночек», либо тогда, когда найдётся блок или строка или столбец, в которые нельзя поставить какую-то из девяти цифр.

Рекурсивная процедура экономного решения судоку.

Рекурсивная процедура экономного решения судоку recfrugal(k, g) работает точно так же, как процедура неэкономного решения судоку rec(k, g). но только для каждого поля перебираются не все цифры от 1 до 9, а только возможные для каждого поля цифры из массива b[k, j]. где j = w[k] больше 1.


Вывод решения с номером d на экран.


Нахождение всех решений судоку.

Может быть утсновлена одна из трёх опций «Поиск скрытых одиночек» (frugal = 2 ), или «Поиск одиночек» (frugal = 1 ), или «Перебор всех цифр» (frugal = 0 ).

Если frugal = 0. то рекурсивной функцией rec(k, g) перебираются все цифры для каждой свободной ячейки, для которой p[k]=true .

Если frugal = 1. то сначала вычисляются и записываются в массив b[k, t] все возможные кандидаты для каждой свободной ячейки c номером k. а количество возможных кандидатов записывается в массив w[k]. После этого в те ячейки, для которых существует единственый кандидат, то есть в такие ячейки, для которых w[k] =1. записывается этот кандидат. Описанные действия осуществляет функция possible(). После того, как не отсанется ни одной «одиночки», для каждой свободной ячейки рекурсивной функцией recfrugal(k, g) перебираются оставшиеся кандидаты.

Если frugal = 2. то после поиска «одиночек» функцией possible() ищутся «скрытые одиночки» функцией ingress(). то есть ищутся ячейки, в которых стоит несколько кандидатов, но один из кандидатов не встречается больше ни в одной другой ячейке данного блока или столбца или строки. Этот кандидидат записывается в соответствующую ячейку. После того, как не отсанется ни одной «скрытой одиночки», для каждой свободной ячейки рекурсивной функцией recfrugal(k, g) перебираются оставшиеся кандидаты.


0), то ; > Если (control() = false), то вывести сообщение 'Судоку неверная'; >; " height=1051 width=809>


Запись решения в файл.

Поиск скрытых одиночек

Заданная Судоку

телефоны +79203451544, +79106942514

Вывод на экран следующего решения судоку.

Если судоку имеет более одного решения, то есть u > 1. то активизируется кнопка «>>», с которой связана процедура ButtonNextSolutionClick(). которая увеличивает значение disp на единицу, если disp < u, и присваивает disp значение 1, если disp = u. После этого решение с номером disp выводится на экран.

Вывод на экран предыдущего решения судоку.

Если судоку имеет более одного решения, то есть u > 1. то активизируется кнопка «<<», с которой связана процедура ButtonBeforeSolutionClick(). которая уменьшает значение disp на единицу, если disp > 1, и присваивает disp значение u. если disp = 1. После этого решение с номером disp выводится на экран.

Два алгоритма генерации судоку с заданным числом решений.

Случайная перестановка из 9 цифр.

Данная процедура randomingnumber() переставляет 9 цифр в случайном порядке и записывает их в глобальный массив y[t] .


Случайная перестановка из 81 поля.

Данная процедура randomfield() переставляет 81 цифр в случайном порядке и записывает их в глобальный массив r[k]. В алгоритме №1 поиска решаемой судоку массив r[k] будет служить для случайной выборки h полей из 81 поля, а в алгоритме №2 поиска судоку первые h полей будут заполняться в порядке, который записан в массиве r[k]

Количество решений судоку.

Данная функция rank(g) имеет параметр g. равный заданному количеству решений. Она берёт данные из глобального массива gen[k]. пытается найти количество решений на единицу больше заданного g сответствующей судоку с цифрами в полях s[k]=gen[k] и записывает в глобальную переменную u количество решений этой судоку.


Алгоритм поиска решаемой судоку. Алгоритм №1.

Случайная выборка из всех решений пустой судоку.

Алгоритм поиска судоку. Алгоритм №2.

Рекомендуем ознакомится: http://ateist.spb.ru