- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] sudoku, k-SAT, dancing links
by Gary McGuire 27 Jul '05

27 Jul '05

Victor wrote >Well, It's certainly possible to solve a Sudoku puzzle without trial >and error and guessing. Here's the proof: you can pose the solution >of Sudoku as a problem in satisfiability (SAT): ............ >You can solve any solvable SAT problem via resolution (which is like >Gaussian elimination), and back substitution. This doesn't involve >any guesswork. However, it could be exponential (since resolving on a >variable can create a large number of new clauses). Could it be exponential because it is searching and backtracking? Creating a large number of new clauses sounds a bit like searching through a tree. I wonder is this somehow equivalent to using the 729x324 matrix which people have discussed. It puts sudoku into the framework of a "covering" problem: Given a matrix of 0's and 1's, we want to find some rows that together have exactly one 1 in each column. In other words, their sum is the vector of all 1's. Here is how to construct the matrix for sudoku: The rows are indexed by pairs (d,(x,y)), where d is a digit and (x,y) are the coordinates of a cell. The columns are in four groups, each group having 81 columns. The first group have labels (d,x), where d is a digit and x labels a row of the puzzle. The second group have labels (d,y), where d is a digit and y labels a column of the puzzle. The third group have labels (d,b), where d is a digit and b labels a box of the puzzle. The fourth group have labels (x,y). where (x,y) are the coordinates of a cell. In row (d,(x,y)) we place a 1 in the columns labelled (d,x), (d,y), (d,b) where b is the box containing the cell (x,y), and (x,y). Each row has four 1's. This gives a 729x324 matrix, which I think deserves the name The Sudoku Matrix. (Of course we can do this for n^2 x n^2 sudoku.) Here's the point: A valid completed sudoku grid corresponds to a set of 81 rows which "cover" in the sense that they collectively have exactly one 1 in each column. A puzzle may be described by a set of rows which extends uniquely to a set of 81 rows which cover. Solving the puzzle is finding the rest of the rows. (If we drop the 81 columns corresponding to the boxes then we have the ordinary Latin squares completion problem.) One way to efficiently search for a solution in covering problems is by a backtracking method of Knuth which he calls "dancing links," mentioned in an earlier post. See addendum at http://spivey.oriel.ox.ac.uk/mike/comp2005/results.html Solving the puzzle via the matrix puts deductions like "only two numbers can go in this cell" and "this number can only go in these two cells" on the same footing, and makes any distinction between them artificial. >I'm not saying that this is the best way to do it though! However, if >you wish to do it this way, it is certainly best to first do >resolution on the subset of 1-clauses and 2-clauses (which is very >fast -- there is a linear time algorithm for this). This corresponds >to making the standard initial deductions. What would correspond to using trial and error? I'm impressed that your program solved that puzzle in a fraction of a second. Could it be tweaked to somehow rate the difficulty of a puzzle? Gary McGuire

1 0

[math-fun] sudoku trial and error, NP-completeness
by Gary McGuire 26 Jul '05

26 Jul '05

If you want a hard sudoku try . . . | . . 3 | . 6 . . . . | . . . | . 1 . . 9 7 | 5 . . | . 8 . ---------------------- . . . | . 9 . | 2 . . . . 8 | . 7 . | 4 . . . . 3 | . 6 . | . . . ---------------------- . 1 . | . . 2 | 8 9 . . 4 . | . . . | . . . . 5 . | 1 . . | . . . I believe that this one cannot be solved without trial and error (aka guesswork). Here's another almost completed example: 193 852 746 854 763 912 672 419 853 938 147 625 246 ... 371 517 236 489 78. 6.. .34 465 3.. .97 32. .74 .68 This is easily completed by making a guess. But I cannot see any way to complete it without making a guess. There is much discussion about whether every sudoku can be solved without resorting to trial and error. I think the above examples show that some sudokus require guesswork, but that's not a proof. None of the puzzles given in newspapers will require guesswork, but there are several levels of difficulty beyond what you find in published newspapers and books. Somebody on a forum quoted the NP-completeness result as being a proof that sudokus requiring guesswork exist. Solving sudoku is NP-complete, as has been mentioned before (see the wikipedia entry). The argument goes that an NP-complete problem requires a non-deterministic algorithm, which is one that has to make a random choice somewhere. This random choice is the guess. Is this a valid argument? I don't know enough about NP-completeness. Gary McGuire

3 3

[math-fun] Comet, RSA200, Prime Gaps, Sudoku, Count Down, Dull Semigroups
by Richard Schroeppel 22 Jul '05

22 Jul '05

A bunch of things. --Rich ----- Comet: Did anyone else see the comet impact? I was out watching for it the night of July 3. I had my binoculars pointed at the right area, but had picked out the wrong dot as "the comet". I saw one bright flash, lasting perhaps a second, with no obvious center - the whole field flashed. The time was right, within a minute or so. ----- RSA200: [For some reason, this wasn't on the NMBRTHRY list?] The (old) challenge number RSA200 (a 200 digit number) has been factored by F. Bahr, M. Boehm, J. Franke, T. Kleinjung, P. Montgomery, and H. te Riele. Calendar time was about 18 months, Dec 2003 - May 2005. The total work was roughly 75 PC-years on a 2GHz machine. The linear algebra used a cluster of 80 machines. They have since made further improvements to the Lattice Sieve. Sieving is a random-access use of the memory, and it must be tweaked to make the best use of cache and TLB. Google/Wikipedia for RSA200 or RSA-200. Discrete logs are lagging behind, at 130 digits. Joux & Lecier used a 16-processor cluster of 1GHz Alphas for 3 weeks (about 1 GHz PC-year). Individual logs take a few hours. ----- Recent progress related to the twin-prime problem: >From the prime number theorem, the average gap between primes is log(Prime). Goldston, Motohashi, Pintz, and Yildirim have shown that the ratio Gap(Prime(i))/log(Prime(i)) has lim inf = 0. This is a far cry from the "lim inf Gap = 2" required for settling twin primes, but it is progress. http://www.maa.org/news/052505twinprimes.html http://www.aimath.org/preprints.html. ----- Sudoku: Until the 17-clue example from yesterday, I was wondering what all the fuss was about. The 17er actually requires some more interesting reasoning, but no trial. I used things like "these two cells must be {3,4} in some order", and subtracted them from larger sets. Also "since these two are {3,4} (or {4,3}), and they are in the same row, I can exclude 3&4 from other cells in the row". The main work is scanning the array looking for an application of one of the simple rules like "this 3x3 box must have a 7 somewhere, and all but one of the empty cells is excluded by having a 7 elsewhere in an intersecting row or column". The popularity of the game means there are lots of folks who like a kind of mathematical reasoning. Dan's Latin Square estimate deflator should have a coefficient of 2, not 8. D_4 includes horizontal and vertical reflection, already counted in the row & column permutations. Diagonal flipping remains, giving the coefficient 2. There are Latin Cubes! Addition mod N gives a Latin Hypercube of any dimension. ----- Book recommendation: Count Down, by Steve Olson. He follows the US team (6 high schoolers) at the 2001 Math Olympiad. I found the book intersting for the side topics: He examines the rarity of women in the contest. He looks seriously at the very idea of competing, and how it applies to the Olympiad. Apparently mathematics is held in higher regard in other countries. And there's a chapter about Ultimate Frisbee. The Olympiad problems and solutions are sketched. ----- Associative-Commutative Crossover at 406: Fix an integer N. Consider all the N^N^2 binary operations defined on N elements. Are there more Commutative operations (with symmetric operation tables), or Associative operations (semigroups)? Likely answer: For N<=405, commutatives win; for larger N, semigroups. A quick look at OIES shows Commutativity getting off to an impressive early lead over Associativity. (The story's the same if we count tables instead of culling isomorphs.) Semigroups (fron N=0; sans isomorphs & anti-isomorphs): A001423: 1,1,4,18,126,1160,15973,836021,1843120128 Commutatives (from N=0; sans isomorphs): A001425: 1,1,4,129,43968,254429900,30468670170912, 91267244789189735259,8048575431238519331999571800, 24051927835861852500932966021650993560, 2755731922430783367615449408031031255131879354330 Note to NJAS: I think the sequence database is missing abelian semigroups of order 8, 221805. (From the Order 8 paper by Satoh &al.) The trick: For large N, the number of abelian tables is N^(N*(N+1)/2). [Divide by ~N! to discount isomorphs, but it doesn't change the gross order.] Very roughly, (N^N^2)^.5. The semigroups are dominated by the Dull Semigroups, which satisfy the equation A(BC)=(DE)F, or equivalently, XYZ=0. The multiplication table has an L-shaped swath of 0s at the top and left edge; the remaining portion of the table consists of random values <= the thickness of the L. The L that gives the most semigroups solves N = L (2 logL + 1), roughly L ~= N / (2logN). This gives (again very roughly) (N^N^2)^1 tables. Empirically, most semigroups are Dull: 85% of the 7s, and 99% of the 8s. I had a proof of this once, but can't recall it. (Usually a bad sign.) Since 1 > .5, the Semigroups must eventually overtake the Abelians. I wrote a Lisp function to do the estimates. I assumed the crossover would be around N=12, and was surprised it was so large. The crossing is sharp, and isomorphisms don't change it. Rules like Mid-Quartile-Swap, (AB)(CD) = (AC)(BD), one of the Average axioms, have even more tables than the semigroups. They have a sub-population of Dull-4 tables, where any product of four things, in any grouping, equals 0. These tables have an outer L of 0s, like the semigroups, and then an inner L with values <= outer-L-thickness, and then a lower-right square region with values <= outer+inner-L-thickness. These outnumber Dull Semigroups. In fact, because it has no top-level singleton, the MQS rule has an even larger set of Dullish tables, where the 0-region is only a small square in the upper-left corner, and the less-restricted values occupy a big lower-right L. For any Rule where each side has 2 or more operations, (like the ternary Defective Distributive Law for Majority, AB.CDE = ABC.ABD.E), Dull-ness will be a consideration, and will likely dominate the numbers. As the number of operations in the Rule is increased, more nested Ls are added, and the Dulls increase. Dullness can be somewhat counteracted by Commutativity, and is vanquished by Idempotence, or any rule with a singleton on one side. <the end of Dullness>

2 1

[math-fun] Re: counting Latin squares
by dasimov＠earthlink.net 21 Jul '05

21 Jul '05

Gary McGuire writes: << Call two completed sudoku grids "equivalent" if one can be obtained from the other by a sequence of the following operations: 1) permutation of the digits 1-9 2) permutation of the rows. These come in two types: a) permute the three rows within a given band b) permute the bands 3) permutation of the columns, same two types. 4) rotation, reflection >> This makes me realize that my previous attempt to define an equivalence relation on Latin squares was much too weak. (I'm more interested in Latin squares than Sudoku grids with their kind-of random condition on certain 3x3 squares.) Call two of these equivalent if they become identical by some combination of the following: 1) any permutation of the n symbols 2) any permutation of the n rows 3) any permutation of the n colums 4) application of any dihedral element from D_4. This suggests most equivalence classes have 8(n!)^3 elements (but not necessarily that many since some combinations of these equivalencing operations may not change anything). Problem: How many n by n Latin squares are there before taking equivalence classes? How many equivalence classes are there? --Dan

1 0

[math-fun] sudoku diagonals
by Gary McGuire 21 Jul '05

21 Jul '05

>HOW ABOUT THE SUPERDOKU WITH ADDITIONAL DIAGONAL AND ANTIDIAGONAL >CONTAINING ALL DIGITS? > >JOHN MCKAY These have been around for yonks in the puzzle books as a variation on "number place" puzzles, which is what sudoku is called sometimes. You can certainly have ordinary sudoku completed grids that have this property, one below. I don't know if this is what you meant, but you can also have sudoku puzzles that cannot be done without having this extra piece of information. If you want *all* the diagonals (the pan-diagonals) to have all the digits, then I don't know the answer. Gary McGuire --------------------------------- 492|681|573 357|249|168 816|735|924 ---+---+--- 573|168|492 168|924|357 924|573|816 ---+---+--- 681|492|735 249|357|681 735|816|249

1 0

[math-fun] sudoku groups
by Gary McGuire 21 Jul '05

21 Jul '05

One of the big sudoku questions was: How many completed Sudoku grids are there? This was answered, see http://www.shef.ac.uk/~pm1afj/sudoku/ The answer is 6670903752021072936960. Call two completed sudoku grids "equivalent" if one can be obtained from the other by a sequence of the following operations: 1) permutation of the digits 1-9 2) permutation of the rows. These come in two types: a) permute the three rows within a given band b) permute the bands 3) permutation of the columns, same two types. 4) rotation, reflection A sequence of these transformations that maps a grid to itself is called an automorphism of the grid. Example: 124|567|893 378|294|516 659|831|742 ---+---+--- 987|123|465 231|456|978 546|789|321 ---+---+--- 863|972|154 495|618|237 712|345|689 the permutation (1397)(2684) on the digits followed by a clockwise rotation through 90 degress is an automorphism. Question: what are the possible automorphism groups? Or equivalently, how many sudoku grids are there up to equivalence? This has been answered, see http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html Now: is this helpful in the problem of searching for a sudoku puzzle with 16 clues? I think fated sets are invariant under an automorphism. Therefore we only need choose one grid from each equivalence class and compute all the fated sets. Unfortunately there are 5472730538 equivalence classes. Anyway, in the computer search for a 16, we don't want to choose two grids that are equivalent. Gary McGuire

1 0

[math-fun] Irrationality proofs
by dasimov＠earthlink.net 19 Jul '05

19 Jul '05

The cutest proof I've seen that sqrt(2) is irrational goes like this: If the hypotenuse of a 1,1,sqrt(2) rt. triangle = p/q, then magnifying by q gives a similar triangle w/ all sides integers L,L,H. Call the sides L1,L2,H. Using (L1 int H) as center, draw the 45-deg. circular arc A of radius L between H and L1. [Erecting a perpendicular to H from where A meets H, extended to reach L2] defines a smaller, similar right triangle whose sides are H-L, H-L, 2L-H (the last by the equality of 2 tangents to a circle from an external point). We can now continue this process to obtain an infinite sequence of similar rt. triangles w/ integer sides, each smaller than the last -- contradiction. (Tom Apostol is one discoverer of this proof; maybe JHC is another?) QUESTIONs: Can this proof be imitated to show other square roots are irrational? (If so, how do we avoid proving that, e.g., sqrt(3^2 + 4^2) is irrational?) What about just trying to show all sqrt(n^2 +1) are irrational? --Dan

1 0

[math-fun] sudoko
by Richard Schroeppel 19 Jul '05

19 Jul '05

I was puzzled about Sudoku, mentioned in a recent message. It's apparently well known on the puzzle circuit. Here's an example I swiped from last Monday's USA Today -- they've started running a daily puzzle. - 6 - | 3 - 8 | - 7 - - - - | - - - | - - - 4 3 - | 6 - 1 | - 9 5 ------+-------+------ - - 5 | - 4 - | 7 - - - - - | - 1 - | - - - - - 1 | - 2 - | 8 - - ------+-------+------ 9 2 - | 4 - 5 | - 3 6 - - - | - - - | - - - - 8 - | 7 - 9 | - 4 - In a completed sudoku, each row and column of the puzzle has one occurence of each digit from 1-9. (This makes it a Latin Square.) In addition, each of the nine marked 3x3 subsquares has (one of) each digit. The solver's job is to fill in the blanks in the puzzle. I think the one above would qualify as simple; I was able to complete it without much "advanced reasoning". Rich rcs(a)cs.arizona.edu

6 8

[math-fun] Re: SUDOKU - TO SUPERDOKU
by MCKAY＠vax2.concordia.ca 19 Jul '05

19 Jul '05

HOW ABOUT THE SUPERDOKU WITH ADDITIONAL DIAGONAL AND ANTIDIAGONAL CONTAINING ALL DIGITS? JOHN MCKAY

1 0

Re: [math-fun] sudoko
by dasimov＠earthlink.net 19 Jul '05

19 Jul '05

Just curious: Is there a closed formula L(n) for the total number of Latin squares on n symbols? (If not, how 'bout an asymptotic expression?) (Even better: Assume we equate two Latin squares if they differ only by 1) a dihedral transform 2) a permutation of the n symbols 3) two cyclic permutations, applied resp. to the rows and columns. These should lower the count by a factor of roughly 8 n^2 n!. Roughly, since a 3) might yield the same result as a 2). Making this exact seems hard.) --Dan

1 0