0

I'm trying to create a sudoku solver program in Java (maybe Python). I'm just wondering how I should go about structuring this...

Do I create a class and make each box a object of that class (9x9=81 objects)? If yes, how do I control all the objects - in other words, how do I make them all call a certain method in the class?

Do I just create functions to calculate and just control all the numbers in there with something like an multi-D array?

And actually, even if I could just create multiple functions, how would I control all the objects if I were to make each box an object?

Thanks.

4

8 回答 8

12

Don't over-engineer it. It's a 2-D array or maybe a Board class that represents a 2-D array at best. Have functions that calculate a given row/column and functions that let you access each square. Additional methods can be used validate that each sub-3x3 and row/column don't violate the required constraints.

于 2009-01-11T00:05:14.240 回答
2

Well, I would use one class for the sudoku itself, with a 9 x 9 array and all the functionality to add numbers and detect errors in the pattern.

Another class will be used to solve the puzzle.

于 2009-01-11T00:06:27.983 回答
1

只是为了好玩，这应该是最短的程序，在 python 中，可以解决数独网格：

def r(a):i=a.find('0') if i<0:print a [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]r(raw_input())

嗯，好吧，这很神秘，我认为它与您的问题不符，所以我为这种噪音道歉:)

无论如何，您会在这里找到对这 173 个字符的一些解释。这里也有法语解释

于 2009-04-07T13:58:12.663 回答
1

Do you need to do it in Python or Java? I do a lot of programming in Python, but this can be done much more concisely with integer program using a language like AMPL or GLPK, which I find more elegant (and generally more efficient) for problems like this.

Here it is in AMPL, although I haven't verified how this works: http://taha.ineg.uark.edu/Sudoku.txt

于 2009-01-11T00:07:04.097 回答
1

The simplest way to do it is to represent the board by a 2D 9x9 array. You'll want to have references to each row, column and 3x3 box as a separate object, so storing each cell in a String makes more sense (in Java) than using a primitive. With a String you can keep references to the same object in multiple containers.

于 2009-01-11T00:08:57.307 回答
0

首先，看起来有两种细胞。

  • 已知电话；那些有固定值的，没有选择。

  • 未知细胞；那些具有一组候选值的候选值减少到一个最终值。

其次，有几组细胞。

  • 水平行和垂直列，每个值必须有一个单元格。该约束用于从行或列中的各个单元格中删除值。

  • 3x3 块，每个值必须有一个单元格。该约束用于从块中的各个单元格中删除值。

最后是整体网格。这有几个互补的观点。

  • 这是81个细胞。

  • 这些细胞也被收集到一个由 3x3 块组成的 3x3 网格中。

  • 细胞也被收集到 9 列中。

  • 细胞也被收集成 9 行。

你有一个求解器策略对象。

  1. set( range(1,10) )它设置为具有候选值的每个未知单元格。

  2. 对于每一行、每一列和 3x3 块（27 个不同的集合）：

    一个。对于每个单元格：

    • 如果它具有确定的值（已知单元格和未知单元格的实现方式不同）：从该分组中的所有其他单元格中删除该值。

以上必须迭代，直到没有发现任何变化。

此时，您要么解决了它（所有单元格都报告了一个确定的值），要么您有一些具有多个值的单元格。现在，您必须使用复杂的回溯求解器来找到“有效”的剩余值的组合。

于 2009-01-11T00:40:43.530 回答
0

包含 81 个整数的一维数组（0 为空）的类对于规则类来说就足够了。规则类强制执行规则（每行、每列或 3x3 方格中没有重复的数字）。它还有一个包含 81 个布尔值的数组，因此它知道哪些单元格是固定的，哪些需要解决。此类的公共接口具有操作板所需的所有方法：

int getCell(int x, int y);
bool setCell(int x, int y, int value);
bool clearCell(int x, int y);
int[] getRow(int x);
int[] getCol(int y);
int[] getSubBox(int x, int y);
void resetPuzzle();
void loadPuzzle(InputStream stream);

然后你的求解器使用这个类的公共接口来解决这个难题。我认为求解器的类结构是编写第 5 百万个数独求解器的目的。如果您正在寻找提示，我稍后会编辑此帖子。

于 2009-01-11T00:49:56.273 回答
0

Maybe a design that had a box per square, and another class to represent the puzzle itself that would have a collection of boxes, contain all the rules for box interactions, and control the overall game would be a good design.

于 2009-01-11T00:06:23.770 回答