CY's Take on PWC#086

pascal_userinterface.jpg# (I will write more some hours later. This may not be a good practice. But) #HKT November 15, 2020 3:32 PM

I am excited by the Sudoku task and eager to share.

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenge - Challenge 086, submit codes on-time (by GitHub or email).



Table of Contents

How the example puzzle is solved

For the puzzle given:
$ perl ch-2ex.pl
tree id: 1   pos: 36 val:C
tree id: 2   pos: 2 val:E
tree id: 3   pos: 40 val:H
tree id: 4   pos: 12 val:E
tree id: 5   pos: 5 val:I
tree id: 6   pos: 1 val:C
tree id: 7   pos: 0 val:D
tree id: 8   pos: 21 val:H
tree id: 9   pos: 7 val:H
tree id: 10   pos: 79 val:E
tree id: 11   pos: 68 val:G
tree id: 12   pos: 45 val:I
tree id: 13   pos: 49 val:D
tree id: 14   pos: 78 val:B
tree id: 15   pos: 66 val:I
tree id: 16   pos: 80 val:I
tree id: 17   pos: 14 val:A
tree id: 18   pos: 58 val:B
tree id: 19   pos: 31 val:I
tree id: 20   pos: 48 val:G
tree id: 21   pos: 11 val:B
tree id: 22   pos: 17 val:C
tree id: 23   pos: 32 val:E
tree id: 24   pos: 35 val:G
tree id: 25   pos: 25 val:F
tree id: 26   pos: 15 val:D
tree id: 27   pos: 44 val:E
tree id: 28   pos: 63 val:B
tree id: 29   pos: 43 val:A
tree id: 30   pos: 26 val:B
tree id: 31   pos: 59 val:F
tree id: 32   pos: 29 val:F
tree id: 33   pos: 75 val:D
tree id: 34   pos: 73 val:F
tree id: 35   pos: 22 val:C
tree id: 36   pos: 54 val:E
tree id: 37   pos: 37 val:G
tree id: 38   pos: 55 val:A
tree id: 39   pos: 51 val:F
tree id: 40   pos: 47 val:A
tree id: 41   pos: 65 val:H
tree id: 42   pos: 33 val:C
tree id: 43   pos: 60 val:H
tree id: 44   pos: 69 val:A
tree id: 45   pos: 20 val:G
4 3 5 2 6 9 7 8 1 
6 8 2 5 7 1 4 9 3 
1 9 7 8 3 4 5 6 2 
8 2 6 1 9 5 3 4 7 
3 7 4 6 8 2 9 1 5 
9 5 1 7 4 3 6 2 8 
5 1 9 3 2 6 8 7 4 
2 4 8 9 5 7 1 3 6 
7 6 3 4 1 8 2 5 9 

Three 25x25 Sudokus:

$ perl ch-2.pl 5
M Y C I R O U A P B L F X E S Q V N H J G T D K W 
N D W V U E I Y K S H O P Q A X T R C G M B J L F 
P A J L K Q W T X F V I C U G B M O Y D N S R E H 
S H B X F J V G M R D N W Y T E K L I P C A U Q O 
T G Q E O N L C D H B M J K R F W U A S X Y I V P 
C E D G B R A Q F I N S O L P H U K J M Y W T X V 
W U Y T L S P X B K F V G M J O N D Q R A H E I C 
H N X M Q T C V L D K W R A Y I B E G F O J P S U 
V K I P J M E O H N T U B X C S A Y W L F Q G D R 
A O R F S U J W Y G Q D E I H P C X T V B M K N L 
F T P R V A K H U X G J L S M N Q C D B W E O Y I 
D S U A H C O B Q Y R X V W F J P T E I L G N M K 
I M N K Y F R L J P A E T D B G X W V O H U S C Q 
E B G Q W I T D S V O K N C U Y L A M H J R F P X 
X J L O C G M N E W I Y H P Q U R S F K D V A B T 
Y F H J A D S P N T W G M R V K E I X Q U L C O B 
O C V N T W Q F I E Y P K B X L S G U A R D H J M 
L I M W G B X K V C U A D H O R J F P Y E N Q T S 
R P E U D L G M O J S Q I T N C H V B W K F X A Y 
K Q S B X H Y U R A C L F J E T D M O N P I V W G 
Q W A Y M V H E G L X R S F I D O P N C T K B U J 
B R K H P X D S A U E C Q V W M G J L T I O Y F N 
G L O C I Y B J W Q P T U N K A F H S E V X M R D 
U V T S N K F I C M J H A O D W Y B R X Q P L G E 
J X F D E P N R T O M B Y G L V I Q K U S C W H A 



$ time perl ch-2.pl 5
M P R X F I G D Y T V B O W J E A Q L H U S N K C 
N J S L Y A Q O F B X C K G R P M U T D I E H V W 
A G C V E H M R L P U D I N Q S W B K O Y F J X T 
T K Q H D N W E J U S F L P M C Y I V X B A G R O 
B O W I U S X V C K T E H A Y G J R N F M L Q D P 
R W N A K G O F D Q J H B L S Y U X P T C I M E V 
S T L Y B R C A H M N Q F V G I D K J E P U O W X 
V M G P X Y L J T I E U D O W H F A C B S Q R N K 
D I F C O X P U E N M R A Y K Q S L W V H J T G B 
Q E U J H W K B V S I T C X P R N M O G L Y D F A 
C A E G L O D I P R F V S Q T K H J B W X M U Y N 
Y B V S N K T G U H D W X J L M C F Q A R P E O I 
J X P O W F A S Q E K M R B H U G Y I N V D C T L 
H Q T K M V Y W X L C I P U N D E O S R F B A J G 
U F I D R J N M B C O Y G E A V L T X P W H K Q S 
O L H E P D V K W Y R N M F B T Q C A U G X S I J 
K R J M C P I N G F A S T D E X V W H Y Q O B L U 
G U Y Q S T B L O J P K W H X N I D E M A V F C R 
I D B W A U R Q M X G J Y C V L O S F K T N P H E 
F N X T V C E H S A Q L U I O B P G R J D K W M Y 
P C A F G B S T I V W O N M D J X E Y Q K R L U H 
L H M N I Q J Y R D B P E K C W T V U S O G X A F 
X V O B Q E H C K G L A J T U F R P M I N W Y S D 
W S K U J L F X N O Y G Q R I A B H D C E T V P M 
E Y D R T M U P A W H X V S F O K N G L J C I B Q 


real	0m19.987s
user	0m19.951s
sys	0m0.012s



$ time perl ch-2.pl 5
U D H T J K G W M S R I C P X A B Y O L F Q N V E 
B R P C M Q I L T J Y D W V E K H F N U X O A G S 
A G W Q X E Y C N O M F H L B S V T R D P K I U J 
K I N O L F D V H X Q A J S U M W G E P T R C B Y 
V S F Y E P R U B A T N K G O Q J X C I L H M D W 
Y E M A V O T I K L J G S W P B U C Q H N X D R F 
H Q D P G U C F V N L K O I Y X E J S R A W B T M 
F B U J T S Q Y G W D X R C H L N M A O I V E P K 
O W X L I R A B E H N Q F U M D T V P K C Y J S G 
C N K S R D P X J M V B A E T Y F I W G Q U H O L 
G O C E F J W D X I H U Q A V P Y N M T S B K L R 
W X T V B A U N Y F S R D O L E I K H C M J G Q P 
I U J H N L M R O P K Y B T G W Q S V X D C F E A 
L M Q D Y G V K S T E C P J W F R U B A H N O X I 
P K A R S H B E Q C F M I X N G O D L J V T Y W U 
M V G I Q B S H A Y O L E N D U X R F W J P T K C 
N H Y F D X E T W K I P V R S C G Q J M B L U A O 
T A E K U M L J D R C W X B Q O P H I Y G S V F N 
R L B W P C N O I Q U J G Y F T S A K V E M X H D 
J C S X O V F P U G A H T M K N L E D B R I W Y Q 
S P V N C Y K G L D W T U Q A J M B X E O F R I H 
D T I G H N O M P E X V L F C R K W U Q Y A S J B 
Q Y R B A W H S F V G O M K J I D P T N U E L C X 
X F O M K I J Q C U B E Y H R V A L G S W D P N T 
E J L U W T X A R B P S N D I H C O Y F K G Q M V 


real	0m19.008s
user	0m18.977s
sys	0m0.004s



SUDOKU... before the Perl script

I had written an command-line application of Sudoku as a project submitted for Hong Kong public exam. Looking back my codes, comparing with the testings this time, I have been as stubborn (for the field I am interested in =_=" ) as that teen in 2006.
When I saw the task statement, the task "N Queens" (Challenge #062)(headlines afterwards) popped in my mind! I knew the Task 2 of Challenge #086 would be a long haul, even if one tried to write a minimalist script.
Actually I did not have much memory about the Pascal codes. I remember that it can run and gave me an "A" for the subject (in public exam), but at that time I did not have much knowledge of good codes. I digged the codes out from mailbox and was comforted a bit that the codes had good consideration of the game. One could choose to play the "advanced" puzzle, which may require some "trial and error" or simultaneous visualization on a few cells; and the "beginner" puzzles could be solved by the technique "naked single" - like the example given in The Weekly Challenge -. As a final note for those Pascal codes, the consideration of the two diagonals Sudoku variant "X-Sudoku" was even implemented.
So, come back to 2020, how was I planning to treat Sudoku this time? I am often ambitious; thinking of the fact that the number of Latin alphabet equals 5*5+1, I thought of a script capable of producing 25x25 Sudoku...

Pascal program written in 2006

Pascal code: Data structures in the beginning

This is the beginning of one of the two source code files which is mostly for algorithmic stuff:
unit solving;

interface
type
  noset = set of 0..9;
  bdbasic = array[0..8,0..8] of byte;
  tribd = record
    puz,ans,ref :bdbasic;
  end;
  fiveg = record
    bd : array[0..5] of bdbasic;
    anpo :byte;
  end;

{two functions for user interface, one is of type fiveg, another is of type tribd; skip here}

implementation

type
  cellval = record
    val :byte;
    poss :noset;
  end;
  bdpos = record
    cel : array[0..8,0..8] of cellval;
    nxn : array[0..2,0..8] of noset;
    found :integer;
    valid :boolean;
    gametype :byte;
  end;
noset means "(a) set of number" here. poss stands for "possible/possibility".

Pascal code: Generating a 9x9 Sudoku Puzzle

procedure randombd(par :byte; var given :bdbasic);
var validor,theboard :bdbasic; i,j,k :byte;okok :boolean;
begin
  repeat
    theboard := given;
    for k := 1 to par do begin
      j := random(9); i := random(9);
      if theboard[j,i] = 0 then theboard[j,i] := random(9)+1;
    end;

    okok := true;
    k := 0;
    while (k<3) and okok do begin
      for i := 0 to 8 do for j := 0 to 8 do validor[i,j] := 0;
      for i := 0 to 8 do for j := 0 to 8 do
        if theboard[cx(i,j,k),cy(i,j,k)] <> 0
          then validor[i,theboard[cx(i,j,k),cy(i,j,k)]-1] := validor[i,theboard[cx(i,j,k),cy(i,j,k)]-1] + 1;
      i := 0;
      while (i<9) and okok do begin
        j := 0;
        while (j<9) and okok do
          if validor[i,j] >= 2 then okok := false else j:=j+1;
        i := i+1;
      end;
      k := k+1;
    end;

  until okok;
  given := theboard;
end;
procedure newv_bd(const bdb :bdbasic; var pla:bdpos);
var i,j :byte;
begin
  pla.found := 0;
  for i := 0 to 8 do begin
    for j := 0 to 8 do begin
      pla.cel[i,j].val := 0;
      pla.cel[i,j].poss := [1..9];
    end;
    for j := 0 to 2 do
      pla.nxn[j,i] := [1..9];
  end;

  for i := 0 to 8 do for j := 0 to 8 do
    if bdb[i,j]<>0 then newv(i,j,bdb[i,j],pla);

  pla.valid := true;

end;
Two supporting functions:
function cx(const cons,vari,typ :byte) :byte;
begin
  case typ of
    0: cx := cons;
    1: cx := vari;
    2: cx := (cons div 3)*3 + vari div 3;
  end;
end;

function cy(const cons,vari,typ :byte) :byte;
begin
  case typ of
    0: cy := vari;
    1: cy := cons;
    2: cy := (cons mod 3)*3 + vari mod 3;
  end;
end;
Comments: par is usually set at 15 (in code section I don't put online). newv will be mentioned in next section.

Pascal code: Generating a Sudoku puzzle

procedure generating_advanced_game(const gametype :byte; var possans:fiveg; var bd_fixed:bdbasic);
var
  i,j,k,startv :byte;
  bd_bas :bdpos;

begin
    bd_bas.gametype := gametype;
    newv_bd(bd_fixed,bd_bas);
    while possans.anpo > 1 do begin
      k := random(possans.anpo);
      i := random(9); j := random(9);
      repeat
        i := (i + 1) mod 9; j := random(9); startv := j;
        repeat
          j := (j+1) mod 9
        until (possans.bd[k][i,j] <> possans.bd[(k+1) mod possans.anpo][i,j]) or (j = startv);
      until possans.bd[k][i,j] <> possans.bd[(k+1) mod possans.anpo][i,j];
      bd_fixed[i,j] := possans.bd[k][i,j];
      newv(i,j,possans.bd[k][i,j],bd_bas);
      possans := trial_and_error(bd_bas);
      write('.');
    end;
end;
The supporting procedure newv:

procedure newv(const x,y,c :byte;var pla :bdpos);
var i :byte;
begin
  pla.cel[x,y].poss := [];
  pla.cel[x,y].val := c;
  pla.found := pla.found + 1;
  exclude(pla.nxn[0,x], c);
  exclude(pla.nxn[1,y], c);
  exclude(pla.nxn[2,(x div 3)*3 + (y div 3) ], c);
  for i := 0 to 8 do begin
    exclude(pla.cel[x,i].poss, c);
    exclude(pla.cel[i,y].poss, c);
    exclude(pla.cel[x - x mod 3 + i mod 3,y - y mod 3 + i div 3].poss, c)
  end;
end;

Pascal code: Generating an easy Sudoku puzzle

procedure generating_beginner_game (const bd_possans:bdbasic; gametype :byte; var bd_fixed:bdbasic);
var
  i,j,startv :byte;
  bd_bas :bdpos;
begin
  bd_bas.gametype := gametype;
  newv_bd(bd_fixed,bd_bas);
  repeat
    i := random(9); j := random(9);
    repeat
      i := (i + 1) mod 9; j := random(9); startv := j;
      repeat
        j := (j+1) mod 9
      until (bd_bas.cel[i,j].val = 0) or (j = startv);
    until bd_bas.cel[i,j].val = 0;
    bd_fixed[i,j] := bd_possans[i,j];
    newv(i,j,bd_possans[i,j],bd_bas);
    first(bd_bas);
    write('.');
  until bd_bas.found = 81;
end;
Overall Comments:
There were a lots of typing. At that time, I worked under the Turbo Pascal IDE. And I did not make any comments on the codes - oh, bad practice - ; my teacher and the graders have been teachers, seems never been professional programmers. I would get a "B" or "C" for the confusing variable names without explanation.
"repeat - until" block has been used many times in these code excerpts.
Observant readers may find that I did not make a good use of the built-in difference of procedure and function in Pascal.
I cannot find the final compiled executable file. The screenshot is from codes in the middle stage of development (for my memorial). I roughly backupped the codes and .exe(s) in email account inbox.

How I do Sudoku in 2020

Here are the summary of subroutines of my SUBMITTED code: (total ~15)
sub num_repr
sub internal_repr_to_trad_3
sub internal_repr_to_trad
sub TEST_print_board
sub coord_to_nth_row
sub coord_to_nth_col
sub coord_to_nth_ssq
sub checkrows  # haven't been used
sub checkcols  # haven't been used
sub r_ssq_tl
sub checkssqs  # haven't been used
sub come_bk_from_fail_attempt
sub declare_impossibility
sub check_complete
sub action_on_new_node
sub bitstr_to_set_of_alphabets
sub choose_an_empty_entry
sub choose_possible_values_for_entry
sub random_an_array
sub countz
sub main
sub initialize
And at the beginning comments of the code, I make an apology:
# Caution: The part for declaring impossibility hasn't been tested.
# Caution: The subroutine "come_bk_after_fail_attempt" 
#          is not logically complete 

Approach

It is a combination of Depth-First Tree and recursion. action_on_new_node uses DFT, and come_bk_from_fail_attempt uses recursion if needed. The former subroutine calls the latter sometimes. (Here, blogging, I realize that I should output "node id" instead of "tree id" to show the progression of the script.)

sub action_on_new_node {
    my $leaf = \$tree[$#tree];
    if (defined($$leaf) && defined($$leaf->position)) {
        $board[$$leaf->position] = $$leaf->value;
        
        my $pos = &choose_an_empty_entry;
        my $p_value = choose_possible_values_for_entry($posif defined($pos);
        if (defined($pos) && @{$p_value} ) {
            for my $v (@{$p_value}) {  
                push @{$$leaf->nexts}, 
                    node->new($pos$v, 0, ($$leaf->depth)+1, []);
            }
             my $trial = shift @{$$leaf->nexts};
             push @tree@{$$leaf->nexts};
             push @tree$trial;
        } else
        { if (!check_complete()) {
                # print "location A \n";    #TESTING LINES
                come_bk_from_fail_attempt;
            }
        }
    } else 
    {
        # print "location B \n";
        come_bk_from_fail_attempt;
    }
}

I will come back to discuss come_bk_from_fail_attempt in next seciton. choose_an_empty_entry is critical, too. Let's see the codes before describing its optimization and functionalities:

sub choose_an_empty_entry {
    my @emptyentry_pos;
    for my $i (0..$BSIZE-1) { push @emptyentry_pos,$i if $board[$ieq 'z';}
    
    my $min_opp = $E_LEN;
    my @candidate_small;
    for my $i (@emptyentry_pos) {
        my $temp_i = scalar @{choose_possible_values_for_entry($i)} ;
        if ($temp_i < $min_opp) {
            $min_opp = $temp_i;
            @candidate_small = ($i)
        } elsif ( $temp_i == $min_opp ) 
        {
            push @candidate_small$i;
        }
    }
    
    @candidate_small = random_an_array(@candidate_small);
    return $candidate_small[0];
}
Many coders put a number into grid when the number of possible values of the grid is 1. What if there are no such grids? Many codes will CAUSALLY (e.g. by order in the position) choose a grid which hasn't filled and start "trial and error". At this point, however, I will choose one of those with the number of possible values being 2, or 3 if none as 2, or 4 if none as 3, or 5 if none as 6... You get what I mean even I make grammatical mistakes. The existence of $min_opp do the job. Without evidence, I claim this is an important strategy for larger sudokus (16x16 or 25x25). Let's see come_bk_from_fail_attempt now:
sub come_bk_from_fail_attempt {
    die "Too much recursion" if $#tree > 5001;  #appear when $LEVEL > 3
    my $naughty = pop @tree;

    # print "$#tree\n";      this line is for testing
    if (!($naughty)) {
        print "here";
        &declare_impossibility;
    }

    # act on the board to return the board to a proper value

    if (defined($naughty->nexts)) {
        # pop @{$naughty->nexts};   #seem no difference? 
        $board[$naughty->position] = 'z';

        die "TRY AGAIN" if $#tree == -1;

        my $leaf = \($tree[$#tree]);

        if (!($$leaf->nexts) && $$leaf->is_stable) {
                print "here";
                &declare_impossibility;
        }

         if ($naughty->depth == $$leaf->depth+1) {
            if (!($$leaf->nexts) && $$leaf->is_stable) {
                print "there";
                &declare_impossibility;
            }
             
        }
        if (scalar @{$$leaf->nexts} <= 1) {
            #  print "======================= need here\n"; #Testing lines
            my $active = pop @tree;
            $board[$active->position] = 'z';
            &come_bk_from_fail_attempt;
        }
    } else {
        print "zere"
        &declare_impossibility;
    }
}
Not a bit messy... Very messy... come_bk_from_fail_attempt is a defected (but not failed!) attempt. I decided not to handle impossibility situation in details (as I had no time).

Bit Vector for Set Operation

From textbooks I know besides hashing, one may perform set operation in Perl through "bit vector". This is my first time playing with this trick. Here is an implementation, involving bitstr_to_set_of_alphabets and choose_possible_values_for_entry:
my $BITWORLD = 2**($E_LEN+1)-1;

#...

sub bitstr_to_set_of_alphabets {
    my $bitstr = $_[0];
    my @set = ();
    for my $p (0..$E_LEN-1) {
        my $temp = 2**$p;
        if ($temp & $bitstr) {
            push @set$ABT[$p];
        }
    }
    return \@set;
}

sub choose_possible_values_for_entry {
    my $e = $_[0];

    my $impos_set = 0;

    #rows
    for (0..$E_LEN-1)
    {
        my $coo = $E_LEN*coord_to_nth_row($e) + $_;
        $impos_set = $impos_set | 2**num_repr($cooif $board[$coone 'z';
    }   

    #columns  [CLOSE TO THAT FOR ROWS]
    
    #small squares
    my $sq_e = (int ($e / $LEVEL) % $LEVEL) + $LEVEL * int ($e / $LEVEL / $E_LEN ); 
    for my $p (0..$LEVEL-1) {
        for my $q (0..$LEVEL-1) {
             my $coo = r_ssq_tl($sq_e) + $p + $q*$E_LEN;
             $impos_set = $impos_set | 2**num_repr($cooif $board[$coone 'z';
        }
    }
    
    my $bit_opp = ( ~ $impos_set ) & $BITWORLD;
    return [@{bitstr_to_set_of_alphabets($bit_opp)}];
}

Note: (1) r_ssq_tl asks for a grid position(or say coordinate), returns the id of the small square. The small squares are labelled in a similar fashion as the whole Sudoku. (2) @ABT is ('A'..chr(ord('A')+$E_LEN-1)) .

# (1) For 9x9 sudoku
# +-+-+-+
# |0|1|2|  
# +-+-+-+
# |3|4|5|  
# +-+-++
# |6|7|8|  
# +-+-+-+
At this moment, I would like to invite you to glance over my full but defected script: ch-2.pl.

What Could Do Better?

  • Of course on the impossibility situations, in game context;
  • of course on come_bk_from_fail_attempt in code context
  • Better input channel should be provided!!! WTH is "zzzBFzGzAFHzzGzzIzAIzzzDEzzHBzAzzzDzzzDFzBIzzzEzzzCzBHzzICzzzGDzDzzEzzCFGzCzAHzzz".
  • I set a property _is_stable for the node object but I haven't put it into the maximum useful practice.
But, for me, these are not as attractive as my testings with 16x16 and 25x25 Sudokus. ...I choose curiosity instead of official correctness.

16x16 Sudokus and 25x25 Sudokus

After seeing THAT warning messages several times, I asked the Internet and it replied with haskell - Why is Perl so afraid of "deep recursion"? - Stack Overflow. Sometimes I can see the script is running into trouble with a few grids.
tree id: 305   pos: 57 val:E
tree id: 562   pos: 56 val:G
tree id: 564   pos: 58 val:F
tree id: 567   pos: 41 val:B
tree id: 569   pos: 43 val:C
tree id: 570   pos: 42 val:H
Deep recursion on subroutine "main::come_bk_from_fail_attempt" at ch-2.pl line 253.
tree id: 305   pos: 57 val:E
tree id: 564   pos: 56 val:J
tree id: 566   pos: 58 val:F
tree id: 569   pos: 63 val:D
tree id: 571   pos: 60 val:K
tree id: 572   pos: 62 val:M
Deep recursion on subroutine "main::come_bk_from_fail_attempt" at ch-2.pl line 253.
tree id: 305   pos: 57 val:E
tree id: 566   pos: 56 val:F
^Z
[4]+  Stopped                 perl ch-2.pl 4
Then I will stop it. For other (lucky) trials, I get large Sudokus. For 16x16 sudokus, the lucky sudoku will appear within 2 to 6 seconds.
$ perl ch-2.pl 4
tree id: 16   pos: 247 val:P
tree id: 31   pos: 212 val:A
tree id: 45   pos: 198 val:B
tree id: 58   pos: 228 val:C
tree id: 70   pos: 215 val:D
tree id: 81   pos: 229 val:E
tree id: 91   pos: 197 val:F
tree id: 100   pos: 231 val:G

#.....
tree id: 856   pos: 102 val:F
tree id: 857   pos: 118 val:L
tree id: 858   pos: 114 val:F
tree id: 859   pos: 98 val:L
P E C J I A K N F B O G D H M L 
B O A D M L P J C H N K F E G I 
N K M H G D E F A I L J C P O B 
G L I F O H C B D M P E K A J N 
I D N G E P A C B O F H L J K M 
M P O B N J D I L E K C G F H A 
H J L A K B F O N D G M E I C P 
K C F E H G L M P J A I O N B D 
O F E L P M H K I N C A J B D G 
C M H K F N J A G P D B I O L E 
A I D N B O G E M F J L H C P K 
J B G P D C I L E K H O N M A F 
L N P M J F B H K C I D A G E O 
F H B O A K N D J G E P M L I C 
D A J I C E M G O L B N P K F H 
E G K C L I O P H A M F B D N J 
Stop manually, or stop within codes:
$ perl ch-2.pl 4
tree id: 16   pos: 11 val:P
tree id: 31   pos: 2 val:A
tree id: 45   pos: 4 val:B
tree id: 58   pos: 14 val:C
#....
tree id: 360   pos: 24 val:O
tree id: 372   pos: 238 val:B
tree id: 383   pos: 252 val:A
tree id: 393   pos: 239 val:C
tree id: 402   pos: 204 val:E
tree id: 410   pos: 255 val:D
tree id: 417   pos: 207 val:G
tree id: 423   pos: 223 val:H
tree id: 430   pos: 222 val:F
tree id: 436   pos: 221 val:I
#...
tree id: 285   pos: 139 val:D
tree id: 4992   pos: 187 val:E
tree id: 4994   pos: 171 val:J
tree id: 4997   pos: 168 val:A
tree id: 4999   pos: 152 val:H
tree id: 5000   pos: 136 val:K
Deep recursion on subroutine "main::come_bk_from_fail_attempt" at ch-2.pl line 253.
tree id: 285   pos: 139 val:D
tree id: 4994   pos: 187 val:J
tree id: 4996   pos: 171 val:E
tree id: 4999   pos: 168 val:A
tree id: 5001   pos: 184 val:H
tree id: 5002   pos: 152 val:K
Too much recursion at ch-2.pl line 218.

real	1m35.208s
user	1m34.886s
sys	0m0.192s
What interests me is that why I haven't met the deep recursion warning for generating 9x9 Sudokus. I have tested the 9x9 sudokus a few times through the following line:
for my $t (1..1000) {main(); print $t,"\n";}
Every time no error messages. Arrrrrrrrrrr. Is there due to something mathematical? Possibly it is about the possible depth of tree, but I again have no a rigorous proof yet.

Final Note - after Reading Some Experts' codes and the existing CPAN Module

:) I am quite happy with the possibility of providing a 25x25 sudoku within 20 seconds.
For The Weekly Challenge, after finishing some work I think it is notable, or probably unique, I would look on other participants' blogs or codes usually. I am very impressed with Mr Abigail's description and ambition for this task. Like, q x p boxes for N x N sudoku, where N = p x q. The CPAN module (mentioned in Mr Roger Bell_West's blog) has impressed me also by its number of variants.
Many years ago, near the year I made the sudoku application for public exam, while Sudoku were hot around the world, I chatted with a Math PhD candidate on Olympiad Math Training. We both thought that Sudoku seems not as interesting as other math puzzles.
Do you think I have changed my mind? :P

Links


Task 1: Pair Difference

After sorting,
for my $i (0..$#arr-1) {
    for my $j ($i+1..$#arr) {
        if ($dff == $arr[$j]-$arr[$i]) {
            print 1,"\n";
            return 1;
        }
    }
}

OK, it is HKT Mon Nov 16 01:31:03 2020. Shouldn't I introduce the data structures behind both Pascal and Perl? (Except bitvector learnt lately.) A good night sleep is good for our immune system.

Stay healthy and alert! □
The blogpost has been revised on 18th Nov.
links for codes: ch-1.pl (Pair Difference), ch-2.pl(Sudoku)

Leave a comment

About C.-Y. Fung

user-pic a beginner in programming; passionate in mathematics, distance running and gender issues; from Hong Kong. https://twitter.com/e7_87