From Code to Community: Sponsoring The Perl and Raku Conference 2025 Learn more

MUDLER / Algorithm-SAT-Backtracking-0.13 / lib / Algorithm / SAT / Backtracking / DPLLProb.pm 

            

              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
—
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

              
package Algorithm::SAT::Backtracking::DPLLProb;
use base 'Algorithm::SAT::Backtracking::DPLL';
use List::Util qw(shuffle);
use Storable qw(dclone);
use strict;
use warnings;
our $VERSION = "0.13";
sub _choice {
    my ( undef, $variables, $model ) = @_;
    my $choice;
    foreach my $variable ( shuffle( @{$variables} ) ) {
        $choice = $variable;
        last if ( !exists $model->{$variable} );
    }
    return $choice;
}
1;
=encoding utf-8
=head1 NAME
Algorithm::SAT::Backtracking::DPLLProb - A DPLL Probabilistic Backtracking SAT solver written in pure Perl
=head1 SYNOPSIS
    # You can use it with Algorithm::SAT::Expression
    use Algorithm::SAT::Expression;
    my $expr = Algorithm::SAT::Expression->new->with("Algorithm::SAT::Backtracking::DPLLProb");
    $expr->or( '-foo@2.1', 'bar@2.2' );
    $expr->or( '-foo@2.3', 'bar@2.2' );
    $expr->or( '-baz@2.3', 'bar@2.3' );
    $expr->or( '-baz@1.2', 'bar@2.2' );
    my $model = $exp->solve();
    # Or you can use it directly:
    use Algorithm::SAT::BacktrackingDPLLProb;
    my $solver = Algorithm::SAT::Backtracking::DPLLProb->new;
    my $variables = [ 'blue', 'green', 'yellow', 'pink', 'purple' ];
    my $clauses = [
        [ 'blue',  'green',  '-yellow' ],
        [ '-blue', '-green', 'yellow' ],
        [ 'pink', 'purple', 'green', 'blue', '-yellow' ]
    ];
    my $model = $solver->solve( $variables, $clauses );
=head1 DESCRIPTION
Algorithm::SAT::Backtracking::DPLLProb is a pure Perl implementation of a SAT Backtracking solver.
Look at L<Algorithm::SAT::Backtracking> for a theory description.
L<Algorithm::SAT::Expression> use this module to solve Boolean expressions.
=head1 METHODS
Inherits all the methods from L<Algorithm::SAT::Backtracking::DPLL> and in this variant C<_choice()> it's overrided to choose a random literal.
=head1 LICENSE
Copyright (C) mudler.
This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
=head1 AUTHOR
mudler E<lt>mudler@dark-lab.netE<gt>
=head1 SEE ALSO
L<Algorithm::SAT::Expression>, L<Algorithm::SAT::Backtracking>,L<Algorithm::SAT::Backtracking::DPLL>, L<Algorithm::SAT::Backtracking::Ordered>, L<Algorithm::SAT::Backtracking::Ordered::DPLL>
=cut