Drools4：对Sudoku示例的分析

网站：JavaEye 作者：hxpwork 发表时间: 2007-08-05 12:47 此文章来自于 http://www.iteye.com
声明：本文系JavaEye网站原创文章，未经JavaEye网站或者作者本人书面许可，任何其他网站严禁擅自发表本文，否则必将追究法律责任！
原文链接： http://www.iteye.com/topic/109129

/*
    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：对Sudoku示例的分析 》 的评论也很精彩，欢迎您也添加评论。查看详细 >>

推荐相关文章：
  精品文章翻译：现实中的规则引擎
  使用 JProfiler 监控 JBoss 运行情况




JavaEye推荐
上海乐福狗信息技术有限公司:诚聘技术经理和开发工程师
免费下载IBM社区版软件--它基于开放的标准，支持广泛的开发类型，让您的开发高效自主！
京沪穗蓉四地免费注册，SOA技术高手汇聚交锋.
上海：优秀公司德比：高薪诚聘 资深Java工程师
广州：优易公司：诚聘Java工程师，开发经理
上海：尤恩斯国际集团：诚聘开发工程师
北京：优秀公司NHNChina招聘:WEB开发,系统管理,JAVA开发, DBA