Поиск символов в строке, которые встречаются только один раз

Question

Я пишу алгоритм на PHP для решения заданной головоломки Судоку. Я установил несколько объектно-ориентированную реализацию с двумя классами: класс Square для каждой отдельной плитки на плате 9x9 и класс 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 единиц.

Answer 1

Это похоже на то, что вы уже исключили как «крайне неэффективное», но со встроенными функциями, поэтому оно может быть весьма эффективным:

$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"

Answer 2

Попробуйте вместо этого использовать двоичное число для представления своих «возможных», поскольку бинарные операции, такие как AND, OR, XOR, имеют тенденцию быть намного быстрее строковых операций.

например. если «2» и «3» возможны для квадрата, используйте двоичное число 000000110, чтобы представить возможности для этого квадрата.

Вот как можно найти уникальных персонажей:

$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
}

Я не уверен, будет ли этот метод работать быстрее, но его стоит рассмотреть.

Answer 3

Вот способ использования только встроенных функций PHP, который должен быть довольно быстрым.

function getUniques($sNumbers)
{
    return join(array_keys(array_count_values(str_split($sNumbers)),1));
}

echo getUniques("1234567891234"); // return 56789;

Answer 4

То, что я хотел бы сделать, - это использовать двоичные биты для хранения фактических значений, как предложил другой ответ. Это позволяет проводить эффективные проверки и в целом может дать самой Судоку более математическое (= эффективное и более короткое) решение (только мое впечатление, я не исследовал это).

По сути, вы представляете числа в квадратах не цифрами, а степенями 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

теперь в $ возможных вариантах содержится «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

Answer 5

В последний раз, когда я дурачилась с решением Судоку, у меня был третий класс под названием «Бег». Экземпляр Run создается для каждой строки, столбца и квадрата 3x3. С каждым квадратом связано три трассы. Класс Run содержит набор чисел, еще не помещенных в цикл. Затем решение доски включает в себя итеративное пересечение множеств на каждом квадрате. Это касается 80% большинства средних плат и 60% большинства жестких досок. После того, как вы прошли всю доску без изменений, вы можете перейти к логике более высокого уровня. Каждый раз, когда ваша логика более высокого уровня заполняет квадрат, вы снова пробегаете свои квадраты.

Приятно, что в этой настройке вы можете легко добавлять варианты в солвер. Допустим, вы используете вариант, в котором две диагонали также уникальны. Вы просто добавляете 4-й проход к этим 18 клеткам.

Answer 6

 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;

 }

Это даст тебе каждый синглтон. Получите первую и последнюю позиции числа в этом массиве, и если они совпадают и не являются ЛОЖНЫМИ (строгое сравнение в случае, если в начале есть синглтон), то в этом массиве есть только одно такое число.

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

 $istr = str($i);
 if ( ($first = strpos($instring, $istr)) !== FALSE 
       and $first == $strrpos($instring, $istr) ) $results[] = $i;

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