Back in 2006 there were a number of messages about the maximum number of strings on a 19x19 board. As noted then the answer is 277.
In the mean time there has been progress on this issue in the context of placing dominoes on a board which is an equivalent problem. A number of papers from 2011 basically solved this issue. I made this post to make sure the computer-go community knows about this (usefull to statically size your group list if you ever play on weird board size) Here is a table for all rectangular boards up to size 19: Chain table 1| 0 2| 1 2 3| 2 4 6 4| 2 5 8 12 5| 3 7 11 14 18 6| 4 8 13 17 22 26 7| 4 10 15 21 26 31 37 8| 5 11 17 24 29 36 42 48 9| 6 13 20 26 33 40 47 54 61 10| 6 14 22 30 37 44 53 60 68 76 11| 7 16 24 33 41 49 58 66 75 83 92 12| 8 17 26 36 44 54 63 72 82 91 100 109 13| 8 19 29 39 48 58 69 78 88 99 108 118 129 14| 9 20 31 42 52 63 74 84 95 106 117 128 138 149 15| 10 22 33 45 56 68 79 91 102 114 125 137 148 160 172 16| 10 23 35 48 60 72 85 97 109 122 134 146 159 171 183 196 17| 11 25 38 51 63 76 90 103 116 129 142 155 168 182 195 208 221 18| 12 26 40 54 67 81 95 109 123 137 151 165 179 192 206 220 234 248 19| 12 28 42 57 71 86 101 115 130 145 159 174 189 203 218 233 248 262 277 (the diagonal are the numbers for square boards) Below this is a simple perl program that calculate the values for any m x n size board with the function "chains". It also has a simple generator for a table like the above one. ============================================================================== #!/usr/bin/perl -w use strict; use warnings; # Determine the maximum number of chains on any m x n board # Based on information from # Computing the Domination Number of Grid Graphs # http://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p141/pdf # Saturated Domino Coverings # http://arxiv.org/pdf/1112.2115v1 # The Domination Number of Grids # http://arxiv.org/pdf/1102.5206v1 our $VERSION = "1.000"; my $MAX = 19; sub naive { my ($m, $n) = @_; return int(($m+2)*($n+2)/5-4); } sub gamma { my ($m, $n) = @_; ($m, $n) = ($n, $m) if $m > $n; my $result; if ($m == 1) { $result = ($n+2) / 3; } elsif ($m == 2) { $result = ($n+2)/2; } elsif ($m == 3) { $result = (3*$n+4) / 4; } elsif ($m == 4) { $result = $n; $result++ if $n == 5 || $n == 6 || $n == 9; } elsif ($m == 5) { $result = (6*$n+8)/5; $result = 9 if $n == 7; } elsif ($m == 6) { if ($n % 7 == 1) { $result = (10*$n+10)/7; } else { $result = (10*$n+12)/7; } } elsif ($m == 7) { $result = (5*$n+3)/3; } elsif ($m == 8) { $result = (15*$n+14)/8; } elsif ($m == 9) { $result = (23*$n+20)/11; } elsif ($m == 10) { if ($n % 13 == 0 || $n % 13 == 3 and $n != 13 && $n != 16) { $result = (30*$n+37)/13; } else { $result = (30*$n+24)/13; } } elsif ($m == 11) { if ($n == 11 || $n == 18 || $n == 20 || $n == 22 || $n == 33) { $result = (38*$n+21)/15; } else { $result = (38*$n+36)/15; } } elsif ($m == 12) { $result = (80*$n+66)/29; } elsif ($m == 13) { if ($n % 33 == 14 || $n % 33 == 15 || $n % 33 == 17 || $n % 33 == 20) { $result = (98*$n+111)/33; } else { $result = (98*$n+78)/33; } } elsif ($m == 14) { if ($n % 22 == 18) { $result = (35*$n+40)/11; } else { $result = (35*$n+29)/11; } } elsif ($m == 15) { if ($n % 26 == 5) { $result = (44*$n+27)/13; } else { $result = (44*$n+40)/13; } } else { $result = naive($m, $n); } return int($result); } sub chains { my ($m, $n) = @_; return $m*$n - gamma($m, $n); } sub show_gamma_table { my ($max) = @_; for my $n (1..$max) { printf "%2d|", $n; for my $m (1..$n) { printf " %3d", gamma($m, $n); } print "\n"; } } sub show_chain_table { my ($max) = @_; for my $n (1..$max) { printf "%2d|", $n; for my $m (1..$n) { printf " %3d", chains($m, $n); } print "\n"; } } sub show_tiddly_table { my ($max) = @_; print "|m\\n|"; for my $n (1..$max) { printf " !%d|", $n; } print "\n"; for my $n (1..$max) { printf "| !%d|", $n; for my $m (1..$n) { my $c = chains($m, $n); my $s = $m*$n - naive($m, $n); if ($s > $c) { print "bgcolor(green):"; } elsif ($s < $c) { print "bgcolor(red):"; } printf " %d|", $c; } for my $m ($n+1..$max) { print "|"; } print "\n"; } } if (0) { print "Gamma table\n"; show_gamma_table($MAX); print "\n\n"; } print "Chain table\n"; show_chain_table($MAX); print "\n\n"; if (0) { print "Tiddly table\n"; show_tiddly_table($MAX); print "\n\n"; } _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
