构建高效的数独求解器 [英] Building an EFFICIENT Sudoku Solver

问题描述

是的，我知道这不是什么新鲜事，而且已经有很多问题(它甚至有自己的标签)，但我想用 Java 创建一个数独求解器，仅用于训练自己编写代码的目的这样效率更高.

Yes, I know this is nothing new and there are many questions already out there (it even has its own tag), but I'd like to create a Sudoku Solver in Java solely for the purpose of training myself to write code that is more efficient.

在程序中执行此操作的最简单方法可能是通过大量 for 循环解析每一列和每一行，收集每个单元格的可能值，然后仅清除一种可能性的单元格(无论它们是否仅包含 1数字，或者它们是行/列中唯一包含此数字的单元格)，直到您解决了难题.当然，对这个动作的纯粹想法应该在每个程序员的脑海中升起一个危险信号.

Probably the easiest way to do this in a program is have a ton of for loops parse through each column and row, collect the possible values of each cell, then weed out the cells with only one possibility (whether they contain only 1 number, or they're the only cell in their row/column that contains this number) until you have a solved puzzle. Of course, a sheer thought of the action should raise a red flag in every programmer's mind.

我正在寻找以最有效的方式解决这个问题的方法(请尽量不要包含太多代码 - 我想自己弄清楚那部分).

What I'm looking for is the methodology to go about solving this sucker in the most efficient way possible (please try not to include too much code - I want to figure that part out, myself).

如果可能的话，我想避免使用数学算法——这些算法太简单了，而且 100% 不是我的工作.

I want to avoid mathematical algorithms if at all possible - those would be too easy and 100% not my work.

如果有人能提供解决数独谜题(无论是人工还是计算机)的逐步、高效的思考过程，我会非常高兴:).我正在寻找一些模糊的东西(所以这是一个挑战)，但信息量足够(所以我没有完全迷失)让我开始.

If someone could provide a step-by-step, efficient thought process for solving a Sudoku puzzle (whether by a human or computer), I would be most happy :). I'm looking for something that's vague (so it's a challenge), but informative enough (so I'm not totally lost) to get me started.

非常感谢，

贾斯汀迈耶

看着我的代码，我开始思考:存储这些求解状态(即数独网格)有哪些可能性.2D 阵列和 3D 阵列浮现在脑海中.哪个可能最好?2D 可能更容易从表面进行管理，但 3D 阵列也会提供盒子"/笼子"编号.

Looking at my code, I got to thinking: what would be some of the possibilities for storing these solving states (i.e. the Sudoku grid). 2D Arrays and 3D Arrays come to mind. Which might be best? 2D might be easier to manage from the surface, but 3D Arrays would provide the "box"/"cage" number as well.

没关系.我要使用 3D 阵列.

Nevermind. I'm gonna go with a 3D array.

推荐答案

这取决于你如何定义高效.

It depends on how you define efficient.

您可以使用蛮力方法，搜索每一列和每一行，收集每个单元格的可能值，然后仅清除一种可能性的单元格.

You can use a brute force method, which searches through each column and row, collects the possible values of each cell, then weeds out the cells with only one possibility.

如果剩余的单元格具有多种可能性，请保存拼图状态，选择具有最少可能性的单元格，选择其中一种可能性，然后尝试解决拼图.如果您选择的可能性导致拼图矛盾，则恢复保存的拼图状态，返回单元格并选择不同的可能性.如果您选择的单元格中的所有可能性都无法解决难题，请选择具有最少可能性的下一个单元格.循环浏览剩余的可能性和单元格，直到你解决了这个难题.

If you have cells remaining with more than one possibility, save the puzzle state, pick the cell with the fewest possibilities, pick one of the possibilities, and attempt to solve the puzzle. If the possibility you picked leads to a puzzle contradiction, restore the saved puzzle state, go back to the cell and choose a different possibility. If none of the possibilities in the cell you picked solves the puzzle, pick the next cell with the fewest possibilities. Cycle through the remaining possibilities and cells until you've solved the puzzle.

尝试解决这个难题意味着搜索每一列和每一行，收集每个单元格的可能值，然后只筛选出一种可能性的单元格.当所有细胞都被清除时，你就解决了这个难题.

Attempt to solve the puzzle means searching through each column and row, collecting the possible values of each cell, then weeding out the cells with only one possibility. When all of the cells are weeded out, you've solved the puzzle.

您可以使用逻辑/数学方法，让您的代码尝试不同的策略，直到解开谜题.使用数独策略"在 Google 上搜索以查看不同的策略.使用逻辑/数学方法，您的代码可以解释"谜题是如何解决的.

You can use a logical / mathematical method, where your code tries different strategies until the puzzle is solved. Search Google with "sudoku strategies" to see the different strategies. Using logical / mathematical methods, your code can "explain" how the puzzle was solved.

这篇关于构建高效的数独求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！