Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Ioannis on 15 Aug 2005 14:38 My uncle is possessed with Sudoku. He spends hours marking and erasing but he finally solves it. He is a civil engineer and also has a Microsoft certificate for Excel usage, or something like that. I suggested he ported the game to Excel, using a template, so he doesn't have to scratch and erase all the time. He was enthused with the idea, but then a natural question arose: What would be a necessary and sufficient condition so that he could check whether his step k is correct? I haven't thought about the puzzle a lot, but the first thought that came to my mind was to check that sum(i,i=1..9)<=45. However this checks only completed rows and columns and even for those I am not sure that this condition is sufficient. Any ideas on what kind of conditional he could program on the Excel cells to check his every step? Thanks much. -- I. N. Galidakis http://users.forthnet.gr/ath/jgal/ Eventually, _everything_ is understandable
From: Stephen J. Herschkorn on 15 Aug 2005 15:24 In sci.math, Ioannis wrote: >My uncle is possessed with Sudoku. He spends hours marking and erasing but >he finally solves it. > >He is a civil engineer and also has a Microsoft certificate for Excel usage, or something like that. > >I suggested he ported the game to Excel, using a template, so he doesn't >have to scratch and erase all the time. > >He was enthused with the idea, but then a natural question arose: > >What would be a necessary and sufficient condition so that he could check >whether his step k is correct? > >I haven't thought about the puzzle a lot, but the first thought that came to my mind was to check that sum(i,i=1..9)<=45. > >However this checks only completed rows and columns and even for those I am not sure that this condition is sufficient. > >Any ideas on what kind of conditional he could program on the Excel cells to check his every step? > I should not admit it, but I have been doing sudokus lately. I do do them on an Excel spreadsheet for ease of makring and erasing. Here are some things I do: I use colored fonts to mark certainty of cells. All the initial numbers are red; I copy this to another worksheet in case I have to start all over. (The latter event does not happen much since I implemented the following precautions.) Cells which are implied by the initial cells I mark blue. Cells implied by red and blue cells I mark green. Etc. - the sequence I have come up with is red, blue, green, violet, brown, rose, lavender, and dark grey. Often, I don't get past green or violet - I stop after a while. All other cells are black. Now, what does that get me, you ask? Well, it happens fairly often that I make a mistake and come up with a contradiction. At this point, I sometimes have to erase all the cells I filled in. With my method, I just erase all the black cells. Then I check the colored cells in order to make sure they are correct and pick up from there. Sure beats starting from scratch. I do build column, row, and box sums into my spreadsheet. This is a necessary but not sufficient condition for a correct final solution. However, given that all twenty-seven sums are 45, I can easily eyeball the solution, and this is good enough for me. Sometimes, I get myself to a point where all I can do is guess and see if this leads to a contradiction. For this, I just copy the current worksheet and put a border around the cell where I make the guess. Ioannis, I will e-mail you my Excel file for this. -- Stephen J. Herschkorn sjherschko(a)netscape.net Math Tutor in Central New Jersey and Manhattan
From: Stephen J. Herschkorn on 15 Aug 2005 15:28 > Ioannis, I will e-mail you my Excel file for this. Except that I can't - the e-mail you give doesn't work. Send me an e-mail if you want it. -- Stephen J. Herschkorn sjherschko(a)netscape.net Math Tutor in Central New Jersey and Manhattan
From: Ioannis on 15 Aug 2005 15:40 ý "Stephen J. Herschkorn" <sjherschko(a)netscape.net> ýýýýýý ýýý ýýýýýý news:G%5Me.11665$9v3.9929(a)fe09.lga... > > > Ioannis, I will e-mail you my Excel file for this. > > > Except that I can't - the e-mail you give doesn't work. Send me an > e-mail if you want it. Yes, sorry. My posting address is bogus. I've sent you an email. Thanks again! > -- > Stephen J. Herschkorn sjherschko(a)netscape.net -- I. N. Galidakis http://users.forthnet.gr/ath/jgal/ Eventually, _everything_ is understandable
From: mensanator@aol.compost on 15 Aug 2005 16:00
Ioannis wrote: > My uncle is possessed with Sudoku. He spends hours marking and erasing but > he finally solves it. > > He is a civil engineer and also has a Microsoft certificate for Excel usage, > or something like that. > > I suggested he ported the game to Excel, using a template, so he doesn't > have to scratch and erase all the time. > > He was enthused with the idea, but then a natural question arose: > > What would be a necessary and sufficient condition so that he could check > whether his step k is correct? You can't. You may have to backtrack because what looks good at step k may lead to a contradiction at step k+n. > > I haven't thought about the puzzle a lot, but the first thought that came to > my mind was to check that sum(i,i=1..9)<=45. > > However this checks only completed rows and columns and even for those I am > not sure that this condition is sufficient. > > Any ideas on what kind of conditional he could program on the Excel cells to > check his every step? Ok, set up your grid at R1C1:R9C9 4 5 9 8 7 8 6 9 6 4 5 3 1 2 5 8 3 7 6 4 6 3 1 9 2 7 8 5 2 3 5 2 7 4 1 9 7 Now, off to the side, you make 5 calculation areas: a binary conversion, a row check, a column check, a region check and a combined check. For the binary conversion (R11C11 in my example), put the following formula in each of the 81 cells: =IF(RC[-10]>0,2^RC[-10],0) This converts the numbers in the grid to single-bit binary numbers where the number determines which bit is a 1. This gives you: 0 0 0 16 0 0 32 0 0 0 0 0 512 0 256 0 0 128 0 256 64 0 0 0 0 0 0 0 512 0 64 16 32 0 0 8 2 4 32 256 8 128 64 0 0 16 64 8 2 512 4 128 256 32 0 0 0 4 0 0 8 32 0 4 0 0 128 0 16 0 0 0 0 0 2 0 0 512 0 128 0 The row check (R1C21:R9C29 in my example) sums the numbers in each row, using the formula (in each cell): =SUM(RC11:RC19) 48 48 48 48 48 48 48 48 48 896 896 896 896 896 896 896 896 896 320 320 320 320 320 320 320 320 320 632 632 632 632 632 632 632 632 632 494 494 494 494 494 494 494 494 494 1022 1022 1022 1022 1022 1022 1022 1022 1022 44 44 44 44 44 44 44 44 44 148 148 148 148 148 148 148 148 148 642 642 642 642 642 642 642 642 642 (yes, the results repeat horizontally, that's intentional) The column check (R11C21:R19C29 in my example) sums the columns using the formula (in each cell): =SUM(R1C[-10]:R9C[-10]) 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 22 836 106 982 536 948 232 416 168 Likewise, I have a region sum (R21C21:R29C29 in my example) 320 320 320 784 784 784 160 160 160 320 320 320 784 784 784 160 160 160 320 320 320 784 784 784 160 160 160 638 638 638 1022 1022 1022 488 488 488 638 638 638 1022 1022 1022 488 488 488 638 638 638 1022 1022 1022 488 488 488 6 6 6 660 660 660 168 168 168 6 6 6 660 660 660 168 168 168 6 6 6 660 660 660 168 168 168 BUT -- unlike the other tables, the formula is only the same for each cell in the region, so I'll show just one example: at R21C21:R23C23 = SUM(R1C11:R3C13) You should be able to figure out the others. Now, finally, we want to OR together the three summation tables to make our combined check. You can binary OR the numbers in a VB macro: Function orthem(a, b, c As Integer) As Integer orthem = a Or b Or c End Function So the combined check (R11C11:R19129 in my example) has (in every cell) =orthem(R[-10]C[10],RC[10],R[10]C[10]) giving 374 884 378 1014 824 948 248 432 184 982 964 1002 982 920 948 1000 928 936 342 836 362 982 856 1012 488 480 488 638 894 638 1022 1022 1022 1016 1016 1016 1022 1022 1022 1022 1022 1022 494 494 494 1022 1022 1022 1022 1022 1022 1022 1022 1022 62 878 110 1022 700 956 236 428 172 150 982 254 982 668 948 252 444 188 662 966 750 982 670 950 746 938 682 When your grid is correctly completed, every cell will have 1022. Note in the example there is one completed row and one completed region. Of course, converting the OR'ed results to binary (upper left region only shown) R11C1:R19C9 =IF(ISBLANK(R[-10]C),LEFT(DEC2BIN(INT(RC[10]/256),2) & DEC2BIN(MOD(RC[10],256),8),9),"") 010111011 110111010 010111101 111101011 111100010 111110101 010101011 shows which numbers are possible for each cell (the blank ones already are solved and are not shown). A single 0 would indicate a forced move. Seeing 111111111 indicates you've made a mistake somewhere since the cell is blank and there are no digits that can be placed there. I find counting the bit positions a pain so I added another grid to convert the bit positions back to digits: R21C1:R29C9 =IF(R[-10]C<>"",IF(MID(R[-10]C,1,1)="0","9","-") & IF(MID(R[-10]C,2,1) ="0","8","-") & IF(MID(R[-10]C,3,1)="0","7","-") & IF(MID(R[-10]C,4,1) ="0","6","-") & IF(MID(R[-10]C,5,1)="0","5","-") & IF(MID(R[-10]C,6,1)="0","4","-") & IF(MID(R[-10]C,7,1)="0","3","-") & IF(MID(R[-10]C,8,1)="0","2","-") & IF(MID(R[-10]C,9,1)="0","1","-"),"") 9-7---3-- --7---3-1 9-7----2- ----5-3-- ----543-1 -----4-2- 9-7-5-3-- BTW, this does not necessarily solve the puzzle (I'm still stuck on this example). On easy puzzles, I can usually just follow the forced moves from start to end. On hard ones, I sometimes have to backtrack because the discrepency may occur after a dozen moves. > > Thanks much. > -- > I. N. Galidakis > http://users.forthnet.gr/ath/jgal/ > Eventually, _everything_ is understandable |