Генератор Судоку (v. 2.x.x).

Описание

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

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

Версии

2.4.1 — к имени каждой переменной добавлен суффикс sudoku.
2.4.2 - добавлена подпрограмма переадресовки по имеющемуся адресу для блоков ('ffa'). Так же умеет вычислять координату блока.
2.5.0 — Подкорректированы два алгоритма, дублирующие некоторые другие алгоритмы. Исключены подпрограммы del_element7 и del_countnum. Добавлена подпрограмма kill_all, предназначенная для избавления от всех переменных, задействованных в игре, что позволяет собирать судоку в виде модуля и добавлять к любой игре.
2.5.1 – Исправлена ошибка в работе алгоритма prove_dcount (проверялось условие, выполнение которого заведомо невозможно). Почищен код. Исключена подпрограмма prove_element, дублирующая подпрограмму prove_anum.
2.5.2 – Добавлена функция очистки ячейки.

Локации

Основные

sudoku – локация самой игры. При сборке модуля эта локация может быть исключена. Здесь она является примерной локацией для Вашей игры.
На этой локации обязательно должна быть выставлена переменная usehtml=1

step1 – шаг первый. Генерация трёх случайных блоков, заполненных случайным образом. Эта подпрограмма всегда вызывается первой. Она заполняет три блока матрицы из восьмидесяти одного элемента числами по правилам судоку:

step2 – шаг второй (условно). Находит элемент с наименьшим возможным количеством вариантов заполнения. Выбирает среди имеющихся вариантов случайным образом один и прописывает этот вариант элементу.

step3 – шаг третий. Заполняет все элементы матрицы через шаг второй. Заполнение ведётся до тех пор, пока numbercount_sudoku не окажется равной нулю.

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

step5 – шаг пятый. Формирует задачу со скрытием заданного количества случайных элементов.

step6 – шаг пятый. Формирует задачу с единственно возможным вариантом решения (около 40 скрываемых элементов).

step7 – шаг пятый. Формирует задачу, похожую на задачу, составленную человеком (порядка пятидесяти скрываемых элементов).

Вспомогательные

full_block – заполняет блок с координатами первого элемента args[0] – args[1] (x_sudoku – y_sudoku) случайным образом.

full_anum – заполняет массив с именем $args[0] текстовыми значениями от '0' до '8'

full_countnum – заполняет массивы $countnum_sudoku_N значениями от '0' до '8', где N – порядковый номер элемента в матрице (0...80), вычисляемый по координатам x – y.

full_countnum_adr – заполняет массив $sountnum_sudoku[N] строковыми значениями вида 'x_sudoku=<<x_sudoku>> & y_sudoku=<<y_sudoku>>', где N – порядковый номер элемента в матрице (0...80), вычисляемый по координатам x_sudoku – y_sudoku.

full_count – заполняет массивы $count_raw_J $count_col_J $count_block_J значениями от '0' до '8', где J – порядковый номер строки, столбца или блока (соответственно) в матрице.

full_menu – заполняет массив $menu_sudoku – конструкциями меню вида 'действие:локация действия'.

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

print_link – выводит в окно основного описания все возможные значения элемента, т. е. массив $countnum_sudoku_N. Необязательная локация.

print_exit – выводит в окно основного описания получившуюся задачу судоку.

print_count – выводит в окно дополнительного описания размеры массивов $countnum_sudoku_N. Необязательная локация.

del_countnum_b – подпрограмма удаления из массивов $countnum_sudoku_N значений элементов, которые в них больше не могут использоваться.

del_element_raw, del_element_col, del_element_block – удаляет из массивов $count_raw_J $count_col_J $count_block_J значение удаленного из матрицы элемента.

del_element – удаляет из массива $dublnum_sudoku элемент с координатами args[1] args[2] (x_sudoku – y_sudoku) и со значением $args[0]. Добавляет в массив $countnum_sudoku_N элемент со значением $args[0], из массива $countnum_sudoku удаляет элемент со значением 'x_sudoku=<<args[1]>> & y_sudoku=<<args[2]>>'. При обращении с локаций del_element_raw, del_element_col, del_element_block непосредственно удаляет из массивов $count_raw_J $count_col_J $count_block_J значение удаленного элемента.

kill_countnum – удаляет все массивы $countnum_sudoku_N.

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

s0 ... s8 – локации, отвечающие за работу контекстного меню в игре.

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

prove_anum7 – практически то же самое, что prove_anum, только алгоритм попроще и в результате выдается маркер перехода.

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

prove_fast – простая проверка на то, есть ли в строке, столбце или блоке ещё удалённые элементы.

prove_place и prove_dcount – сложно вспомнить, что это за проверки, однако в результате этих проверок заполняется массив $dcount_N значениями, которые у этого элемента не могут быть.

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

Переменные:

Sudoku

USEHTML – выставляется равной единице для корректного отображения судоку на экране.

action_sudoku – в зависимости от состояния этой переменной при обращении к локации выводится тот или иной набор действий.

Step1

i_sudoku – используется как счётчик циклов

n_sudoku – используется, как счётчик цикла, отсчитывающий количество (3) незаполненных случайных блоков.

$block_sudoku – массив, содержащий все номера блоков, которые можно заполнить.

z_sudoku – этой переменной возвращается номер случайного элемента массива $block_sudoku.

b_sudoku и a_sudoku – координаты блока среди остальных блоков. Вертикальный и горизонтальный координат соответственно.

x_sudoku и y_sudoku – матричные координаты первого (верхний левый) элемента блока.

Step2

z_sudoku – наименьшее найденное значение (под значением подразумевается количество возможных вариантов решений для элемента). Изначально выставляется 9, т. е. 9 возможных вариантов решения.

s_sudoku и t_sudoku – матричные координаты элемента по горизонтали и вертикали соответственно.

zx_sudoku и zy_sudoku – матричные координаты элемента значение которого меньше z_sudoku.

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

gump_sudoku – если равна единице, значит, выброшенное значение элемента не является одним из возможных значений этого элемента. Маркер

zz_sudoku – случайный элемент массива $countnum_sudoku_N (иными словами одно из значений элемента матрицы).

$countnum_sudoku_<<zx_sudoku+zy_sudoku*9>> - массив возможных значений элемента матрицы с координатами zx_sudoku — zy_sudoku.

$znumber_sudoku – временно хранит выброшенное значение элемента матрицы.

$num_sudoku[zx_sudoku+zy_sudoku*9] – элемент массива $num_sudoku, хранящий текущее значение элемента матрицы с координатами zx_sudoku — zy_sudoku.

Step3

numbercount_sudoku – подсчитывает количество заполненных элементов

step4

j_sudoku и i_sudoku – матричные координаты элемента $num_sudoku[], счётчики циклов.

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

$num_sudoku — массив, содержащий значения всех элементов получившейся матрицы судоку.

$marker_sudoku_p — если элемент оказывается незаполненным, в ячейку этого массива (номер ячейки соответствует номеру ячейки в массиве $num_sudoku) записывается слово «error».

$marker_sudoku_raw – если значения двух (или более) элементов в строке оказываются одинаковыми, в ячейку (индексируются по номеру строк) данного массива вписывается слово «error».

$marker_sudoku_col и $marker_sudoku_block – то же, что и$marker_sudoku_raw только для столбцов и блоков.

z_sudoku – временно хранит позицию проверяемого на совпадения в $anum_sudoku элемента.

a_sudoku – счётчик цикла, номер проверяемого блока.

q_sudoku и w_sudoku – границы координат, в пределах которых нужно производить проверку при переборе элементов блока.

Step5

numbercount_sudoku – количество скрываемых элементов. Можно задавать от 25 до 50. Чем больше скрыто элементов, тем меньше вероятность, что у судоку будет только одно решение.

z_sudoku – случайное число от 0 до 80. Этой переменной возвращается номер скрываемого элемента.

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

$restore_num – хранит получившуюся задачу судоку для возможности сброса.

$zanum_sudoku – хранит все значения элементов матрицы, присвоенные до получения задачи.

Step6

numbercount_sudoku – количество обрабатываемых элементов. Счётчик цикла.

$restore_num – хранит получившуюся задачу судоку для возможности сброса.

$zanum_sudoku – хранит все значения элементов матрицы, присвоенные до получения задачи.

$dublnum_sudoku – хранит временное состояние задачи. Если полученная задача проходит проверку, она копируется в $num_sudoku, если не проходит, $dublnum_sudoku возвращается вид из предыдущего шага.

$countnum_sudoku[] - массив, в котором хранятся строки вида 'x_sudoku=<<x_sudoku>> & y_sudoku=<<y_sudoku>>', из которых производится восстановление адреса элемента.

$inum_sudoku – временно хранит значение выбранного в массиве $dublnum_sudoku элемента матрицы.

x_sudoku и y_sudoku – соответственно горизонтальные и вертикальные матричные координаты элемента. Вычисляются из значения ячейки $countnum_sudoku[].

hiden_sudoku – счётчик корректно скрытых элементов матрицы.

Step7

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

numbercount_sudoku – количество обрабатываемых элементов. Счётчик цикла.

$restore_num – хранит получившуюся задачу судоку для возможности сброса.

$zanum_sudoku – хранит все значения элементов матрицы, присвоенные до получения задачи.

$count_raw_N - хранит оставшиеся значения элементов для строк, то же, но без N для временного хранения данных

$count_col_N - хранит оставшиеся значения элементов для столбцов, то же, но без N для временного хранения данных

$count_block_N - хранит оставшиеся значения элементов для блоков, то же, но без N для временного хранения данных

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

< Назад

Скачать последнюю версию генератора судоку