3

特定の数独パズルを解くアルゴリズムを PHP で作成しています。Square9x9 ボード上の個々のタイルごとのクラスと、ボードを表す s のSudokuマトリックスを持つクラスの 2 つのクラスを使用して、ややオブジェクト指向の実装をセットアップしました。Square

私が使用しているアルゴリズムの実装は、一種の 3 層アプローチです。最初のステップは、最も基本的なパズルのみを解決します (ただし、最も効率的です)。ボードの初期設定に基づいて単一の値しか取り得ない正方形を埋め、残りの部分に応じて制約を調整します。未解決の正方形。

通常、この「一定の伝播」のプロセスはボードを完全には解決しませんが、かなりの部分を解決します。次に、2 番目の層が開始されます。これは、未解決の各正方形の「可能な」値について、各ユニット (または行または列などの一意の番号割り当てが必要な 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

(上記の第 2 層で説明したように) ユニット内の未解決の正方形の配列全体が与えられると、第 2 層は「可能性」のすべての文字列を単一の文字列に連結します。次に、その単一の文字列を検索して、一意の文字値 (繰り返されない値) を探します。これは、正方形の単位内で、その特定の値を取ることができる正方形が 1 つしかないことを示します。

私の質問は、この第 2 層を実装するために、ユニット内のすべての可能な値のこの文字列を解析し、一意の値を簡単に検出するにはどうすればよいですか? 各インデックスが 1 ～ 9 の数字で表される配列を作成できることはわかっています。また、見つかったその数字の可能な値ごとに、対応するインデックスの値を 1 ずつ増やしてから、配列を再度スキャンして、値は 1 ですが、これは非常に非効率的で、各ユニットに対して配列の 2 つの線形スキャンが必要であり、数独パズルでは 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項演算は文字列演算よりもはるかに高速である傾向があるため、代わりに2進数を使用して「可能性」を表すことを検討してください。

たとえば、正方形に「2」と「3」が可能である場合、その正方形の可能性を表すために2進数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でない場合（先頭にシングルトンがある場合の厳密な比較）、その配列にはそのような数値が1つだけあります。

ここで速度が非常に心配な場合は、おそらくそのループの内部を次のように置き換えることができます

 $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

私がすることは、別の回答が示唆するように、実際の値を格納するために実際にバイナリビットを使用することです。これにより、効率的なチェックが可能になり、一般的に、数独はより数学的な (= 効率的で短い) ソリューションに役立つ可能性があります (私の印象です。これについては調査していません)。

基本的に、数字ではなく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 に答える
0

前回数独を解いてだまされたとき、「ラン」という 3 番目のクラスがありました。各行、列、および 3x3 の正方形に対して Run インスタンスが作成されます。すべての正方形には、それに関連付けられた 3 つのランがあります。Run クラスには、ラン内にまだ配置されていない一連の数字が含まれています。ボードを解くには、各正方形でセットを繰り返し交差させる必要があります。これにより、ほとんどのミディアム ボードの 80% とほとんどのハード ボードの 60% が処理されます。変更なしでボード全体を確認したら、より高いレベルのロジックに進むことができます。高レベルのロジックが正方形を埋めるたびに、正方形をもう一度実行します。

この設定の良いところは、ソルバーにバリアントを簡単に追加できることです。2 つの対角線も一意であるバリアントを使用するとします。これらの 18 マスに 4 回目を追加するだけです。

于 2008-12-30T01:13:16.563 に答える