查找字符串中仅出现一次的字符 [英] Finding characters in a string that occur only once

问题描述

我正在用PHP编写算法来解决给定的数独难题。我已经建立了一个带有两个类的面向对象的实现：9x9板上每个单独的图块 Square 类，以及 Sudoku 类，它具有 Square s的矩阵来表示董事会。

I'm writing an algorithm in PHP to solve a given Sudoku puzzle. I've set up a somewhat object-oriented implementation with two classes: a Square class for each individual tile on the 9x9 board, and a Sudoku class, which has a matrix of Squares to represent the board.

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

The implementation of the algorithm I'm using is a sort of triple-tier approach. The first step, which will solve only the most basic puzzles (but is the most efficient), is to fill in any squares which can only take a single value based on the board's initial setup, and to adjust the constraints accordingly on the rest of the unsolved squares.

通常，这种恒定传播过程不能完全解决电路板问题，但可以解决相当大的一块问题。然后第二层开始。这将解析每个未解决的正方形的可能值的每个单位（或9个正方形，必须全部具有唯一的数字分配，例如，一行或一列）。此可能值列表在 Square 类中以字符串表示：

Usually, this process of "constant propagation" doesn't solve the board entirely, but it does solve a sizable chunk. The second tier will then kick in. This parses each unit (or 9 squares which must all have unique number assignments, e.g. a row or column) for the "possible" values of each unsolved square. This list of possible values is represented as a string in the Square class:

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

给定一个单位中未解决的正方形的整个数组（如以上第二层中所述），第二层会将可能的所有字符串连接为一个字符串。然后，它将在该单个字符串中搜索任何唯一的字符值-不会重复自身的值。这将表明，在平方单位内，只有一个平方可以具有该特定值。

Given a whole array of unsolved squares in a unit (as described in the second tier above), the second tier will concatenate all the strings of "possibles" into a single string. It will then search through that single string for any unique character values - values which do not repeat themselves. This will indicate that, within the unit of squares, there is only one square that can take on that particular value.

我的问题是：要实现第二层，如何实现我可以解析一个单元中所有可能值的字符串并轻松检测唯一值吗？我知道我可以创建一个数组，其中每个索引都由数字1-9表示，并且我可以为找到的该数字的每个可能值将对应索引处的值加1，然后再次扫描该数组以查找值1，但这似乎效率极低，每个单元需要对数组进行两次线性扫描，而Sudoku拼图中有27个单元。

My question is: for implementing this second tier, how can I parse this string of all the possible values in a unit and easily detect the unique value(s)? I know I could create an array where each index is represented by the numbers 1-9, and I could increment the value at the corresponding index by 1 for each possible-value of that number that I find, then scan the array again for any values of 1, but this seems extremely inefficient, requiring two linear scans of an array for each unit, and in a Sudoku puzzle there are 27 units.

推荐答案

这有点像您已经排除为极度低效的内容，但是具有内置功能，因此效率可能很高：

This is somewhat like what you have already ruled out as "extremely inefficient", but with builtin functions so it might be quite efficient:

$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

这篇关于查找字符串中仅出现一次的字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！