は、私の友人は、私はまだ解決できない課題を提起した

Question

今日桁のランダムな「パターンロック」シーケンスを生成します3行3列の1-9キー成る-lock：今

--------------------------- 
|       | 
|  1  2  3  | 
|       | 
|  4  5  6  | 
|       | 
|  7  8  9  | 
|       | 
--------------------------- 

は、長さが与えられると、我々は、これらの基準を使用して、提供される長さの桁のランダムな、非反復シーケンスを生成する必要があります。

1. Aは、配列は、例えば、（長さ：8）隣接する数字（おそらく斜め）を介してのみ向かう特定の方向/パターンに従わなければならない生成：最初の行の数字が続いてはならない

   1 2 
        
   4 5 6 
         
   7 8 9 
   

2. 、12569874を第3行からの桁、およびその逆の場合もある。列についても同様です。例えば、図1は、8に続くことができない、および6を容易にAndroidのパターンロックシステムから

ここ発生いくつかの例であることができる複数の基準を推測することができる。4.

を続けることができません長さ9のための配列：5分の12369874、142536987など、および長さ= 6：987532など

Iはrand()でこれを行うことを試みた：

$chars = "123456789"; 
    $length = 9; 
    $clen = strlen($chars)-1; 
    $id = ''; 

    for ($i = 0; $i < $length; $i++) { 
     $id .= $chars[mt_rand(0,$clen)]; 
    } 
    return ($id); 

しかし、まだ運がありません...

どうすればこの問題を解決できますか？

Answer 1

にはいくつかの制限がありますが、それは解決するためのものです。私は支払ったときだけ頭痛に対処する:)。ここで

<pre> 
<?php 

// Keypad 
$grid = [ 
    ['1', '2', '3'], 
    ['4', '5', '6'], 
    ['7', '8', '9'], 
]; 

// Sequence Target Length 
$target_length = 5; 

// Place to store the Keypad sequence 
$points = []; 

// Starting Point 
$x = rand(0, 2); 
$y = rand(0, 2); 

// Run through the process until we have the sequence at the desired length 
while (count($points) < $target_length): 

    // Check if the grid keypad entry has been used 
    if ($grid[$x][$y]): 
     // Hasn't been used, so stire it 
     $points[] = $grid[$x][$y]; 
     // Mark it used 
     $grid[$x][$y] = NULL; 
    endif; 

    // Sanity Check, imagine if you will,.... target length of 9, and you hit 6 5 2 1, You'll vault off into the twilight zone without this 
    if ((!$grid[$x + 1][$y]) && (!$grid[$x][$y + 1]) && (!$grid[$x - 1][$y]) && (!$grid[$x][$y - 1])): 
     // We have no where to go 
     break; 
    endif; 

    // Start looking for possible values 
    do { 
     $test_x = $x; 
     $test_y = $y; 
     $dir = rand(0, 3); 

     switch ($dir): 
      case (0): 
       $test_y--; // Up 
       break; 
      case (1): 
       $test_x++; // Right 
       break; 
      case (2): 
       $test_y++; // Down 
       break; 
      case (3): 
       $test_x--; // Left 
       break; 
     endswitch; 
     // Optional Gibberish 
     echo "Moving from {$x}, {$y} to {$test_x}, {$test_y} --> " . (($grid[$test_x][$test_y] === NULL) ? 'FAILED' : 'OK!') . '<br>'; 

     // Keep going until we find a valid direction 
    } while ($grid[$test_x][$test_y] === NULL); 

    // assign the new coords 
    $x = $test_x; 
    $y = $test_y; 

    // repeat 
endwhile; 

// report 
echo implode('-', $points) . "\n"; 

?> 
</pre> 

Answer 2

ここでは、このようになりますマトリックスのための擬似コードの例です：あなたの行列が大きいことが起こっているか、あなたが生成するためにいくつかのコードを書きたいかもしれません変化することが起こっているadjacenyではなく、ハードコーディングする場合

1 2 
3 4 

# Get which other numbers are "legal moves" from each number. 
adjacency = { 
    1: [2, 3], 
    2: [1, 4], 
    3: [1, 4], 
    4: [2, 3] 
} 

# Get the length of code required. 
n = 8 
# Start at a random position; 
pos = rand(keys(adjacency)) 
result = [] 
while (n > 0) 
    n -= 1 
    newpos = rand(adjacency[pos]) 
    result[] = newpos 
    pos = newpos 
print(result.join(', ')) 

それ。

Answer 3

これらの規則を適用するソリューションです。

• パスだけ斜めに
• パスは二回同じセルを含めることはできませんを含む隣接している隣接セル、すなわち、にステップ実行することができます

次のアルゴリズムは、シーケンスに追加されるすべての桁に対して再帰を使用します。シーケンスが「スタック」すると、バックトラックが発生し、代替パスが試行されます。代替案がない場合、バックトラックが継続されます。

与えられた長さを提供し、与えられた長さのパスが返されることが保証されているが、1と9の間にある：

function randomSequence($len) { 
    if ($len < 1 || $len > 9) return []; // No results 
    $row = [null, 1, 1, 1, 2, 2, 2, 3, 3, 3]; 
    $col = [null, 1, 2, 3, 1, 2, 3, 1, 2, 3]; 
    $neighbors = [[], [2, 4, 5],  [1, 4, 5, 6, 3],   [2, 5, 6], 
         [1, 2, 5, 7, 8], [1, 2, 3, 4, 6, 7, 8, 9], [2, 3, 5, 8, 9], 
         [4, 5, 8],  [4, 5, 6, 7, 9],   [5, 6, 8]]; 
    // Shuffle the neighbor lists to implement the randomness: 
    foreach ($neighbors as &$nodes) shuffle($nodes); 

    $recurse = function ($seq) use (&$len, &$row, &$col, &$neighbors, &$recurse) { 
     if (count($seq) >= $len) return $seq; // found solution 
     $last = end($seq); 
     echo "try " . json_encode(array_keys($seq)) . "\n"; 
     foreach ($neighbors[$last] as $next) { 
      if (isset($seq[$next])) continue; // Skip if digit already used 
      $result = $recurse($seq + [$next => $next]); 
      if (is_array($result)) return $result; 
     } 
    }; 
    $choice = rand(1, 9); 
    return array_keys($recurse([$choice => $choice])); 
} 

echo "result: " . json_encode(randomSequence(9)) . "\n"; 

は、それがrepl.it