查找字符串中只出现一次的字符

Question

我正在用 PHP 编写一个算法来解决给定的数独难题。 我已经设置了一个带有两个类的面向对象的实现：一个用于 9x9 棋盘上每个单独图块的 Square 类，以及一个具有矩阵的 Sudoku 类代表棋盘的方块。

我正在使用的算法的实现是一种三层方法。 第一步，仅解决最基本的难题（但也是最有效的），是根据棋盘的初始设置填充只能取单个值的任何方格，并相应地调整其余部分的约束未解的方块。

通常，这种“不断传播”的过程并不能完全解决棋盘问题，但它确实解决了相当大的问题。 然后第二层将启动。它将解析每个单元（或 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

 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;

最少的计算次数替换该循环的内部。 好吧，假设 PHP 的本机 strpos 是处理这些事情的最佳方法，据我所知，这并非不合理。

Answer 4

上次我愚弄数独解决时，我有第三堂课，名为“跑步”。 为每行、每列和 3x3 正方形创建一个 Run 实例。 每个方格都有与其相关的三个运行。 Run 类包含尚未放入运行中的一组数字。 然后，求解棋盘需要迭代地在每个方格处相交集合。 这可以处理 80% 的大多数中型板和 60% 的大多数硬板。 一旦您完成了整个板且没有任何更改，您就可以继续进行更高级别的逻辑。 每次您的更高级别逻辑填充一个正方形时，您都会再次遍历您的正方形。

此设置的好处是您可以轻松地向求解器添加变体。 假设您使用两个对角线也是唯一的变体。 您只需在这 18 个方格中添加第 4 次游程即可。

Answer 5

我要做的实际上是使用二进制位来存储实际值，正如另一个答案所建议的那样。 这允许进行有效的检查，并且通常可能使数独本身具有更数学（=高效且更短）的解决方案（只是我的印象，我还没有研究过这一点）。

基本上，您不用数字而是用 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

这样，您可以简单地添加单个方格的内容来找出 3x3 或行或数独的任何其他子集中缺少哪些数字，例如这样：

// 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

Answer 6

这是一种仅使用 PHP 内置函数的方法，应该相当快。

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

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