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

我正在用PHP写一个算法来解决给定的数独谜题。我已经设置了一个稍微面向对象的实现至少两个类：一个Square类用于在9x9的板上的每个个体瓦片和Sudoku类，其具有Square秒的矩阵来表示板。在只出现一次的字符串中查找字符

我使用的算法的实现是一种三层次的办法。第一步只能解决最基本的谜题（但效率最高），其方法是根据棋盘的初始设置填写任何只能取一个值的方块，然后相应地调整其余部分的约束条件未解决的广场。

通常，“常量传送”的这个过程中没有解决板完全，但它确实解决了相当大的块。第二层然后踢入。这解析每个单元（或者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

鉴于未解平方在一个单元中的整个阵列（如上面在第二层中所述），第二层将串联的所有字符串“可能性”转换为单个字符串。然后，它将通过该单个字符串搜索任何独特的字符值 - 不会重复的值。这将表明，在正方形单位内，只有一个正方形可以采用该特定值。

我的问题是：执行本二线，我怎么能在解析一个单位的所有可能值的这个字符串，方便地检测的独特价值（S）？我知道我可以创建一个数组，其中每个索引由数字1-9表示，并且我可以将相应索引处的值递增1，以找到该数字的每个可能值，然后再次扫描数组值为1，但这看起来非常低效，需要对每个单元进行两次线阵扫描，而在一个数独拼图中，有27个单位。

来源

2008-12-29 Magsol

这有点像你已经排除了“效率极低”，但与内建功能，因此它可能是非常有效：

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

来源

2008-12-30 00:36:38 PEZ

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是这些事情的最佳方式，据我所知这不是不合理的。

来源

2008-12-30 00:41:24 Glazius

考虑使用二进制数来表示你的“候选条件”代替，因为像AND，OR，XOR二进制操作往往比字符串操作快得多。

E.g.如果“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 
}

我不知道，如果这个方法将实际工作速度更快，但它是值得研究的。

来源

2008-12-30 00:56:20 Artelius

上次我用Sudoku求解时，我有第三个类叫做“Run”。为每行，col和3x3正方形创建一个Run实例。每个广场都有三个与之相关的跑步。 Run类包含尚未放置在运行中的一组数字。然后解决棋盘涉及迭代地在每个方格上相交集合。这需要处理大多数中型板的80％以及大多数硬板的60％。一旦你完成整个板子而没有任何改变，你就可以转向更高层次的逻辑。每次你的高级逻辑填充一个正方形时，你再次穿过你的正方形。

这个设置的好处是你可以很容易地向求解器添加变体。假设你使用两个对角线也是唯一的变体。您只需在这18个方格中添加第四次运行。

来源

2008-12-30 01:13:16 jmucchiello

我会做什么，实际上是使用二进制位来存储实际值作为另一个建议的答案。这允许进行有效的检查，并且通常可以将Sudoku本身提供给更加数学的（=高效的和更短的）解决方案（就我的印象而言，我没有研究过）。

基本上，你所代表的号码不以数字方块，但与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

现在$候选条件中包含的是，在这个广场是可能的数字位的位置“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

来源

2008-12-30 08:02:40 Gnudiff

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

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

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

来源

2008-12-31 08:53:35 null

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

回答

相关问题