生成数字随机“模式锁定”序列

Question

今天我的朋友提出，我仍然解决不了的挑战：数字被安排为拨号盘/模式“生成在PHP中的随机数字序列”

-lock即由3行1-9键和3列：

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

现在，给定的长度，我们要生成的设置长度的数字的随机的，非重复的序列，使用这些标准：

1. 甲生成的序列应该按照特定的方向/图案仅通过相邻数字去（可能对角），例如（长度：8），12569874：从第一行

   1 2 
        
   4 5 6 
         
   7 8 9 
   

2. 位数应该永远不会被随后是从第三行开始，反之亦然。列也是如此。例如，一个1不能被随后是8和6不能跟一个4.

3. 可以猜测多个准则可以很容易地从机器人图案锁定系统

下面是产生一些示例对于长度为9的序列：5分之12369874，142536987等，以及用于长度= 6：987532等

我试图与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

下面是伪代码为基质的例子是这样的：

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(', ')) 

如果你的矩阵将是大的或将要改变你可能想要写一些代码来生成adjaceny而不是硬编码它。

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