3

我正在用 PHP 编写算法来解决给定的数独难题。我已经建立了一个有点面向对象的实现，它有两个类：一个Square类用于 9x9 板上的每个单独的瓷砖，一个Sudoku类，它有一个Squares 矩阵来表示板。

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

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

4

6 回答 6

3

这有点像您已经排除的“效率极低”，但是使用内置函数，它可能非常有效：

$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-30T00:36:38.213 回答
1

考虑使用二进制数来表示您的“可能”，因为像 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
}

我不确定这种方法是否真的会更快，但值得研究。

于 2008-12-30T00:56:20.450 回答
0 
 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-30T00:41:24.270 回答
0

上次我用数独解决问题时，我有第三节课，叫做“跑”。为每一行、col 和 3x3 正方形创建一个 Run 实例。每个方格都有与之关联的三个运行。Run 类包含尚未放置在运行中的一组数字。解板然后涉及迭代地在每个正方形处相交集合。这可以处理 80% 的大多数中板和 60% 的大多数硬板。一旦你完成了整个电路板而没有任何变化，你就可以进入更高级别的逻辑。每次您的高级逻辑填充一个正方形时，您都会再次遍历您的正方形。

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

于 2008-12-30T01:13:16.563 回答
0

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

基本上，您不是用数字表示数字，而是用 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
于 2008-12-30T08:02:40.060 回答
0

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

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

echo getUniques("1234567891234"); // return 56789;
于 2008-12-31T08:53:35.523 回答