Sudoku求解器速度较慢，需要更早考虑约束条件 [英] Sudoku solver is slow, needs considering constraints earlier

问题描述

我有一个用序言编写的NxN数独求解器.下面的代码可以很好地解决4 * 4问题. (我有一些域信息)但是9x9的速度很慢.我已经尝试了多种方法来改进create row函数，它已经考虑到行中的每个值都应该是唯一的(并且必须包含在其域中)，但是它们没有用. 在没有任何库的情况下如何改进呢?

I have an NxN sudoku solver written in prolog. The code below works fine for 4*4 solving. (I have some Domain infos) But it is slow for 9x9. I've tried many way to improve the create row function, that it is already considering that every value in a row should be unique (and must be contained in its domain), but they did not work. How could I improve this without any librarys?

all_distinct(X) :-
    sort(X, Sorted),
    length(X, OriginalLength),
    length(Sorted, SortedLength),
    OriginalLength == SortedLength.

 good_by_coulmns(Solution) :- length(Solution, Length), 
                              forall((between(1, Length, X), get_column(Solution, X, Y)),
                              all_distinct(Y)).
get_area(Solution, X, Y, Z) :- length(Solution, Length), 
                               SQRootF is sqrt(Length),
                               SQRoot is round(SQRootF),
                               MinCol is SQRoot * (X-1) + 1,
                               MinRow is SQRoot * (Y-1) + 1,
                               matrix_block(MinRow, MinCol, SQRoot, SQRoot, Solution, A), flatten2(A,Z).

good_by_areas(Solution) :- length(Solution, Length),
                           SQRootF is sqrt(Length), SQRoot is round(SQRootF),
                           forall((between(1, SQRoot, X), between(1, SQRoot, Y), get_area(Solution, X, Y, Z)),
                           all_distinct(Z)).

createRow(Solution, Domain, Row) :- maplist(member, Row, Domain), 
                                    all_distinct(Row), 
                                    good_by_coulmns(Solution).%, write(Solution), nl.

tryToSolve(Domains, Solution) :- length(Solution, L), length(Domains, L), !, 
                                 maplist(createRow(Solution), Domains, Solution),
                                 good_by_coulmns(Solution), 
                                 good_by_areas(Solution).

如果需要，我可以提供缺少的规则，但这工作得很好，因此我们可以将其用作构建基块.

I can give the missing rules if needed, but this is working fine sofar, so we can use these as building blocks.

推荐答案

问题更多是关于AI然后编程.

The question is more about A.I then programming.

好吧，您需要为数独设置一些约束，以使其更快地工作.有一个约束，但是这很繁琐，所以我将以数学形式进行解释和编写，这取决于您如何实现代码以及可以轻松采用它:

Well, you need some constraints for your sudoku in order to let it work faster. There is a constraint,however it's much work so i will explain and write it in mathematics form and it depends how you implemented your code and you can easily adopt it:

构想:基本思想是，当给您一些数独时，您可以立即填充几个位置，以便在许多分支机构中程序不会深入，然后失败，然后回溯，而是如果它在某个更高的节点上失败，则更好.看下面的图片，如果您放置此约束，则可以在6个地方阻止prolog的方式，而在3个地方只允许它，因为每一行都有9个元素.在许多情况下，它不会探索我标记为蓝色的节点.在没有约束的情况下，它会一直持续到最后，您会看到它探索了多少个额外的分支.

Idea: The basic idea is that when you are given some sudoku then you can immediately fill few places so that at many branches program will not go into depth and then fail and then backtrack , instead it's better if it fails at some higher node. Look below at the picture, If you place this constraint then it's possible to block the way for prolog at 6 places and allow it only at 3 places because every row has 9 elements. In many cases it will not explore the nodes where i have marked blue.Without constraint it will go down till the end and you see how many extra branches it explores.

如何?我们利用数独的属性:

How? We exploit the properties of sudoku:

规则:每行，每个列和每个网格都有独特的元素.

Rules: Every row , every colum and every grid has unique elements.

算法:给定一些(数独表)后，您必须检查前三行(0,1,2)，如果两行中的任何元素均相同.例如，对于第一行中的每个元素，您都必须检查该元素是否在第二行或第三行中，然后转到第二行并尝试查找第二行和第三行中的元素.这有两种可能性:

Algorithm: When you are given some (sudoku-table) then you have to check first three lines(0,1,2) if they have any element which is same in any of two rows. For example for every element from first row you have to check if that element is in 2nd or third row if not then go to second row and try to find an element which is in second and third row. Here are two possibilities:

您没有匹配项:如果前三行没有相同的元素，请转到下三行(3,4,5)并找到然后再行(6,7) ，8).

You have no match: If first three lines don't have any same element then go to the next three line (3,4,5) and find there and then line (6,7,8).

注意:您只需检查一起形成网格(3x3矩阵)的那些行.例如，行(0,1,2)在一起，则(3,4,5)是在一起，然后(6,7,8)在一起.

Note: You have to check only those lines who form a grid(3x3 matrix) together.For example rows (0,1,2) are together then (3,4,5) are together and then (6,7,8) are together.

您有一个匹配项:假设您在第(0,2)行中找到了一个匹配项.由于每行可以有一个唯一元素，因此我们知道this元素应该在第1行中，但是我们如何知道结果行是1，那么，我们需要一个公式.见下:

You have a match: Suppose you found a match in rows (0,2). Since each row can have a unique element then we know that the this element should be in row 1 but how do we know that the resulting row is 1 ,well , we need a formula. see next:

数学形式:您可以通过相减得到总结果行.我们在第0行和第2行有一个匹配项.正弦这三行在一起，因此我们将它们的行号相加(0 +1 + 2 = 3).由于我们使用变量，因此您在(i = 0和j = 2)处匹配，并且您的总和= 3

Mathematics form: You can get always resulting row by subtraction. We had a match at row 0 and row 2. Sine these three rows are together so we take sum of their row number (0 + 1 + 2 = 3). Since we work with variables and you match at (i = 0 and j = 2) and your total sum = 3

和sum- i - j = 1 so the new element should be in row 1.此公式始终有效:认为您在行号(i = 4 and j = 5)处匹配，然后在这三个行号之和

and sum- i - j = 1 so the new element should be in row 1 . This formula is always valid: think that you have match at row numbers (i = 4 and j = 5) then sum of these three row numbers

是4 + 5 + 6 = 15并减去15 - 4 -5 = 5.但是，还有其他方法，但是我们使用变量，因此我们需要知道必须将与之匹配的元素放在哪一行中的其他两行中.

is 4 + 5 + 6 = 15 and subtract 15 - 4 -5 = 5. However there are alternative ways but we work with variable so we need to know in which row we have to place the element from which we have a match in other two rows.

确定网格:确定新元素将位于哪一行后，下一步就是检查其将位于哪一网格中，因为每一行都是三个网格(3x3矩阵)的一部分).例如，第0行在第一个网格中具有元素(0,1,2)，然后在第二个网格中具有元素(3,4,5)，然后在第三个网格中具有元素(6,7,8).

Determining grid: Once you have determined in which row your new element will lie then the next step is to check in which grid it will lie because every row is a part of three grids(3x3 matrices). For example rows 0 has elements (0,1,2) in first grid then (3,4,5) in second grid and then (6,7,8) in third grid.

总共有(9)个子网格，且从(0到8)开始.

In total you have (9) subgrids and starting from (0 to 8).

子网格与行之间的关系:我们只有关于行的信息，因此我们需要找到行与网格号之间的关系.这是一个NxN矩阵，因此网格的高度等于网格的宽度(3x3)，这意味着每三行一起形成3个网格，因为行的长度为9，网格的长度为3，所以我们得到3个网格高度3和长度3的示例.示例:行(0,1,2)形成三个网格，起始于0，1，2，然后是来自另外3个网格的行(4,5,6):gridnumber(4,5,6).

Relation between subgrids and rows: We have only infromation about rows so we need to find relation between rows and grid numbers. It's a NxN matrix so height of a grid is equal to the width of the grid(3x3) that means that every three rows together form 3 grids because the length of the rows is 9 and length of the grid in 3 so we get 3 grids of height 3 and length 3.Example: rows (0,1,2) form three girds starting at 0 ,1 ,2 and then rows (4,5,6) from another3 grids: gridnumber(4,5,6) .

我们可以通过执行以下操作来获得其网格编号:(假设在第0行，第4列有匹配项，第2行和第2列匹配，那么我们应该得到第0网格和第1网格(respt)，因为第一个网格是网格0(列:0 1 2).

We can get their grid number by doing this : (suppose at row 0 we had a match at colum 4 with a row number 2 and colum number 2 then we should get grid 0 and grid 1(respt) because first grid is grid 0(colum: 0 1 2).

我们使用此公式在一维列表中获取网格号.

We use this formula to get a grid number in one dimensional list.

(mod(x,9)/3) + 3*(x/27)

我们现在知道网格1和2不能具有此元素，因为在每个网格中我们都需要一个从1到9的唯一元素.因此它应该是网格0，但是如何得到结果网格，我们可以得到再次取三个行数之和(因为行数等于网格数)= 3，然后减去其他两个网格的网格数为(0 + 1)，则得出网格2.

We know now that grid 1 and 2 can't have this element because in every grid we need a unique elemen from 1 to 9. SO it should be grid 0 but how do get resulting grid, well , we can get that again by taking sum of the three row numbers (because number of rows are equal to number of grid) which is = 3 and subtract the grid number of other two grids which was(0+1) then we get grid 2.

我们还没有完成，我们需要将其转换为一个索引，因为我们主要处理一维列表.所以这个公式给出了确切的位置:

We are not done yet , we need convert this thing to one index because we work mostly with one dimensional list. So this formula give exact place:

公式: x =(newRow)* 9 +(newGrid)* 3 和 x 是我们的位置.您可以通过插入值来验证此公式.现在，我们获得了可以放置元素的确切三个槽.此时，您说list [x] = list [i]或list [x + 1] = list [i]或list [x + 2] = list [i].

formula: x = (newRow)*9 + (newGrid)*3 and x is our place. You can verify this formula by pluging in values.Now we get exact three slots where out our element can be placed. At this point you say that either list[x] = list[i] or list[x+1] = list[i] or list[x+2] = list[i].

这篇关于Sudoku求解器速度较慢，需要更早考虑约束条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！