CY's Take on PWC#086
# (I will write more some hours later. This may not be a good practice. But) 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
- Three 25x25 Sudokus
- SUDOKU... before the Perl script
- Pascal program written in 2006 (for my memorial)
- How I do Sudoku in Perl in 2020
- Links
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;
Comments: exclude does a set operation.
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 initializeAnd 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($pos) if 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;
}
}
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($pos) if 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[$i] eq '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];
}
my @emptyentry_pos;
for my $i (0..$BSIZE-1) { push @emptyentry_pos,$i if $board[$i] eq '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;
}
}
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($coo) if $board[$coo] ne '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($coo) if $board[$coo] ne 'z';
}
}
my $bit_opp = ( ~ $impos_set ) & $BITWORLD;
return [@{bitstr_to_set_of_alphabets($bit_opp)}];
}
#...
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($coo) if $board[$coo] ne '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($coo) if $board[$coo] ne '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 4Then 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 JStop 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
- English Wikipedia: Mathematics of Sudoku (Kilfoil-Silver-Pettersen formula... I have never taken a statistics course formally. "First approximation" for me is a remembrance term related to physics.)
- CPAN: Games::Sudoku::General
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;
}
}
}
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.
This blog is inactive and replaced by https://e7-87-83.github.io/coding/blog.html ; but I post highly Perl-related posts here.
Leave a comment