暴力数独求解器：回溯？
用于解决数独谜题的暴力算法的实现，如果单元格失败发现放置 1-9 中的任何数字都是非法的。
该实现是用 C 编写的，棋盘由 9x9 数组表示。求解器从 9 开始倒数，直到达到合法数字，如果没有达到，则在其位置输出零。
零还代表要填充的单元格。如果输入一串零（空板），则以下是输出（截断）：
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
最后三个零存在，因为之前填充的值没有更改。 如何我怎样才能阻止求解器出现这样的失败？
An implementation of a brute-force algorithm to solve Sudoku puzzles fails if a cell is discovered in which placing any of the digits 1-9 would be an illegal move.
The implementation is written in C, with the board represented by a 9x9 array. The solver counts down from 9 until a legal number's reached, and if none can be reached, it outputs a zero in its place.
A zero also represents a cell to be filled in. Here's the output (truncated) if a string of zeros (an empty board) is the input:
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
Those last three zeros are there because the values filled in previously aren't changing. How can I stop the solver from failing like this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您当前在某个位置输入了零，请返回到您输入数字的上一个位置并继续倒计时，直到找到该位置的另一个值数字。
例如，在您的示例中：
您不会将零放在 3 的下面，而是返回并尝试将 6 放在 4 的下面。
If you would currently put a zero in a spot, instead go back to the previous spot you put a number in and continue to count down till you find another value number for that spot.
For instance, in your example:
Instead of putting the zero in below the three, you would instead go back and try putting a 6 in below the 4.
不要将每一个“举动”都视为正确的举动。例如，放置最后 7 个似乎没问题，但会导致下一个单元格中没有留下有效的移动。因此，一旦遇到“无法移动”的情况，请返回并尝试下一个选项。迭代，你就会得到你的解决方案。
当然，更好的方法是对剩下少量选项的地方开始暴力破解；遍历所有单元格，并对剩余选项数量最少的单元格开始暴力破解。当从全零开始时，您最终会得到
合法的结果，而无需回溯一次。
don't treat every "move" like the right move. E.g. placing the last 7 seemed ok but makes it so that in the next cell no valid moves are left. So upon hitting the "no move possible" situation, go back, and try the next option. Iterate and you will have your solution.
A better way of course would be to start brute forcing for places with a small set of options left; run through all cells and start brute forcing with the cell with the least number of options left. When starting out with all-zero, you would then end up with
which is legal, without backtracking once.
您可以通过将您的猜测压入堆栈来完成此操作。每次您最终想要输出零时，请将最后一个答案从黑板上弹出并继续从中计数。
因此，如果您在 (2,3) 中猜测 3，接下来您查看 (3,3) 并得到零，请返回到 (2,3) 并尝试 2，然后是 1，然后弹出到 (2 ,3) 猜测等。
You can do this by pushing your guesses onto a stack. Every time you end up wanting to output a zero, instead pop your last answer off the board and continue counting from it.
So if you guess 3 in (2,3) and next you're looking at (3,3) and get to zero, go back to (2,3) and try 2, then 1, then pop to before your (2,3) guess, etc.