Я пишу алгоритм в PHP для решения данной головоломки Sudoku. Я создал объектно-ориентированную реализацию с двумя классами: Square класс для каждой отдельной плитки на доске 9×9 и класс Sudoku , который имеет матрицу Square s для представления платы.
Реализация алгоритма, который я использую, является своего рода тройным уровнем. Первый шаг, который решает только самые основные головоломки (но наиболее эффективные), состоит в том, чтобы заполнить любые квадраты, которые могут принимать только одно значение, основанное на начальной настройке платы, и соответственно корректировать ограничения на оставшуюся часть неразрешенные квадраты.
Обычно этот процесс «постоянного распространения» не полностью решает вопрос, но он решает значительную часть. Второй уровень затем начнется. Это анализирует каждую единицу (или 9 квадратов, каждая из которых должна иметь уникальные присвоения номеров, например строку или столбец) для «возможных» значений каждого неразрешенного квадрата. Этот список возможных значений представлен в виде строки в классе Square :
class Square { private $name; // 00, 01, 02, ... , 86, 87, 88 private $peers; // All squares in same row, col, and box private $number; // Assigned value (0 if not assigned) private $possibles; // String of possible numbers (1-9) public function __construct($name, $p = 0) { $this->name = $name; $this->setNumber($p); if ($p == 0) { $this->possibles = "123456789"; } } // ... other functions
Учитывая целый массив нерешенных квадратов в единице (как описано во втором эшелоне выше), второй уровень объединяет все строки «возможных» в одну строку. Затем он будет искать эту единственную строку для любых уникальных значений символов – значений, которые не повторяются. Это будет означать, что внутри единицы квадратов существует только один квадрат, который может принимать это конкретное значение.
Мой вопрос: для реализации этого второго уровня, как я могу разобрать эту строку из всех возможных значений в единице и легко обнаружить уникальные значения? Я знаю, что могу создать массив, где каждый индекс представлен цифрами 1-9, и я мог бы увеличивать значение в соответствующем индексе на 1 для каждого возможного значения этого числа, которое я нахожу, а затем снова сканировать массив для любого значения 1, но это кажется крайне неэффективным, требующим двух линейных сканирований массива для каждой единицы, а в головоломке Судоку – 27 единиц.
Это похоже на то, что вы уже исключили как «крайне неэффективное», но со встроенными функциями, чтобы оно могло быть достаточно эффективным:
$all_possibilities = "1234567891234"; $unique = array(); foreach (count_chars($all_possibilities, 1) as $c => $occurrences) { if ($occurrences == 1) $unique[] = chr($c); } print join("", $unique) . "\n";
Печать: "56789"
Подумайте о том, как использовать двоичный номер для представления ваших «возможностей», потому что двоичные операции, такие как AND, OR, XOR, как правило, намного быстрее, чем операции с строкой.
Например, если для квадрата возможны «2» и «3», используйте двоичное число 000000110, чтобы представить возможности для этого квадрата.
Вот как вы можете найти uniques:
$seenonce = 0; $seenmore = 0; foreach(all_possibles_for_this_unit as $possibles) { $seenmore |= ($possibles & $seenonce); $seenonce |= $possibles; } $seenonce ^= $seenmore; if ($seenonce) { //something was seen once - now it must be located }
Я не уверен, будет ли этот метод работать быстрее, но стоит посмотреть.
function singletonsInString($instring) { $results = array(); for($i = 1; $i < 10; $i++) { $first_pos = strpos($instring, str($i)); $last_pos = strrpos($instring, str($i)); if ( $first_pos !== FALSE and $first_pos == $last_pos ) $results[] = $i; } return $results; }
Это даст вам каждый синглтон. Получите первую и последнюю позиции числа в этом массиве, и если они совпадают и не совпадают с FALSE (строгое сравнение в случае, если в начале есть одноэлемент), то в этом массиве есть только один такой номер.
Если вы супер супер беспокоятся о скорости здесь, вы, вероятно, можете заменить интерьер этого цикла
$istr = str($i); if ( ($first = strpos($instring, $istr)) !== FALSE and $first == $strrpos($instring, $istr) ) $results[] = $i;
для минимального количества вычислений. Ну, если предположить, что родные strpos PHP – лучший способ обойти эти вещи, которые, насколько я знаю, не являются необоснованными.
В последний раз, когда я обманывал решение Sudoku, у меня был третий класс под названием «Run». Экземпляр Run создается для каждой строки, col и 3×3. Каждый квадрат имеет три пробега, связанных с ним. Класс Run содержит набор чисел, еще не помещенных в ход. Решение решетки тогда включает пересечение множеств на каждом квадрате итеративно. Это касается 80% большинства средних плат и 60% большинства жестких плат. После того, как вы пройдете всю доску без изменений, вы можете перейти к логике более высокого уровня. Каждый раз, когда ваша логика более высокого уровня заполняет квадрат, вы снова запускаете свои квадраты.
Самое приятное в этой настройке – вы можете легко добавить варианты решателю. Скажем, вы используете вариант, где две диагонали также уникальны. Вы просто добавляете 4-й прогон к этим 18 квадратам.
То, что я сделал бы, на самом деле использует двоичные биты для хранения фактических значений в качестве другого предложенного ответа. Это позволяет делать эффективные проверки и вообще может предоставить Судоку самому более математическому (= эффективному и коротким) решению (просто мое впечатление, я не исследовал это).
В принципе, вы представляете числа в квадратах не с цифрами, а с полномочиями 2
"1" = 2^0 = 1 = 000000001 "2" = 2^1 = 2 = 000000010 "3" = 2^2 = 4 = 000000100 "4" = 2^3 = 8 = 000001000 ... etc up to "9" = 2^8 = 256= 100000000
таким образом, вы можете просто добавить содержимое «одиночных квадратов», чтобы узнать, какие числа отсутствуют в 3×3 или строке или любом другом поднаборе судоку, например:
// shows the possibles for 3x3 square number 1 (00-22) $sum=0; for ($i=0; $i< 3; $i++) for ($j=0; $j < 3; $j++) $sum += $square["${i}${j}"]->number $possibles = $sum ^ 511 // ^ stands for bitwise XOR and 511 is binary 11111111
теперь $ possibles содержит «1» в битовых позициях цифр, которые возможны в этом квадрате, и вы можете выполнять побитовые операции с результатами для других квадратов, чтобы их совместить, например:
например. скажем:
$possibles1 = 146 // is binary 100100101, //indicating that this row or 3x3 square has place for "9", "6", "3" and "1" $possibles2 = 7 // is binary 000000111, indicating it has place for "3", "2" and "1". // so: $possibles1 & $possibles2 // bitwise AND, will show binary 101 saying that "3" and "1" is unfilled in both bloces $possibles1 | $possibles2 // bitwise OR will give that in total it is possible to use "9", "6", "3", "2" and "1" in those two squares together
Вот способ использования только встроенных функций PHP, которые должны быть довольно быстрыми.
function getUniques($sNumbers) { return join(array_keys(array_count_values(str_split($sNumbers)),1)); } echo getUniques("1234567891234"); // return 56789;