java – 递归回溯何时适用?
我正在为一个类创建一个SudokuSolver,我在解决方法上遇到麻烦.我目前的解决方案使用递归回溯(我认为).
作业要求
(上述策略)
心理思想 我可以迭代地跟随一个小的输入.例如,说我必须未解决的单元格#1和单元#2. #1有可能{1,3}和#2有可能{2,3}.我会的 set 1 to 1 set 2 to 2 hasConflicts? 0 : 1 set 2 to 3 hasConflicts? 0 : 1 set 1 to 3 set 2 to 2 hasConflicts? 0 : 1 set 2 to 3 hasConflicts? 0 : 1 实际代码 public int solve() { long startTime = System.currentTimeMillis(); int result = 0; if (!hasConflicts()) { Queue<VariableCell> unsolved = getUnsolved(); reduceUnsolvedPossibilities(unsolved); // Gets the possibilities down from all of 1-9 if (!hasConflicts()) { result = solveRec(unsolved); } } mElapsedTime = System.currentTimeMillis() - startTime; return result; } protected int solveRec(Queue<VariableCell> unsolved) { if (unsolved.isEmpty()) { return (hasConflicts()) ? 0 : 1; } int result = 0; VariableCell cell = unsolved.remove(); Iterator<String> possibilityIt = cell.getPossibilities().iterator(); while (possibilityIt.hasNext()) { cell.setSymbol(possibilityIt.next()); if (hasConflicts()) { possibilityIt.remove(); } else { ++result; } } return result + solveRec(unsolved); } 检测结果 testSolveSingleSolution expected 1,actual 1 testSolveSolved expected 1,actual 1 testSolveUnsolvable expected 0,actual 0 testSolveMultiSolutions expected 2,actual 7 // MAJOR PROBLEM! 递归回溯的一些很好的解释 > This answer to StackOverflow – Sudoku发生器的递归解决方案 题 我之前已经进行了递归回溯,我已经看过上面的所有链接,我仍然有麻烦.我认为问题在于我如何解决这个问题. (参见Psudeocode Idea.)是否适合使用递归回溯进行详尽的搜索?追溯权是否正确执行错误?我可以使用比递归回溯更好的算法吗?先谢谢了! 解决方法
这看起来像一个实现问题.检查块的结果增加.你真的要增加那个单元格的每个有效值吗?如果有几个有效值,那么覆盖旧的有效值呢?
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |