今天我的朋友提出了一个我仍然无法解决的挑战：“在PHP中生成随机数字序列”
数字排列为拨号盘/图案锁，由 1-9 键组成 3 行 3 列：
---------------------------
| |
| 1 2 3 |
| |
| 4 5 6 |
| |
| 7 8 9 |
| |
---------------------------
现在，给定一个长度，我们必须使用以下标准生成一个随机的、不重复的给定长度的数字序列：
生成的序列应遵循仅通过相邻数字（可能是对角线）的特定方向/模式，例如（长度：8）、12569874：
1 🡪 2
🡫
4 5 🡪 6
🡩 🡫
7 🡨 8 🡨 9
第一行的数字后面不应跟第三行的数字，反之亦然。列也是如此。例如，1 后面不能跟 8，6 后面不能跟 4。
可以从Android模式锁定系统轻松猜测更多标准
以下是一些生成的序列示例，长度为 9：12369874/5、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);
但是，还是没有运气...
我该如何解决这个问题？
有一些限制，但这需要您自己解决。 我只有在得到报酬时才会处理头痛:)。
<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>
这是应用这些规则的解决方案：
以下算法对添加到序列中的每个数字使用递归。每当序列“卡住”时，就会发生回溯，并尝试替代路径。如果没有更多替代方案，则继续回溯。
保证返回给定长度的路径，前提是给定长度在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";
这是一个矩阵的伪代码示例，如下所示：
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