Drools4：对Sudoku示例的分析

hxpwork

浏览: 111692 次
性别:
来自: 广州

最近访客更多访客>>

老魔杖

bjliuming

ticky998

powerrliu

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (35)

社区版块

存档分类

游戏 C C++C#数据挖掘

/*
Sodu：数独游戏，一个9x9的方格棋盘中，按照每三行三列再细分为9个小棋盘,如下
|a|a|a|b|b|b|c|c|c|
|a|a|a|b|b|b|c|c|c|
|a|a|a|b|b|b|c|c|c|
|d|d|d|e|e|e|f|f|f|
|d|d|d|e|e|e|f|f|f|
|d|d|d|e|e|e|f|f|f|
|g|g|g|h|h|h|i|i|i|
|g|g|g|h|h|h|i|i|i|
|g|g|g|h|h|h|i|i|i|
其中a,b...i分别代表大棋盘中的9个小棋盘，规则是：
1、使用1-9，九个数字填入字母a-i所在位置
2、大棋盘上的每一行，每一列都不能有重复数字
3、小棋盘上也不能有重复的数字
数独游戏实际上是一个推理游戏，与数字计算无关；首先会随机产生一些数字在棋盘上，然后游戏者完成剩下的填空
数独游戏通常会在棋盘上事先准备好一些数字，然后由游戏者完成剩下的格子。
如何使用规则引擎完成这一任务呢？
--首先我们要对Drools这种正向推理性的引擎有一个认识前提，就是它是基于数据进行规则推导的，
也就是说如果需要规则引擎帮你找到结果，那首先必须将所有可能的结果都准备好。
这一方法在Golfer球员排序时也使用过，当时是将所有球员组合情况都放到引擎中，由引擎自己找出答案。
那么现在我们第一步要做的就是在所有未确定数据的空格子位置上准备所有可能的结果，也就是在那里放上从1-9的数字，最后由引擎自己挑选。
现在我们在每个空格子里面都准备好了数据，那么下面就是要将格子中无关的数据去掉，如果剩下一个，那显然就是答案了。
要如何去掉格子中无效的数据呢？那显然就是要遵循行、列、区域中都不能有重复数字的规则了。
设想一下，获得某一行上有数据的格子，那么空格子中与这些格子的数据显然就不能重复，这样就可以排除掉无用的数据。
依次类推，在列与区域中也进行这样的检查，那么最终会有空格子的可选数据会只剩一个，此时就将该可选数据转换为正式数据，
同时又会引发新的筛选，进一步减少可选值。
但是这样的规则够了吗？从实际效果上看显然是不够的，因为在很多情况下，这样的规则并不能确定所有格子的值，还需要继续的挖掘潜在的规则。
从游戏的原则中我们又可以推导从下面的规则：
如果在一个区域/行/列内，某一个空格子上的可选值在这个区域/行/列里是唯一的，并且不会违反行列区域已有数字冲突的原则，那么该可选值就是格子真正的数字。
采用了这个规则后，大部分的格子可以完成推导，有时甚至可以完成全部格子推导，但是仍然存在不可以得到结果的情况。
或许对于数学非常精通的程序员，可以通过数学定理推导规则是否可以满足所有情况，但是作为大多数人，多测试是唯一的办法。
这也提醒我们，使用规则引擎解决复杂推理问题时，一定要多想多测试，并尽可能找到显式规则以及所有的潜在规则，
宁多勿缺，只要规则正确，最多就是走走弯路，好过没有完成任务！
最后我们再找到一组潜在的规则
如果在区域中有两个格子都只剩两个可选值，并且这两个可选值一样的情况下，显然这两个格子只能是这两个可选值中的一个；
这时删除区域中其它空格子中相同的可选值。
*/

Fact 插入

StatefulSession session = null;
try {
Collection fields = new ArrayList();
// 对于数独阵列中的每一个格子有4个属性：数字，行，列，区域
// 下面就是根据这四个属性建立Fact数据，顺便将每一行数据打印出来
for ( int i = 0; i < field.length; i++ ) {
String row = "{";
for ( int j = 0; j < field[i].length; j++ ) {
row += field[i][j] + ",";
fields.add( new Field( "" + field[i][j],
j + 1,
i + 1,
getZone( i,
j ) ) );
}
row += "}";
System.out.println( row );
}
// 启动规则引擎
RuleBase ruleBase = readRule();
session = ruleBase.newStatefulSession();
// 将每一个Field实例插入WorkingMemory，同时保存FachHandle
Iterator iter = fields.iterator();
Collection handles = new ArrayList();
while ( iter.hasNext() ) {
handles.add( session.insert( iter.next() ) );
}
session.fireAllRules();
System.out.println( "Size: " + iteratorToList( session.iterateObjects() ).size() );
// 完成计算以后将数据写回阵列
iter = session.iterateObjects();
//Copy the values of the fields into the matrix
while ( iter.hasNext() ) {
Object next = iter.next();
if ( next instanceof Field ) {
field[((Field) next).getRow() - 1][((Field) next).getColumn() - 1] = Integer.parseInt( ((Field) next).getValue() );
}
}
// 打印结果
for ( int i = 0; i < field.length; i++ ) {
String row = "{";
for ( int j = 0; j < field[i].length; j++ ) {
row += field[i][j] + ",";
}
row += "}";
System.out.println( row );
}
} catch ( Throwable t ) {
t.printStackTrace();
} finally {
if ( session != null ) {
session.dispose();
}
}

规则

# 首先将所有数字为0的格子删除，并对这个格子插入从1-9的所有可能情况
rule "Rule 1: If a field has the value 0, it is empty: remove it and insert the PossibleValues"
salience 100
when
$field : Field( value == 0, $row : row, $column : column, $zone : zone )
then
insert( new PossibleValue("1", $field ) );
insert( new PossibleValue("2", $field ) );
insert( new PossibleValue("3", $field ) );
insert( new PossibleValue("4", $field ) );
insert( new PossibleValue("5", $field ) );
insert( new PossibleValue("6", $field ) );
insert( new PossibleValue("7", $field ) );
insert( new PossibleValue("8", $field ) );
insert( new PossibleValue("9", $field ) );
// 插入完毕后删除Field，因为该Field中的数据不是我们所需要的，
// 我们需要的只是它的位置信息，而这些是不变的，已经在PossibleValue初始化时保留。
retract( $field );
#System.out.println("Rule 1 fired.");
end
# 这个规则是当某一个格子上的PossibleValue只剩下一个时，那么这个PossibleValue的值就是要寻找的值
rule "Rule 2: If there is one PossibleValue left at a certain position, it should be the Fields value"
salience 5
when
$pv : PossibleValue ( $row : row, $zone : zone, $column : column, $value : value )
not ( PossibleValue ( row == $row, zone == $zone, column == $column, value != $value ) )
then
insert( new Field( $value, $column, $row, $zone ) );
System.out.println ( "Field be found in row="+$row+";col="+$column+"value="+$value );
retract( $pv );
#System.out.println("Rule 2 fired.");
end
# 获得行中已确定的数字，将该行上空格子中的相同备选数字删除
rule "Rule 3: If there is a field with a value in a row, remove all PossibleValues with this value in this row"
salience 15
when
$field2 : Field( $row : row, $value : value != 0 )
$possible : PossibleValue( row == $row, value == $value )
then
retract( $possible );
#System.out.println("Rule 3 fired.");
end
# 获得列中已确定的数字，将该列上空格子中的相同备选数字删除
rule "Rule 4: If there is a field with a value in a column, remove all PossibleValues with this value in this column"
salience 15
when
$field1 : Field( $column : column, $value : value != 0 )
$possible : PossibleValue( column == $column, value == $value )
then
retract( $possible );
#System.out.println("Rule 4 fired.");
end
# 获得区域中已确定的数字，将该区域上空格子中的相同备选数字删除
rule "Rule 5: If there is a field with a value in a zone, remove all PossibleValues with this value in this zone"
salience 15
when
$field1 : Field( $zone : zone, $value : value != 0 )
$possible : PossibleValue( zone == $zone, value == $value )
then
retract( $possible );
#System.out.println("Rule 5 fired.");
end
# 一旦产生新的格子数字，则删除在这个格子上的所有可选值
# Rule 2,3,4,5 不会引起该规则的调用，因为这几个规则是将其它可选值删除后剩余的值设为格子数字。
# 该规则是由Rule 7，8，9激发的
rule "Rule 6: For fields with a value remove all PossibleValues"
salience 250
when
Field( value != 0, $col : column, $row : row, $zone : zone )
$pv : PossibleValue( column == $col, row == $row, zone == $zone )
then
retract( $pv );
#System.out.println("Rule 6 fired.");
end
# 如果在一个小区域内，某一个空格子上的可选值在这个区域里是唯一的
# 并且不会违反行列区域数字冲突的原则，那么该可选值就是格子真正的数字
rule "Rule 7: If there is only one PossibleValue left in a zone, it must have the value of the field"
salience 4
when
$pv : PossibleValue( $zone : zone, $value : value, $col : column, $row : row)
not (PossibleValue( zone == $zone, value == $value ))
not (Field( value == $value, zone == $zone) )
not (Field( value == $value, row == $row) )
not (Field( value == $value, column == $col) )
then
insert( new Field( $value, $col, $row, $zone ) );
retract( $pv );
#System.out.println("Rule 7 fired.");
end
# 如果在一列上，某一个空格子上的可选值在这个列上是唯一的
# 并且不会违反行列区域数字冲突的原则，那么该可选值就是格子真正的数字
rule "Rule 8: If there is only one PossibleValue left in a column, it must have the value of the field"
salience 4
when
$pv1 : PossibleValue( $zone : zone, $value : value, $col : column, $row : row)
not (PossibleValue( column == $col, value == $value ))
not (Field( value == $value, zone == $zone) )
not (Field( value == $value, row == $row) )
not (Field( value == $value, column == $col) )
then
insert( new Field( $value, $col, $row, $zone ) );
retract( $pv1 );
#System.out.println("Rule 8 fired.");
end
# 如果在一行上，某一个空格子上的可选值在这个行上是唯一的
# 并且不会违反行列区域数字冲突的原则，那么该可选值就是格子真正的数字
rule "Rule 9: If there is only one PossibleValue left in a row, it must have the value of the field"
salience 4
when
$pv : PossibleValue( $zone : zone, $value : value, $col : column, $row : row)
not (PossibleValue( row == $row, value == $value ))
not (Field( value == $value, zone == $zone) )
not (Field( value == $value, row == $row) )
not (Field( value == $value, column == $col) )
then
insert( new Field( $value, $col, $row, $zone ) );
retract( $pv );
#System.out.println("Rule 9 fired.");
end
# 如果在一个区域中的两个空格子只剩两个可选值，则删除该区域中与这两个可选值相同的其它可选值
rule "Rule 10: If there are two fields with only two possible values, remove the PossibleValues for the same Value in the rest of the zone"
salience 1
when
# 找到一个可选值A
PossibleValue( $zone : zone, $val1 : value, $row1 : row, $col1 : column )
# 要求在相同区域中，不同列上具有与A数字相同的可选值C
PossibleValue( zone == $zone, value == $val1, $row2 : row, $col2 : column != $col1)
# 要求与A在同一个格子里有其它可选值B
PossibleValue( zone == $zone, row == $row1, column == $col1, $val2 : value )
# 要求在C的格子里有与B的数字相同的可选值
PossibleValue( zone == $zone, row == $row2, column == $col2, value == $val2 )
# 要求在A格子中不存在除A与B的数字以外的可选值，也就是说A格子中的可选值不超过两个
not ( PossibleValue( zone == $zone, row == $row1, column == $col1, value != $val1, value != $val2 ) )
# 要求在C格子中不存在除A与B的数字以外的可选值，也就是说C格子中的可选值不超过两个
# 这两个not条件组合起来要表达的就是区域中有A，C两个格子中的可选值一样，并且只有两个
not ( PossibleValue( zone == $zone, row == $row2, column == $col2, value != $val1, value != $val2 ) )
# 获得区域中与A数字相同的其它可选值
$pv : PossibleValue( zone == $zone, value == $val1)
then
retract( $pv );
#System.out.println("Rule 10 fired.");
end
# 如果在一个区域中的两个空格子只剩两个可选值，则删除该区域中与这两个可选值相同的其它可选值
# 本规则与上一规则基本一样区别是寻找C格子时使用不同行而不是不同列
rule "Rule 11: If there are two fields with only two possible values, remove the PossibleValues for the same Value in the rest of the zone"
salience 1
when
PossibleValue( $zone : zone, $val1 : value, $row1 : row, $col1 : column )
# 本行与规则10不同
PossibleValue( zone == $zone, value == $val1, $row2 : row != $row1, $col2 : column)
PossibleValue( zone == $zone, row == $row1, column == $col1, $val2 : value )
PossibleValue( zone == $zone, row == $row2, column == $col2, value == $val2 )
not ( PossibleValue( zone == $zone, row == $row1, column == $col1, value != $val1, value != $val2 ) )
not ( PossibleValue( zone == $zone, row == $row2, column == $col2, value != $val1, value != $val2 ) )
$pv : PossibleValue( zone == $zone, value == $val1)
then
retract( $pv );
#System.out.println("Rule 11 fired.");
end

分享到：

drools4: Conway示例分析 | Drools4：对Ticket示例的分析

2007-08-05 12:47
浏览 4512
评论(8)
论坛回复 / 浏览 (6 / 9677)
分类:企业架构
查看更多

8 楼 hrfdotnet 2008-06-20

哥们，能把这个示例完整的源码发一份给我吗，先谢谢了！hrfsun@yahoo.com.cn

7 楼 czhcc 2007-10-09

学习中。不过想问一下，为什么 salience值为250的规则不被首先执行？

6 楼 tvjody 2007-09-18

的确是很不错
楼主写写你的Drools的应用心得以及成功案例

5 楼 chinapr 2007-08-27

看了楼主的很多帖子都还不错

4 楼 wl1985 2007-08-23

像是游戏开发中使用的中间件,仔细研究一下,代码注释很规范,值得借鉴

3 楼宋存义 2007-08-23

太感谢了，正在学习中，
太多的不明白啊，想请教一下，
query是怎么用啊
要做一个从数据库中通过id能显示内容和其他的例子怎么做啊
我现在学的都晕了，谢谢各位知道的回答一下

2 楼 linyajun 2007-08-08

给分,支持drools4

1 楼江南白衣 2007-08-06

给分，兄弟为drools4推广出力良多。

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论