应用A *数独的启发式功能 [英] Heuristic function for applying A* sudoku

问题描述

我需要一个好的启发式函数来解决数独问题。
sudoku网格为4X4，根据定义，每个州的合法操作是在下一个空闲单元格中插入一个新数字（顺序为从左到右，从上到下）。 / p>

例如，这是输入网格：

，现在我们应该填充单元格（1,2）。

所有节点都是代表不同网格的网格不同的状态。
分支因子为4，因此下一个单元格有4种可能性：1、2、3或4，即每个节点4个子代。

如何在节点上定义启发式函数以在网格上应用A *？

我可以想想是：

如果插入到当前州网格中的新数字不合法（=在同一行，列或框中多次出现），那么h （n）=无限。

  else，h（n）= [空的剩余单元格数]。 
  

我认为我的解决方案是不正确的，因为两个节点之间的启发式值没有区别

解决方案

一个启发式函数是选择约束最大的单元格。

例如在您的示例中，您可以选择（2,3） =>，因为它只有一种适合的可能性（最大约束数量）。进行下注（放置数字）后，可以继续使用相同的策略=>放置 S [2,3] = 2 =>选择 S [2,2] ，依此类推。

受约束，我的意思是每个单元格有多少个选项，考虑到数独规则中的限制。

h [cell] = 1 /（＃每个框的选项+每行的选项+＃选项每个
列）

尽管这是一个非常简单的策略（一个前瞻性选择），但是更复杂的策略会将这个策略组合成高阶逻辑=>基本上是：

h2 [cell] = h [cell-left] + h [ cell-right] + ...;

I need a good heuristic function for A star for sudoku solving. The sudoku grid is 4X4 and by definition the legal operation from each state is to insert a new number to the next free cell (the order is left to right and up to down).

for example, this is the input grid:

and we should now fill the cell (1,2).

All the nodes are different grids that represents different states. The branching factor is 4, so we have 4 possibilities for the next cell:1, 2, 3 or 4, i.e. 4 children for each node.

How can I define heuristic function on the nodes for applying A* on the grid?

All I can think of is:

if the new number that was inserted to the current state's grid is illigal (= appears more than once in the same row, column or box) so h(n)= infinity.

else, h(n)= [number of empty remain cells].

I think that my solution is not correct because there is no difference in the heuristic value between two nodes in the same level that are legal.

解决方案

One heuristic function would be to pick the cell that has the maximum number of constraints on it.

E.g. in your example, you could pick (2,3) => since it has only one possibility to fit (max # of constraints). After you've made a "bet" (placed a number), you could continue with the same strategy => place S[2,3] = 2 => pick S[2,2] and so on.

By constraints, I mean how many options do you have per cell, given the constraints in Sudoku rules.

h[cell] = 1/(#options per box + #options per row + #options per column)

This is a very simple strategy though (one look-ahead option), but more complex strategies would be to combine this strategy into higher-order logic => basically:

h2[cell] = h[cell-left]+h[cell-right]+...;

这篇关于应用A *数独的启发式功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！