小學一年級數學題 - 系列-3

Windows19

贊            

sunzhiguolu

回復 31# Windows19
謝謝諸位大神，包括樓上打醬油的 。說過的話一定會兌現，等我消化消化。。。

jason680

回復 23# sunzhiguolu

http://www.cesargiobbi.com/thread-4263652-1-1.html

zhouzhen1

回復 14# 523066680

Algorithm:ermute版本 <= 0.12的話在Perl 5.24及以上是build不出來的。這是因為Perl 5.24有一個稱為Context rework的工作，提高了函數調用的速度，但是一些原來非公開的內部API被改了，當時造成了一批XS package break。

我前兩天因為單位里工作的原因，剛好把Algorithm:ermute修了一下，現在最新的版本是0.14，你可以再試試。

523066680

回復 34# zhouzhen1

厲害了。高性能。

rubyish

v3:

1. real        0m0.030s

復制代碼

1. #!/usr/bin/perl
   
2. # version 26, subversion 0 (v5.26.0)
   
3. use 5.010;
   
4. explore();
   
5. 
   
6. # ______________________ SUB ______________________
   
7. 
   
8. sub explore { E_(0) }
   
9. 
   
10. sub E_ {
    
11.     my $n = shift;
    
12.     state $b   = [ (0) x 4 ];
    
13.     state $has = [ (0) x 10 ];
    
14.     state $in  = [ [ 0, 1 ], [ 2, 3 ], [ 0, 2 ], [ 1, 3 ], [ 0, 3 ] ];
    
15. 
    
16.     if ( $n == 3 ) {
    
17.         # b3 = 15 - (15 - b0 - b1) - (15 - b0 - b2)
    
18.         my $b3 = $b->[0] + $b->[0] + $b->[1] + $b->[2] - 15;
    
19.         return if $b3 < 1 or $b3 > 9;
    
20.         $b->[3] = $b3;
    
21.         my ( @test, @x ) = (0) x 10;
    
22.         $test[$_]++ and return for @$b;
    
23. 
    
24.         for my $i (@$in) {
    
25.             my $it = $b->[ $i->[0] ] + $b->[ $i->[1] ];
    
26.             return if $it < 6 or $it > 14;
    
27.             $it = 15 - $it;
    
28.             return if $test[$it]++;
    
29.             push @x, $it;
    
30.         }
    
31. 
    
32.         say join ' ', @$b[ 0, 1 ], $x[0];
    
33.         say join ' ', @$b[ 2, 3 ], $x[1];
    
34.         say join ' ', @x[ 2, 3, 4 ];
    
35.         say '-----';
    
36.         return;
    
37.     }
    
38. 
    
39.     for my $it ( 1 .. 9 ) {
    
40.         next if $has->[$it];
    
41.         $has->[$it]++;
    
42.         $b->[$n] = $it;
    
43.         E_( $n + 1 );
    
44.         $has->[$it]--;
    
45.     }
    
46. }
    
47. 
    
48. __DATA__
    
49. $_
    

復制代碼

jason680

回復 32# sunzhiguolu

>> ...說過的話一定會兌現，等我消化消化。。。

消化消化
帖子都快消失，還不出來說說話...

aef25u

最近在看《七周七語言》，這類題用prolog是最合適的，而perl有AI:rolog，寫了個代碼，因為要完成窮舉和滿足所有條件，運行時間會有點久。
fd_domain與fd_all_diff函數都是自己寫的，另個解決問題的方式是通過遞歸來實現的。

1. use AI::Prolog;
   
2. use Data::Dumper;
   
3. $Data::Dumper::Indent = 0;
   
4. 
   
5. my $prolog;
   
6. 
   
7. # If reading from DATA, we need a CHECK block to ensure that
   
8. # DATA is available by the time the constructor is called
   
9. CHECK {
   
10.     $prolog = AI::Prolog->new(
    
11.         do { local $/; <DATA> }
    
12.     );
    
13. }
    
14. #[4, 9,2,
    
15. # 3,5,7,
    
16. # 8, 1,6]
    
17. $prolog->query("sudoku([_, _,_,_,_,_,_, _,_], Solution).");
    
18. 
    
19. #顯示執行過程
    
20. #$prolog->trace(1);
    
21. while ( my $results = $prolog->results ) {
    
22.     #print "@$results\n";
    
23.     print Dumper $results;
    
24. }
    
25. 
    
26. __DATA__
    
27. member(X, [ X | _ ]).
    
28. member(X, [ _ | TAIL ]) :-
    
29.    member(X, TAIL).
    
30. fd_domain([],_).
    
31. fd_domain([ HEAD | TAIL ],L) :-
    
32.    member(HEAD,L),
    
33.    fd_domain(TAIL,L).
    
34. fd_all_diff([]).
    
35. fd_all_diff([ HEAD | TAIL ]) :-
    
36.    not(member(HEAD,TAIL)),
    
37.    fd_all_diff(TAIL).
    
38. sum([], 0).
    
39. sum([Head|Tail],Total) :-
    
40.     sum(Tail,Sum),
    
41.     Total is Head + Sum.
    
42.    
    
43. valid([]).
    
44. valid([HEAD|TAIL]) :-
    
45.     sum( HEAD , Total),
    
46.     eq(15,Total),
    
47.     valid(TAIL).
    
48. sudoku(Puzzle, Solution) :-
    
49.     Solution = Puzzle,
    
50.     eq(Puzzle, [S11, S12, S13, S21, S22, S23, S31, S32, S33]),
    
51.     fd_domain(Solution, [1,2,3,4,5,6,7,8,9]),
    
52.     eq(Row1,[S11, S12, S13]),
    
53.     eq(Row2,[S21, S22, S23]),
    
54.     eq(Row3,[S31, S32, S33]),
    
55.     eq(Col1,[S11, S21, S31]),
    
56.     eq(Col2,[S12, S22, S32]),
    
57.     eq(Col3,[S13, S23, S33]),
    
58.     eq(ObjLineL,[S11, S22, S33]),
    
59.     eq(ObjLineR, [S13, S22, S31]),
    
60.     fd_all_diff(Solution),
    
61.     valid([Row1, Row2, Row3, Col1, Col2, Col3, ObjLineL, ObjLineR]).

復制代碼