PHP中的数独解决/生成算法

Question

我在算法的某个特定部分遇到了麻烦，希望有人能够指出我做错了什么。

我的程序基本上是这样运作的：

创建 81 个空单元格，在检查它们是否有效的同时一步一步地填充每个单元格。

我有三个有效性检查，而水平有效性检查（如果数字在同一行中重复多次）已经给我带来了麻烦。

这是我的函数：

private function isValidHorizontal($index)
    {
        for ($i = 0; $i < 81; $i += 9){

            $firstIndex = $i * 9;
            $lastIndex = 9 * ($i + 1) - 1;

            // fisrt loop tracking fowards, 2nd loop tracking backwards
            if ($index >= $i && $index <= $lastIndex) {
                for ($j = 0; $j <= $lastIndex; $j++) {
                    if ($this->cell[$index]->getValue() == $j) {
                        return false;
                    }
                }
                for ($k = 0; $k >= $firstIndex; $k--){
                    if ($this->cell[$index]->getValue() == $j) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

$index 是单元格的位置，当 $index = 0 时，这是第一个单元格。最后一个单元格将为 $index = 80

$this->cell[$index]->getValue() 返回一个整数，我已经检查过，所以我正确地获取了值。

问题在于它似乎从来没有返回 true。

有任何想法吗？显然这只是代码的一部分，如果您需要更多帮助，请写下评论，我会进行编辑 :)

- gempir

Answer 1

在第二个内循环中，您使用了$j而不是$k：

for ($k = 0; $k >= $firstIndex; $k--){
    if ($this->cell[$index]->getValue() == $j) { // Here, change to $k

- laurent

---

该死，我现在感觉很愚蠢。现在完美运行了，谢谢！ - gempir

你有什么想法为什么我的代码现在停在了第9个单元格？第9个单元格是第二行的第一个单元格，所以它不应该遇到错误。 - gempir

Answer 2

你已经从@this.lau_那里得到了正确的答案，但如果我可以提供一些建议，你可以通过改变逻辑来缩短一些。PHP不是最适合这个任务的语言，所以它看起来仍然有点笨重，但值得一看。:)

private function isValidHorizontal($index) {
    $taken = [];
    foreach (range($index, 81, 9) as $i) {
        $value = $this->cell[$i]->getValue();
        if (is_int($value) && in_array($value, $taken)) {
            return false;
        }
        $taken[] = $value;
    }
    return true;
}

- Joel Hinz

---

我明白你想做什么，这会使它更有效率，但我已经在第一个单元格处得到了一个无效值。 - gempir

是的，我无法测试代码，因为我没有你的对象，所以我只是把它当作一个粗略的想法模板。对此我很抱歉。但至少你已经让其他答案中的代码工作了。 :) - Joel Hinz