[math-fun] "Self-erasure surviving numbers"
Hello Seqfan and math-fun, Take an integer like 36, for example. Concatenate an infinite amount of copies. You get: 363636363636363636363636363636... - read the leftmost digit -"3"-, - jump *over* 3 digits (to the right), land on (3) and erase it: 3636(3)6363636363636363636363636... ^ - read the leftmost unread digit, jump only visible digits, erase: 3636(3)6363(6)36363636363636363636... ^^ - repeat until you see a substring like this [...(a)36(b)...] [(a) and (b) are erased digits - "36" is the integer you are, testing]: bingo, you have found a "Self-erasure survi- ving number" (SESN): "36" is such a number: 3636(3)63(6)3(6)36(3)(6)3(6)36363636363636... ^^^^ ^^ .. <-- hit This erasing technique gives sometimes quite complicated pat- terns. "16", for instance, is not a SESN -- but it takes a while to see: 16(1)616(1)61(6)1(6)(1)6(1)(6)1(6)1(6)1(6)1(6)(1)6(1)616(1)61(6)1(6) ^^ ^^^ ^^ ^ ^ ^ ^ ^ ^ ^ ^^^ ^^ ^ |_______________________________________________| recurrent pattern The first SESN I have found by hand are: 0 1 2 3 4 5 6 7 8 9 10 20 23 24 25 26 27 28 29 30 32 36 37 38 39 40 42 ... [BTW, reading "0" means erasing the closest visible digit immediately to the right] No SESN > 10 begins with "1" -- see why? No SESN > 29 begins with "2", etc. The sequence is finite, thus. Last term? And what about recurrent patterns: do all integers behave like that? Could some strings be definitely "chaotic"? I guess no... Best, É.
The sudoku puzzles that the L.A. times has started carrying have me wondering how the puzzles are created and validated, and especially how it would be done without resorting to brute force computer techniques. I'm guessing the puzzles start with the solution, then remove squares until some desired degree of difficulty to reconstruct the solution is achieved. The Times puzzles are graded "easy" "moderate" and "diabolical". 1) Are all "solved puzzles" the same intrinsic complexity, or are some intrinsicly easier than others. 2) How do they validate that the solution for a puzzle is unique, and how do they grade the level of difficulty.
Almost all Sudoku (or Number Place) puzzles are computer generated and computer verified. A Google search will give you a number of sites that will generate and solve puzzles for you. The notable exception is Japan, where most all puzzles are designed by hand and conform to stylistic guidelines, such as rotational symmetry of the clue number placement. The puzzles come in a wide range of complexity. Some can be solved with just a handful of solving rules. And I have seen some that the best solvers in the world cannot solver without resorting to extensive trial and error (essentially brute force). I'd be curious to see what the LA Times calls "daibolical"; please send me the clues via email. Difficulty would be hard to determine by a brute force solver. I image that they are rated by human test solvers, or a program that uses a range of solving rules and rates the level of complexity reached during the heuristic search. Those that appear in the U.S. Puzzle Championship (wpc.puzzles.com) are all designed by hand and are variations on the theme (since many of us have been doing Number Place for 10+ years and are somewhat tired of the standard style). For example this year we had one on a torus, with the 3x3 regions replaced by shapes that wrapped around one or two edges of the grid; and one with the number clues given as partial LED readout. Nick Dave Dyer wrote:
The sudoku puzzles that the L.A. times has started carrying have me wondering how the puzzles are created and validated, and especially how it would be done without resorting to brute force computer techniques.
I'm guessing the puzzles start with the solution, then remove squares until some desired degree of difficulty to reconstruct the solution is achieved. The Times puzzles are graded "easy" "moderate" and "diabolical".
1) Are all "solved puzzles" the same intrinsic complexity, or are some intrinsicly easier than others.
2) How do they validate that the solution for a puzzle is unique, and how do they grade the level of difficulty.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Nick Baxter wrote:
Difficulty would be hard to determine by a brute force solver. I image that they are rated by human test solvers, or a program that uses a range of solving rules and rates the level of complexity reached during the heuristic search.
I researched this just a little bit not long ago, and found that at least some places have a list of solving rules, of increasing complexity, and the rating is based on the highest-complexity rule that you need to use to solve it. In particular, a puzzle is "easy" iff it can be solved by repeatedly filling in a box with the only number that can go there. But surely there's no agreed-upon standard for ratings, and I can't locate my source for that information, so it's just about useless. Donning my editor's cap, let me mention that I'd be happy to run an Intelligencer column on sudoku-related material -- gotta cache in on those hot fads, don'cha know -- if anyone has something interestingly mathematical to say about it. Noteworthy facts: just a month or so ago, Bertram Felgenhauer managed to enumerate solutions; there are 6,670,903,752,021,072,936,960 9x9 latin squares which obey the 3x3 subgrid constraint. I learned this from the very good Wikipedia article: http://en.wikipedia.org/wiki/Sudoku Oh, and the general solution problem on an n^2 x n^2 grid is NP-complete, as proved by Yato and Seta. --Michael -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Donning my OEIS cap, let me just mention - with respect to sudokus - that this is now sequence A107739, and indeed 6670903752021072936960 is given there as the third term! Neil
participants (5)
-
Dave Dyer -
Eric Angelini -
Michael Kleber -
N. J. A. Sloane -
Nick Baxter