优化数独求解回溯算法
我希望优化我的数独求解器的回溯算法。
现在的作用：
递归求解器函数采用具有各种给定值的数独谜题。
我将搜索拼图中的所有空槽，寻找可能性最小的槽，并获取值列表。
从值列表中，我将通过将列表中的值之一放入槽中来循环遍历它，并递归地求解它，直到填满整个网格。
对于某些谜题来说，这个实现仍然需要非常长的时间，我希望进一步优化它。有谁知道我如何进一步优化这个？
如果您有兴趣，这是我的 Java 代码。
public int[][] Solve(int[][] slots) {
// recursive solve v2 : optimization revision
int[] least = new int[3];
least[2] = Integer.MAX_VALUE;
PuzzleGenerator value_generator = new PuzzleGenerator();
LinkedList<Integer> least_values = null;
// 1: find a slot with the least possible solutions
// 2: recursively solve.
// 1 - scour through all slots.
int i = 0;
int j = 0;
while (i < 9) {
j = 0;
while (j < 9) {
if (slots[i][j] == 0) {
int[] grid_posi = { i, j };
LinkedList<Integer> possible_values = value_generator
.possibleValuesInGrid(grid_posi, slots);
if ((possible_values.size() < least[2])
&& (possible_values.size() != 0)) {
least[0] = i;
least[1] = j;
least[2] = possible_values.size();
least_values = possible_values;
}
}
j++;
}
i++;
}
// 2 - work on the slot
if (least_values != null) {
for (int x : least_values) {
int[][] tempslot = new int[9][9];
ArrayDeepCopy(slots, tempslot);
tempslot[least[0]][least[1]] = x;
/*ConsoleInterface printer = new gameplay.ConsoleInterface();
printer.printGrid(tempslot);*/
int[][] possible_sltn = Solve(tempslot);
if (noEmptySlots(possible_sltn)) {
System.out.println("Solved");
return possible_sltn;
}
}
}
if (this.noEmptySlots(slots)) {
System.out.println("Solved");
return slots;
}
slots[0][0] = 0;
return slots;
}
I'm hoping to optimize my backtracking algorithm for my Sudoku Solver.
What it does now:
The recursive solver function takes a sudoku puzzle with various given values.
I will scour through all the empty slots in the puzzle, looking for the slot that has the least possibilities, and get the list of values.
From the list of values, I will loop through it by placing one of the values from the list in the slot, and recursively solve it, until the entire grid is filled.
This implementation still takes incredibly long for some puzzles and I hope to further optimize this. Does anyone have any ideas how I might be able to further optimize this?
Here's my code in Java if you're interested.
public int[][] Solve(int[][] slots) {
// recursive solve v2 : optimization revision
int[] least = new int[3];
least[2] = Integer.MAX_VALUE;
PuzzleGenerator value_generator = new PuzzleGenerator();
LinkedList<Integer> least_values = null;
// 1: find a slot with the least possible solutions
// 2: recursively solve.
// 1 - scour through all slots.
int i = 0;
int j = 0;
while (i < 9) {
j = 0;
while (j < 9) {
if (slots[i][j] == 0) {
int[] grid_posi = { i, j };
LinkedList<Integer> possible_values = value_generator
.possibleValuesInGrid(grid_posi, slots);
if ((possible_values.size() < least[2])
&& (possible_values.size() != 0)) {
least[0] = i;
least[1] = j;
least[2] = possible_values.size();
least_values = possible_values;
}
}
j++;
}
i++;
}
// 2 - work on the slot
if (least_values != null) {
for (int x : least_values) {
int[][] tempslot = new int[9][9];
ArrayDeepCopy(slots, tempslot);
tempslot[least[0]][least[1]] = x;
/*ConsoleInterface printer = new gameplay.ConsoleInterface();
printer.printGrid(tempslot);*/
int[][] possible_sltn = Solve(tempslot);
if (noEmptySlots(possible_sltn)) {
System.out.println("Solved");
return possible_sltn;
}
}
}
if (this.noEmptySlots(slots)) {
System.out.println("Solved");
return slots;
}
slots[0][0] = 0;
return slots;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
我的任务就是做到这一点：用 Java 构建最快的数独求解器。我最终以 0.3 毫秒的时间赢得了比赛。
我没有使用跳舞链接算法，也没有与之比较，但肯定有一些参赛者尝试过，但我最接近的竞争对手用了大约15毫秒。
我简单地使用了递归回溯算法，用 4 个“规则”对其进行了增强（这使得几乎每个谜题都不需要回溯），并保留一个位字段作为每个位置的合法值列表。
我写了一篇关于它的博客文章： http://byteauthor.com/2010/08/sudoku -solver/
并在此处发布代码： https://github.com/stonkie/SudokuSolverV1
I had an assignment to do just that: build the fastest sudoku solver in Java. I ended up winning the contest with a time of 0.3 millisecond.
I didn't use the dancing links algorithm and didn't compare with it, but some contestants must have tried it, yet my closest competitor took about 15 milliseconds.
I simply used a recursive backtracking algorithm, augmented it with 4 "rules" (which made backtracking unnecessary for almost every puzzle) and kept a bit field as a list of legal values for each position.
I wrote a blog post about it : http://byteauthor.com/2010/08/sudoku-solver/
And posted the code here : https://github.com/stonkie/SudokuSolverV1
我最近用 Python 编写了一个可以解决数独难题的程序。它基本上是一种回溯算法，会强力搜索空间。我在此线程中发布了有关实际算法的更多详细信息。
然而，在这里我想更多地关注优化过程。更准确地说，我探索了不同的方法来最小化求解时间和迭代次数。这更多的是关于可以进行的算法改进，而不是编程改进。
所以想一想，回溯蛮力算法中没有太多可以优化的东西（很高兴在这里被证明是错误的）。可以进行的两个真正的改进是：第一，选择下一个空白单元格的方法；第二，选择下一个可能的数字的方法。这两个选择可以决定是走一条死胡同的搜索路径，还是走一条以解决方案结束的搜索路径。
接下来，我坐下来尝试针对上述两种选择提出不同的方法。这就是我的想法。
可以通过以下方式选择下一个空白单元格：
这里表示从 1 到 9 的数字）
是来自同一行、同一列或同一 3x3 的一个
象限）
单元格中心点到单元格中心点）
选择
选择
下一个数字可以通过以下方式选择：
可用选项数
可用选项数
空白单元格
空白单元格
board
所以
我把上面的方法都编进了程序中。前面的数字和字母可以作为参数传递给程序，程序会采用相应的优化方法。此外，由于有时两个或更多单元格可能具有相同的分数，因此可以选择提供第二个排序参数。例如，参数“EC”意味着从具有最少可用选择的所有单元格中选择一个随机单元格。
第一个函数将分配乘以 1000 的权重，第二个函数将添加乘以 1 的新权重。因此，如果第一个函数中的三个单元格具有相同的权重，例如 3000、3000 3000，则第二个函数将添加其权重自己的体重。例如3111、3256、3025。排序将始终选择最低权重。如果需要相反的情况，则使用 -1000 amd -1 调用权重函数，但排序仍然选择最低权重。
在继续之前，值得一提的是，程序将始终选择一个空白单元格（而不是填充的单元格），并且始终选择单元格当前数独限制内的数字（否则这样做是不合理的）。
有了上述内容，我决定使用每种可能的参数组合运行程序，看看会发生什么，哪些表现最好 - 基本上是暴力破解:) 有 12 种单元格选择方法和 11 种数字选择方法所以理论上有17,424种组合可以尝试，但是我删除了一些不必要的组合（例如“AA”，“BB”等，并且还排除了随机方法，因为它们都非常低效），因此结果是 12,100。每次运行都是在同一个数独谜题上完成的，这是一个简单的谜题：
……搜索空间为 36,691,771,392。这只是给定谜题的每个空白单元格的选择数量的简单乘积。这是一种夸大其辞的说法，因为一旦一个单元格被填满，其他单元格的选择数量就会减少，但这是我能想到的最快、最简单的分数。
我编写了一个简短的脚本（当然是用 Python 编写的）来自动化整个测试过程 - 它为每组参数运行求解器，记录完成时间并将所有内容转储到文件中。另外，我决定每次运行 20 次，因为单次运行时，我从 time.time() 函数中得到了一些 0 次。而且，如果任何组合需要 10 秒以上才能完成，脚本就会停止并移至下一个。
该脚本在配备 Intel Core i7-4712MQ 2.30GHz 的笔记本电脑上于 13:04:31 小时内完成，使用的 8 个核心不超过 2 个，平均 CPU 负载约为 12%。 12,100 个组合中的 8,652 个在 10 秒内完成。
获胜者是：（* 根据单次运行时间/迭代调整数字）
1) 最快时间为 1.55 毫秒：
“A0”和“A1”具有 84 次迭代和 46 次回溯迭代
以及“B0”、“B01”、“B1”、“B10”、“BA01”、“BA1”、“BD01”、“BD1”和“BD10”，具有 65 次迭代和 27 次回溯迭代
最快的方法是最简单的方法，如A、B、D。另一种方法直到排名第308位才出现，那就是“E0”。
2) 最少迭代次数为 38 次和 0 次回溯迭代：
令人惊讶的是，许多方法都成功实现了这一目标，最快的方法是“B17”、“B6”、“B7”、“BA16”、“BA60”、“BA7”、“BD17”和“BD70”，时间为 2.3 毫秒，最慢的是“IK91”、“JK91”、“KI91”、“KJ91”、“KJ9a”、“IK9a”、“JK9a”和“KI9a”，时间约为 107 毫秒。
同样令人惊讶的是，方法 F 在这里有一些不错的位置，例如“FB6”，时间为 7 毫秒 (？？？)
总体而言，A、B、D、E、G 和 K 的性能似乎明显优于 C、F、H 和 L ，而 I 和 J 则介于两者之间。而且，数字的选择似乎并不重要。
最后，让我们看看这些获胜者方法如何处理世界上最难的数独难题，如本文所述 http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can- you-crack-it.html
* 考虑到算法并非普遍快速，也许某些算法在某些数独谜题上表现更好，但在其他数独谜题上则不然......
谜题是：
...搜索空间为 95,865,912,019,648,512 x 10^20。
获胜者是“A0”，以 1092 毫秒完成了 49,559 次迭代和 49,498 次回溯迭代。其他大多数人都做得不太好。 “A0”、“A1”、“B0”、“B01”、“B1”、“B10”、“BA01”、“BA1”、“BD01'、“BD1”和“BD10”在大约 2500 毫秒和 91k 内完成迭代，其余 30+ 秒，400k+ 迭代，
但这还不够，所以我也对最难的数独进行了所有参数集的完整测试，这次运行了 20 次，并且截止时间为该脚本在 8:23:30 内完成，12,100 个组合中有 149 个在 2.5 秒内完成。
两个类别的获胜者分别是“E36”、“E37”、“EA36”和“EA37”，时间为 109 毫秒，迭代次数为 362 次，回溯迭代次数为 301 次。此外，前 38 个位置均以“E”开头。
总体而言，E 名列榜首，只需查看汇总电子表格即可毫无疑问。 A、B、I、J 有几个名次，但没什么大不了的，其余的甚至一次都没有进入 2.5 秒以下。
总之，我认为可以肯定地说，如果数独谜题是一个简单的谜题，那么用最不复杂的算法对其进行暴力破解，但如果数独谜题是一个困难的谜题，那么值得花费选择方法的开销。
希望这有帮助:)
I recently wrote a program in Python that can solve a Sudoku puzzle. It is basically a backtracking algorithm which brute forces the search space. I have posted more details on the actual algorithm in this thread.
Here however I would like to focus more on the optimization process. To be more precise, I have explored different approaches to minimize the solve time and the number of iterations. And this is more about the algorithmic improvements that can be made, rather than the programming ones.
So having thought about it, there aren't many things in a backtracking brute force algorithm that can be optimized (happy to be proven wrong here). The two real improvements that can be made are: first, the method by which the next blank cell is chosen and second, the method by which the next possible digit is chosen. These two choices can make the difference between going down a dead-end searching path or going down a searching path that ends with a solution.
Next, I sat down and tried to come up with different methods for the aforementioned two choices. Here's what I came up with.
The next blank cell can be chosen in the following ways:
here means a digit from 1 to 9)
is one from the same row, from the same column or from the same 3x3
quadrant)
cell center point to cell center point)
choices
choices
And the next digit can be chosen in the following ways:
number of choices available
number of choices available
blank cells
blank cells
board
board
So I have programmed the above methods into the program. The preceding digits and letters can be passed as parameters to the program and it will use the corresponding optimization method. What's more, because sometimes two and more cells can have the same score, there is an option to provide a second sorting parameter. For example parameter "EC" would mean choose a random cell from all the cells that have the fewest choices available.
The first function will assign weights multiplied by 1000 and the second function will add new weights multiplied by 1. Thus, if for example from the first function three cells have the same weight, e.g. 3000, 3000 3000, then the second function will add its own weights. e.g. 3111, 3256, 3025. The sorting will always choose the lowest weight. And if the opposite is needed, then the weight functions are called with -1000 amd -1, but the sorting still chooses the lowest weight.
Before proceeding it's worth mentioning that the program will always choose a blank cell (not a filled one) and will always choose a digit that is within the current Sudoku constraints of the cell (doing otherwise is just so unreasonable).
Having the above, I then decided to run the program with every possible combination of parameters and see what happens, which ones perform the best - basically to brute force the brute force :) There are 12 methods for cell choosing and 11 methods for digit choosing so in theory there are 17,424 combinations to try, but I removed some unnecessary ones (such as "AA", "BB", etc., and also excluded the random methods as they are all terribly inefficient), so the number of combinations in the end was 12,100. Each run was done on the same Sudoku puzzle, which is an easy one:
...and the search space is 36,691,771,392. This is just a simple product of the number of choices for each blank cell of the given puzzle. It is an overstatement because as soon as one cell is filled this reduces the number of choices for other cells, but it is the fastest and easiest score I could come up with.
I wrote a short script (in Python of course) that automated the whole process of testing - it ran the solver for each set of parameters, recorded the completion time and dumped everything into a file. Also, I decided to do 20 runs of each because I was getting some 0 times from the time.time() function for single runs. And also, if any combination took more than 10 seconds to complete, the script would stop and move to the next one.
The script completed in 13:04:31 hours on a laptop with Intel Core i7-4712MQ 2.30GHz, no more than 2 out of 8 cores were being used and the average CPU load was about 12%. 8,652 out of the 12,100 combinations completed in under 10 seconds.
And the winners are: (* numbers adjusted back for single run times/iterations)
1) Fastest time of 1.55 ms:
"A0" and "A1" with 84 iterations and 46 backtrack iterations
and "B0", "B01", "B1", "B10", "BA01", "BA1", "BD01", "BD1" and "BD10" with 65 iterations and 27 backtrack iterations
The fastest methods are the simplest ones like A, B and D. Another method does not appear until ranking position 308, and that is "E0".
2) Fewest iterations of 38 and 0 backtrack iterations:
Surprisingly many methods managed to achieve this, the fastest ones being "B17", "B6", "B7", "BA16", "BA60", "BA7", "BD17" and "BD70" with time of 2.3 ms and the slowest ones being "IK91", "JK91", "KI91", "KJ91", "KJ9a", "IK9a", "JK9a" and "KI9a" with time of about 107 ms.
Also surprisingly, method F has a few good positions here such as "FB6" with 7 ms (???)
Overall A, B, D, E, G and K seemed to perform significantly better than C, F, H, and L, and I and J are kinda in between. Also, the choice of digit didn't seem to matter much.
And finally, let's see how these winner methods handle the world's hardest Sudoku puzzle, as claimed by this article http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html
* Having in mind that algorithms are not universally fast, maybe some algorithms do better on some Sudoku puzzles, but not on others...
The puzzle is:
...and the search space is 95,865,912,019,648,512 x 10^20.
The winner is "A0" finishing in 1092 ms with 49,559 iterations and 49,498 backtrack iterations. Most of the other ones didn't do very well. "A0", "A1", "B0", "B01", "B1", "B10", "BA01", "BA1", "BD01', "BD1" and "BD10" finished in about 2500 ms and 91k iterations, and the rest 30+ seconds, 400k+ iterations.
But that's not enough so I ran a full test of all set of parameters for the hardest Sudoku too. This time doing a single run not 20, and also a cut-off time of 2.5 seconds. The script completed in 8:23:30 hours. 149 out of the 12,100 combinations completed in under 2.5 seconds.
The winners in both categories are "E36", "E37", "EA36" and "EA37" with time of 109 ms, 362 iterations and 301 backtrack iterations. Also, the first 38 positions were dominated with by a beginning "E".
Overall E tops the charts, no doubt about it just by looking at the summary spreadsheet. A, B, I and J have a few rankings but nothing much and the rest did not even make it once under 2.5 seconds.
In conclusion, I think it is safe to say that if the Sudoku puzzle is an easy one then brute force it with the least complex algorithm, but if the Sudoku puzzle is a hard one then it's worth spending the overhead of the choosing methods.
Hope this helps :)
很长一段时间我写了一个数独求解器（几年前，但我保留了我写的所有代码）。它尚未被推广到解决比通常的数独“更大”的问题，但它的速度相当快。
它在 103 毫秒内解决了以下问题（在 Core 2 Duo 1.86 Ghz 上），并且实际上尚未优化：
您的速度有多快以及在哪块板上速度较慢？你确定你不会不断地重走不该重走的路吗？
这是算法的核心内容：
IPlatform 抽象（请客气一点，它是很多年前写的，当时我才知道在 Java 中在接口名称之前添加“I”并不流行）：
a long time I wrote a Sudoku solver (several years ago, but I keep all the code I write). It hasn't been generalized to solve "bigger" size than the usual Sudoku, but it is pretty fast.
It solves the following in 103 ms (on a Core 2 Duo 1.86 Ghz) and really hasn't been optimized:
How fast is yours and on which board is it slow? Are you sure you're not constantly revisiting path that shouldn't be revisited?
Here's the meat of the algo:
And the IPlatform abstraction (please be nice, it was written a lot of years ago, before I knew that in Java adding 'I' before interface names wasn't all the rage):
不久前，我用 Ruby（一种不太高效的语言）实现了 Donald Knuth 的 Dancing Links 和他的数独算法 X。对于我检查的几个示例，在我的 1.5 GHz 笔记本电脑上花费了几毫秒。
您可以查看维基百科“跳舞链接”的工作原理，并自行将其改编为数独。或者你看看 "A Sudoku Solver in Java Implementing Knuth 的跳舞链接算法”。
PS：算法X是一种回溯算法。
A while ago I implemented Donald Knuth's Dancing Links and his Algorithm X for Sudoku in Ruby (a language not known to be too efficient). For the few examples I checked, it took few milliseconds on my 1.5 GHz laptop.
You can look at the wikpedia how the Dancing Links work, and adapt it to Sudoku yourself. Or you take a look at "A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm".
PS: Algorithm X is a backtracking algorithm.
我认为一个很大的优化不仅是保留棋盘的状态，而且还保留每行/列/方格的状态（如果它包含数字 1-9 中的每个数字）。现在要检查一个位置是否可以有一个数字，您只需检查该位置所在的行/列/方格是否不包含该数字（这只是 3 个数组查找）。
此外，为每个递归调用创建一个新数组也会造成很大的速度损失。不要这样做，而是在递归调用之前对数组进行更改，然后在递归调用之后撤消它。基本上添加一个不变量，即 Solve 将在运行时更改插槽，但当它返回时，它将保持调用函数时的状态。
另外，每次解决返回时，您都必须检查棋盘是否已解决。如果solve没有找到解决方案，它应该只返回null，如果找到解决方案，它应该返回该解决方案。这样你就可以快速测试你的递归调用是否找到了解决方案。
在选项最少的方格中放置一个数字真的有帮助吗？如果没有它，代码会简单得多（您不必将内容保存在链接列表等中）
这是我的伪代码：
这是我的代码（我还没有测试过）：
I think a big optimization would be to keep not only the state of the board, but for each row/col/square if it contains each of the numbers 1-9. Now to check if a position can have a number you simply need to check if the row/col/square the position is in don't contain that number (which is just 3 array lookups).
Also a big speed loss has to be making a new array for each recursive call. Instead of doing this make the change in the array before the recursive call, then undo it after the recursive call. Basically add the invariant that Solve will change slots while it runs, but when it returns it will leave it as it was when the function was called.
Also every time solve returns you have to check if the board is solved or not. If solve doesn't find a solution it should just return null, if it finds a solution it should return that. This way you can quickly test if your recursively call to solve found a solution or not.
Does placing a number in the square with the fewest options really help? Without that the code is a lot simpler (you don't have to save things in linked lists etc.)
Here is my psuedo code:
Here is my code (I haven't tested it):
在每个不确定步骤之前进行一些约束传播。
在实践中，这意味着您有一些规则可以检测强制值并插入它们，并且只有当这不再取得进展时，您才会通过可能的值进行回溯搜索。
大多数人类数独谜题的设计根本不需要回溯。
Do some constraint propagation before each nondeterministic step.
In practice this means that you have some rules which detect forced values and inserts them, and only if this doesn't make progress any more you resort to backtracking search through possible values.
Most Sudoku puzzles for humans are designed so that they don't need backtracking at all.
找到具有最少可能解决方案的老虎机的成本非常昂贵，对于传统的数独谜题来说可能不值得花费这些费用。
一种更简单的优化是跟踪每个数字已使用了多少个，当您“尝试”将数字放入插槽中时，从使用最少的数字开始（编辑：确保包括那些数字）该谜题已播种）。这将使您的算法更有可能走上一条成功的道路，而不是一条失败的道路。
另外，请按照 Imsasu 的建议查看人工智能：现代方法。这是一本很棒的书，详细介绍了递归回溯。
PS 我很好奇“第一步”优化带来的性能提升（如果有的话）。你有身材吗？
Finding the slot with the least possible solutions is incredibly expensive, and for a traditional Sudoku puzzle probably isn't worth the overhead.
An easier optimization is to keep track of how many of each digit has been used, and when you "try" to place a digit in a slot, start with the one that has been used the least (edit: make sure to include the ones the puzzle was seeded with). This will make your algorithm more likely to start down a successful path rather than a failed one.
Also, do check out Artificial Intelligence: A Modern Approach as suggested by Imsasu. It is a fantastic book and covers recursive backtracking in good detail.
P.S. I'm curious as to the performance gains (if any) given by your "step 1" optimization. Do you have a figure?
我对数独回溯算法的优化结果如下。您可以从 http://yikes.com/~bear/suds.c 下载代码。这纯粹是基于鸽子洞原理，我发现它通常比基于规则的求解更快。
使用此线程上另一篇文章中的值，我在 core2 duo @2.2 ghz 上得到 7ms 的结果，在 core i5 上得到 3ms 的结果。这与海报的 100 毫秒结果进行了比较，尽管这可能是通过不同的方式测量的。 http://yikes.com/~bear/suds2.c 中添加了计时。
这是我 10 年前写的，如果我重做这个问题，肯定会以不同的方式进行优化。
The results from my optimizations of the backtracking algorithm for Sudoku are below. You can download the code from http://yikes.com/~bear/suds.c. This is purely based on pigeon hole principle and I found it to generally be faster than rules based solving.
Using the values from another post on this thread I get a result of 7ms on a core2 duo @2.2 ghz or 3ms on a core i5. This compares to the poster's result of 100ms, although that may have been measured in a different way. Timing added in http://yikes.com/~bear/suds2.c.
I wrote this 10 years ago, and would certainly optimize in a different way if I re-did this problem.
您可能应该使用分析器来查看哪个语句花费的时间最多，然后考虑如何优化它。
如果不使用探查器，我的建议是您每次都从头开始创建一个新的 PuzzleGenerator，并将槽作为参数传递给 possibleValuesInGrid 方法。我认为这意味着 PuzzleGenerator 每次都会从头开始重新计算每个位置和每个插槽配置的所有内容；相反，如果它记住以前的结果并逐步改变，它可能会更有效。
You should probably use a profiler to see which statement is taking the most time, and then think about how to optimize that.
Without using a profiler, my suggestion is that you're creating a new PuzzleGenerator from scratch each time, and passing slots as an argument to the possibleValuesInGrid method. I think that means that PuzzleGenerator is recalculating everything from scratch each time, for each position and for each slots configuration; whereas instead it might be [much] more efficient if it remembered previous results and changed incrementally.