当前位置：文江博客话题详情

表示数独谜题的正确数据结构？

发布于 2024-09-30 05:04:51 字数 219 浏览 12 评论 0原文

用于表示数独谜题的智能数据结构是什么？即一个 9X9 的正方形，其中每个“单元格”包含一个数字或一个空格。

特殊考虑因素包括：

能够跨行、列和 3X3“组进行比较
易于实现（特别是在 Python 中）
效率（不是最重要的）

我想在紧要关头，二维数组可能会起作用，但这似乎不太优雅我只是想知道是否有更好的数据结构。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不念旧人 2024-10-07 05:04:51

实际上，我构建了这样一个野兽，既是求解器又是生成器，并且我使用了 2D 数组。效果很好。

您只需要了解索引以及它们在哪里，掌握起来并不难。

行中的单元格之间的相对关系不会根据列而改变，列中的单元格甚至小方块中的单元格也是如此。

有时，不太“优雅”的解决方案就可以了。事实上，有时，这是更好的:-)

就其价值而言，您可能对我用于求解器/生成器的算法感兴趣。

首先，我编写了求解器部分，它首先将所有单元格设置为可以是任何值，然后按顺序应用所有规则来查看单个单元格是否可以被求解或以其他方式受到限制，例如：

如果单元格是线索，将其设置为该值。
如果一行（或列或小方块）中只剩下一个单元格，则可以将其设置为剩余值。
如果某个单元格被标记为可能是 N 并且 N 存在于其行/列/小方块中的其他位置，则消除这种可能性。
如果行/列/小方块中有两个单元格，并且它们具有相同的两种可能性（并且没有其他可能性），则该行/列/小方块中的所有其他单元格都应该删除该可能性。

依此类推，添加我在解决真正的难题时使用的每条规则。

对于生成器，我从：开始

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

，然后在不同大小（至少 500）的循环中，继续以永远不会产生无效谜题的方式交换行和列。换句话说，将行或列与它们所在的组交换（例如，第 1、2 和 3 行是一个组，第 4、5 和 6 列也是一个组）。

这足以对细胞进行重组，从而产生一个像样的谜题。

然后，我开始选择随机单元格并将它们设置为未知。一旦单元格被设置为未知，我就会将整个谜题传递给求解器。如果可以解决，我会继续，否则我会重新设置单元格并继续。

这防止了我遇到逻辑上无法解决的难题。

一旦完成大量随机单元删除，我将尝试使用相同的方法按顺序删除所有剩余的单元。剩下的就是解决这个难题所需的最少信息量。

而且，所以这对数独初学者来说并不是一件痛苦的事，我允许他们指定一个较低的难度级别，这将把一定数量的不必要的单元放回去。这

不是一个坏方案，可能有更好的方案，但有一个有效对我来说很好。

现在，如果我能弄清楚这些 Kakuro 的东西，我就可以幸福地死去:-)

Actually, I built such a beast, both a solver and a generator, and I used a 2D array. It worked fine.

You just had to understand the indexes and where they were and that wasn't too difficult to master.

The relative relationships between cells in a row doesn't change depending on the column, same goes for cells in a column, or even cells in a mini-square.

Sometimes, a less "elegant" solution is just fine. Indeed, sometimes, it's preferable :-)

For what it's worth, you may be interested in the algorithms that I used for the solver/generator.

First I wrote the solver part which would first set all cells as being able to be any value then apply all the rules in sequence to see if a individual cell could be solved or otherwise limited, things like:

if the cell was a specific value in the clues, set it to that value.
if there's only one cell left in a row (or column or mini-square), you can set it to the remaining value.
if a cell is marked as being possibly N and N exists in its row/column/mini-square elsewhere, remove that possibility.
if there are two cells in the row/column/mini-square and they have the same two possibilities (and no other possibilities), all other cells in that row/column/mini-square should have that possibility removed.

And so on, adding each rule that I use in solving the real puzzles.

For the generator, I started with:

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

and then, in a loop of varying size (at least 500), proceeded to swap rows and columns in such a way that it would never produce an invalid puzzle. In other words, swap rows or columns with the group they're in (for example, rows 1, 2 and 3 are a group, so are columns 4, 5 and 6).

This shuffled up the cells well enough to produce a decent puzzle.

Then, I started choosing random cells and setting them as unknown. Once a cell was set as unknown, I would pass the whole puzzle into the solver. If it was solvable, I would continue, otherwise I would re-instate the cell and carry on.

This prevented me getting a puzzle that was logically unsolvable.

Once a large number of random cell removals had been done, I would try to remove all the remaining cells in order using the same method. What was left then was the minimum amount of information required to solve the puzzle.

And, so it wasn't a pain to Sudoku beginners, I would allow them to specify a lower difficulty level which would put a certain number of the unnecessary cells back in.

Not a bad scheme, there may be better ones but that one worked fine for me.

Now, if I could only figure out this Kakuro stuff, I could die happy :-)

回复收藏 0 原文