формула объяснения алгоритма судоку
Я реализую решение судоку, используя человеческий алгоритм. Которые имеют 3 ограничения, различное число в строке, ячейке и поле.
Я погуглил и получил http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/. Но я не могу понять, как этот парень получил floor($cell / 9) для функции return_row или floor(return_row($cell) / 3) * 3 + floor(return_col($cell) / 3) для возврата
Я пытаюсь выяснить это, записав данные в Excel, и я знаю, что есть такая схема:
[cell] [column]
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 0
Но как он понял, что формула $cell % 9 ?
Я хочу знать, если я не знаю ответ для формулы, как я могу рассчитать это? Как я могу определить эту формулу? Какой метод я должен использовать?
Спасибо
Решение
Это происходит из-за способа подсчета ячеек, который мы могли бы назвать строкой-мажором.
Вы можете видеть номера блоков и ячеек с соответствующими номерами строк и столбцов на этом изображении:
строки и столбцы
Первая строка (0) содержит ячейки с 0 по 8, ячейки второго ряда с 9 по 17 и так далее до строки 8, которая содержит ячейки с 72 по 80.
Если вы нумеруете строки от 0 до 8 и столбцы от 0 до 8, мы можем видеть, что формула для ячейки, которая соответствует этой нумерации, равна cell = 9 * row + col, который должен объяснить формулы для get_row и get_col.
При перемещении вправо от любой ячейки на один столбец вы добавляете 1 к числу ячеек, что означает, что формула для номера ячейки выглядит следующим образом something + col,
При перемещении вниз на одну строку вы добавляете к числу ячеек количество ячеек на строку, которое здесь равно 9, поэтому формула также выглядит следующим образом: 9 * row + something,
Собрав их вместе, вы получите формулу, которая 9 * row + col + offset : зависимости «+ что-то» — это строки и столбцы, но, возможно, они все еще содержат постоянное значение.
В нашем случае формула дает требуемую нумерацию со смещением = 0, но если бы вы начали нумерацию с 1, вы бы получили формулу 9 * row + col + 1,
Однако вы не должны делать это каждый раз. Просто теперь, когда у вас есть прямоугольник, где вы посчитаете элементы построчно, формула для номера элемента всегда row * row_size + col + number at (0,0), Это также то, как непрерывная память выделяется для двойных массивов в C, например, очень распространенный шаблон. Если вы посчитаете столбец за столбцом, то у вас есть col * col_size + row + number at (0,0)
Блоки
Теперь блоки нумеруются одинаково, но есть только 3 строки и столбца. Вы можете заменить один за другим элементы в формуле get_block, чтобы понять это: floor(row / 3) * 3 + floor(col / 3)
Поскольку имеется 3 ряда блоков, но 9 ячеек, строки (ячейки) 0, 1 и 2 соответствуют первому ряду блоков, 3-5 — второму ряду блоков и 6-8 — последнему и третьему ряду. блоков. Из этого мы получаем, что ряд блоков rb содержит ряды клеток 3 * rb, 3 * rb +1 а также 3 * rb + 2, Противоположной операцией является деление на 3 и пол, который дает вам rb для любого из выражений выше.
Это работает точно так же для столбцов.
Таким образом, при замене в выражении мы теперь имеем: block_row * 3 + block_col, Это я бы точно такую же формулу (с 3 вместо 9), что мы имели для нумерации ячеек, и, таким образом, получает номер блока из его строки и столбца.
Другие решения
Других решений пока нет …