Sunday, 29 November 2009

Computers are fast!


Killer Sudoku is a popular variant on the perennial Sudoku game found in British newspapers. The same rules about the numbers 1 to 9 appearing only once in row, column and 3x3 box still apply, but unlike Sudoku, the puzzle doesn't come with any numbers filled in. Instead, cells are groups with dotted lines and the total of all those cells are written in.

Here's part of a puzzle. The two cells grouped by a 10 could be 1+9, 2+8, 3+7 or 4+6. (It can't be 5+5 because that would mean two 5s in same box.) Not a lot to work on, but also look at the three cells grouped by a 23 in the same 3x3 box; The only possible fit is 6+8+9. This means the only possible fit for the 10 group is 3+7, as all the possibilities would clash with the 6,8 or 9 required to make the 23.

I could go on. If you want to complete the puzzle, its the Guardian's puzzle number 166. The point of this article isn't to solve the puzzle, but something I observed along the way.

Am I sure there's no other way to split 23 into three parts, 1 to 9, without duplicates? I confess, mental arithmetic is not my forte. Part of the puzzle solving process for me is going through each dotted group and building a crib sheet on all the possible ways to make the total, so I can cross them off later.

This isn't a part of the puzzle I particularly enjoy, so I decided to automate it. (Is that cheating? I don't think so in my circumstances, but that's another topic of conversation.)

So I sat down and designed an algorithm...
  • Input: n (the number of cells, 2 to 9) and m (the total, 3 to 45).
  • Output: All solutions to SUM(n integers 1-9 without duplicates) = m.
Only problem, as with so many mathematical endeavors, life got in the way. By the time I had worked out a basic algorithm, I noticed it was 2AM and suddenly felt rather tired, but I didn't want to stop, so I simplified my plan.

Loop, starting with (1,1,1,1,1,1) then (1,1,1,1,1,2), ending with (9,9,9,9,9,9). For each combination, if they add up to the target, have no duplicates, and is in order, add it to the list. It was a very inefficient algorithm, but it would work and I wouldn't have to expend much thought on building it.

Then something surprising happened. While testing with 2 or 3 digit targets, it was near instantly fast, but I had expected 6 digit targets to take something like a few minutes. In fact, it took 2 seconds.

2 seconds!!!!! I had learnt to write programs on my early 80s BBC Micro and I was used to leaving it running overnight calculating something like this. Computers are fast!

(If all that seems too much like hard work. Wikipedia have built the tables for you.)

10 comments:

  1. These are my favorite type of puzzle. Interesting insight you have. Thanks!

    ReplyDelete
  2. In the time it takes light from the monitor to reach your eyes, the computer has processed about a dozen instructions.

    ReplyDelete
  3. You could optimize the thing if you started with something like (1,2,3) then (1,2,4), ..., (1,2,9), (1,3,4), (1,3,5)... you get the idea. This way you exclude permutations of the same combinations.

    I think, you could do 10^7-10^8 operations in 5-10 seconds on a modern processor, so this could come in handy for n>=8.

    ReplyDelete
  4. There are only a little over one half million 6 digit sequences of the values 1..9, and really, there are only 84 ways of choosing 6 items, all orderings being the same, and a little over 60k of allowing permutations.

    A good article for generating sets with/without permutations is: http://www.thelowlyprogrammer.com/2010/04/indexing-and-enumerating-subsets-of.html . Code for C#, Java, and Python is available.

    ReplyDelete
  5. comprooters r fast. oh. i did not no that

    ReplyDelete
  6. Reminds me of the quote usually attributed to Ken Thompson: When in doubt, use brute force.

    ReplyDelete
  7. *Main> [ ((a,b,c),(d,e)) | a <- [1..7], b <- [2..8], c <- [3..9], d <- [1..8], e <- [2..9], a < b, b < c, d < e, List.intersect [d,e] [a,b,c] == [], a+b+c == 23, d+e == 10 ]
    [((6,8,9),(3,7))]

    ReplyDelete
  8. Fast is relative. A calculation with 100% CPU usage taking 2 seconds on a server taking in thousands of requests a second would get you fired if you spent 2 seconds per...
    Especially if they reviewed the code after it reached production. (It doesn't matter that reviews should have caught it long ago.)
    I'm sure the author was amazed at how fast today's computer was vs. the 80's. I wasn't impressed with these "PC" thingies since I worked on mainframes and was saddled with supporting the office's first PC. Today's PC can almost do all the work one mainframe can do now.
    Fast is relative. If you could build logic that would just increment the numbers without the overhead of loops and looking at the numbers to see if they are giving the right answer, a 1GH machine should give an answer in less than 1 thousandth of a second.
    I built a simlar puzzle solver that calculates a solution from under a second to a few minutes depending on what numbers are being solved, but if I used the same method of calculating the time and the same method of calculating the solution, a 4GH machine should get the answer in 10 to the 30'th power years from now.
    Make the machine a billion times faster than that. Now it's only 10 to the 21'st years. Uhh, I don't think I'll wait up for it.

    ReplyDelete
  9. Dude that is the funniest thing I've read all day, thanks for writing it!

    ReplyDelete
  10. I'm the one that wrote "Fast is relative" and I'm back. You said you wanted something fast and easy to do. OK, I get that you knew there were better ways and accepted your way is "easy".
    Nope, not easy. Lazy thinking is more like it. You ended up doing a lot more work than you needed to do.
    The algorithm:Give the number and the number of positions. OK, so now I'm tied to your computer program to get my crib sheet. I've also got to write a user interface to supply those numbers and return those answers. (A windows app?)
    I'm thinking Hmmm, if we put the numbers in excel, it has great filters just give it all the possible solutions and all the number of positions that can do the solution.
    Sorry, I didn't read your original post of giving up to 9 positions. 9 is ridiculous, there is only one answer and its the same as giving no clues in that sheet. 8 is almost as bad since there are 8 possible numbers and only one solution possible. It gives you one answer on the sheet from 1 to 9 if the number is 44, the answer is 1 and if the number is 36, the answer is 9. I'm not going to fix my algorithm to go up to 8 because I don't do killer suduko. (KenKen, yes. Regular suduko, yes.)
    You have a lot of checking to do when you get up to 6 numbers. The first number can't be equal to the other five, second to the other four, etc. That doesn't remove duplicates. (1,2,3,4,5,6) isn't the same as (5,1,2,3,4,6) but your routine would produce both and I don't want to see both, I want a distinct list of numbers.
    OK, I fall into the trap of making things complex when it can be simple as well. I'm thinking, set up a two dimensional 5X37 array of arraylists, build and store arrays, then I can list the results in numerical order and by the number of the solution and positions, when it hits me. DUMMY! Excel is pretty good at sorting, let it do it for you.
    Well, I'm not that good at VB.NET, I'll use that. Loop the first number from 1 to 8. Loop the second number from the prior number plus 1 to 9. Repeat the second loop's process 4 more times. This is going to produce about 32K results (Wrong, 456 results.) and I don't know if “For i6 = 12 To 9” won't loop, loop once and quit or be “real helpful” and implicitly add “by -1” to it, I'll add if tests to make sure.
    I'll add stats so I know how many milliseconds this takes and a loop counter. I wrote and tested the console app in about half an hour. While debugging, the code ran in about 3/10 of a second. When I executed it on a command line and redirected output to a file it ran in 8 milliseconds. I'm betting the majority of that time was for IO. Hmmm, one number in 6 positions in 2 seconds or all possible numbers for 2 to 6 positions in 0.008 seconds.

    Here is the last loop
    For i6 = i5 + 1 To 9
    Console.WriteLine("{0},6,{1},{2},{3},{4},{5},{6}", i1 + i2 + i3 + i4 + i5 + i6, i1, i2, i3, i4, i5, i6)
    lp += 1
    Next i6

    Note that “,6,” is changed in each loop so they are 2 through 5.
    After the first loop finished I executed
    i1 = (DateTime.Now.Ticks - dts.Ticks) / 10000
    Console.WriteLine("{0},milliseconds,{1},loop,{2},{3}", i1, lp, dts.Millisecond, DateTime.Now.Millisecond)

    I put in the last two fields to verify what I thought the number of ticks in a millisecond was.
    Before the loops started I executed
    Dim dts As DateTime = DateTime.Now
    Dim lp As Integer = 0
    Console.WriteLine("total,NumItms,Num1,Num2,Num3,Num4,Num5,Num6")

    ReplyDelete