tag:blogger.com,1999:blog-1675441879744497602.post5509302577082327486..comments2022-11-10T09:35:19.438+01:00Comments on Codiary: Zarankiewicz Problem and Algorithmic Approaches11235813tddhttp://www.blogger.com/profile/15962159614063868604noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1675441879744497602.post-46049567492436880042016-02-23T00:11:56.253+01:002016-02-23T00:11:56.253+01:00I might share code for the more efficient algorith...I might share code for the more efficient algorithm, since the one described in my previous comment does not take advantage of any theorems, does not exploit the full symmetry group, and does no precomputations. The column symmetry reduction I described is fairly simple to implement recursively - call enforceColumnOrdering(0,0,width) each time a row is added. let g(x,y) be the number in the grid at x,y.<br /><br />enforceColumnOrdering(y, left, right):<br />-- for(left < x < right):<br />---- if(g(x-1,y)==0 and g(x,y)==1):<br />------ reject this partial solution<br />-- if(row y+1 exists):<br />---- for(left < x < right):<br />------ if(g(x-1,y)==1 and g(x,y)==0):<br />-------- enforceColumnOrdering(y+1,left,x)<br />-------- enforceColumnOrdering(y+1,x,right)<br />Andrew Kayhttp://andrewkay.name/blog/noreply@blogger.comtag:blogger.com,1999:blog-1675441879744497602.post-55139152168936254582016-02-22T22:13:53.590+01:002016-02-22T22:13:53.590+01:00It is good to see, that there is progress on this ...It is good to see, that there is progress on this problem. Although, I am not working on Zarankiewicz/Latin Squares, I am going to work on similar patterns soon (row/column symmetries again). Your approach is indeed better, since symmetries are exploited much better! <br />My algorithm took 34min to finish the search on 11x11 grid, so you achieved a speedup of factor 9.5 for this dimension.<br />Are you going to share the code? :)<br /><br />Best Regards and thanks again for your comment!11235813tddhttps://www.blogger.com/profile/15962159614063868604noreply@blogger.comtag:blogger.com,1999:blog-1675441879744497602.post-34428856921512116532016-02-22T18:10:52.345+01:002016-02-22T18:10:52.345+01:00I have been interested in this problem recently, a...I have been interested in this problem recently, and I wrote a direct solver which uses row/column symmetries to find exact solutions, but does not depend on any theorems or conjectures.<br /><br />Row symmetry is used to choose rows in weight order (most 1s to fewest 1s), and rows of equal weight in lexicographic order (with 1 before 0). This gives an upper bound on the weight of a partial grid's completion, which can be used to reject partial grids because the most recent solution can be used as a lower bound.<br /><br />Column symmetries are used to recursively partition the columns such that the next row in a partial grid has, without loss of generality, 1s followed by 0s within each partition.<br />Transpose symmetry could be used to require that no column has a weight greater than the weight of the first row, though I didn't implement this.<br /><br />Results for some small grids are below. Times to find the optimum (and prove it is optimal) are in seconds, from a Java implementation on a 2.4GHz processor:<br /><br />n,score,time<br />7,21,0.002<br />8,24,0.027<br />9,29,0.107<br />10,34,11.133<br />11,39,213.261<br /><br />This seems considerably more efficient than the algorithm you describe.<br /><br />If the rows are ordered lexicographically rather than by weight, the algorithm is much slower, but the resulting solutions are in a form analogous to the Paige-Wexler normal form of the incidence matrix of a finite projective plane. This leads to an elegant (and even more efficient) algorithm analogous to using transversals to search for mutually orthogonal Latin squares.Andrew Kayhttp://andrewkay.name/blog/noreply@blogger.com