Objective-c中的数独生成

Question

我应该制作一个生成完全数独谜题的应用程序.我可以使用以下代码正确生成第一行,但是,无论我做什么,我都无法使下一行正常工作.他们都生成了正确的方法,因为我以随机的顺序得到数字1-9,但我无法让它制作一个可行的数独谜题.

码:

NSMutableArray *array = [[NSMutableArray alloc] initWithCapacity:8];
    for (int integerA = 0; integerA < 10; integerA ++) {
        [array addObject:[NSNumber numberWithInt:integerA]];
        //NSLog(@"%i", (integerA + 1));
    }

 for (int x = 8; x >= 0; x --) {
        [array exchangeObjectAtIndex:(arc4random() % (x + 1)) withObjectAtIndex:x];
        section[x][0] = ([[array objectAtIndex:x] intValue] + 1);
        for (int y = 8; y >= 0; y --) {
            if (0) {

            }
        }
    }

那部分有效.如果我尝试创建另一个数组并为每个"x"值生成"y"值,那就太奇怪了.如果没有多条条件语句,是否有一种有效的方法来生成完全解决的数独谜题？

"奇怪的结果":

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

Answer 1

找到正确的数独计划的问题是一个非常常见的功课,它有许多不同的解决方案.

我不会向你提供代码,但是让我给你一些建议:你当然知道,目的是生成一个在行,列和方形中具有非重复数字的方案.
更基本的是,这是产生随机非重复数的问题.网络上充满了解决这个问题的方法,这里和这里只是几个例子.

现在我们能够生成非重复数字,问题是填满表格.

有许多可能的方法:显然你不能避免检查(以某种方式)当前数字每行,每列,正方形只出现一次.

我想到的第一个解决方案是递归过程(让我们称之为int fill(int row)):

在do-while 循环中(我将在后面解释为什么)执行此操作:

• 生成一个随机数组(这是为了避免算法始终生成相同的方案)非重复数字(从1到9)

这可能成为row您计划的最新行.当然,大多数情况下你准备好你的行是不会很幸运的,所以你必须检查一些条件:

• 对于数组中的每个数字,检查它是否第一次出现在列和正方形中(由于您构建了一个非重复数字数组,因此无需检入该行).

我不会进一步解释如何检查,因为它几乎是微不足道的.
如果是,请将其复制到您的方案中,并在阵列末尾移动它.这样,在数组的开头,您将始终拥有未使用的数字.
如果不是,请跳过它并尝试下一个.

注意:您必须保留已使用数字的引用,否则您可以在一行中使用相同数字的两倍.

• 但是,通过这种方式,可以在没有数字似乎适合您的桌子的情况下到达.在这种情况下,只需返回0

• 相反,如果您在当前行中插入了所有9个数字,请致电int chk = fill(row+1).当然,如果到达最后一行(row==9),则不能调用递归步骤.在这种情况下,只需返回1.

chk 将存储递归步骤的返回值.

• 如果chk==0这意味着该算法无法为下一级别找到合适的行.在这种情况下,只需重新启动初始do-while循环.

• 否则递归步骤成功,因此您可以返回1.

但是,这只是一种可能的解决方案.还有许多其他可能的算法/变化.由您来提高性能并进行一些优化.