Solving with Excel

Advanced methods and approaches for solving Sudoku puzzles

Solving with Excel

Postby Guest » Fri Mar 11, 2005 3:55 pm

As I've said on another thread [Administrator: see "Trial & Error?" post in this forum], I have found 2 Fiendish T2 puzzles with more than one solution. I do them in an Excel grid that sums each line, column and box to check I get "45". It also does a "COUNTIF" on each cell in the grid for each of the digits 1 - 9. If all the rows, columns and boxes each add up to 45 and if there are 9 of each digit in the whole grid, then that is a valid solution.

When logic fails and I can't get any further, I set the font colour in all the un-filled squares to red. I then try a possible number in a square that I think might unlock the puzzle. If I wind up with a dead-end (2 of the same number in a square, for example) I hit "Undo" until I'm left with the original "try". I then re-work the puzzle with the same number, to check that I didn't make a mistake the first time. If I arrive at the same problem, I re-work the puzzle with the other possible number. On at least 2 occasions to date, I have managed to solve the puzzle in 2 ways.

Therefore, I would suggest, the claim that all T2's puzzles have a unique solution is in error.
Guest
 

Postby shakers » Fri Mar 11, 2005 4:33 pm

I'm now seeing boxes and numbers when I close my eyes, so I'm probably wrong, but surely to make sure the solution is valid, your Excel sheet would also need to use COUNTIF on each 3x3 box...?
shakers
 
Posts: 93
Joined: 10 March 2005

Postby Guest » Fri Mar 11, 2005 6:20 pm

No, you just need to set up 9 cells with the following formula:

=COUNTIF(A1:I9,N)

where N is digits 1 to 9.

Each column, each row and each box should add up to 45 when the puzzle is solved. By checking that there are also 9 of each digit as well, you're eliminating any possibility (hard to see how anyway) of duplicates/missing numbers.
Guest
 

Postby Guest » Fri Mar 11, 2005 9:21 pm

OK, now it's absolutely foolproof... I've done conditional formatting on each row, column and box summation cell, so that if, and only if, it contains one of each of the digits 1 to 9, it turns the cell background green. Any duplicates in a completed line/box and it doesn't change colour.

So, the rows, columns and boxes each add up to 45, there are 9 of each digit and all the summation cells coloured green means that the solution is valid.

Mathematically, that's probably over-kill, but there's no doubt now.
Guest
 

Postby Guest » Tue Mar 15, 2005 10:01 pm

If this is true, can you give us the 'apparent' 2 solutions to some of the puzzles then..........

Lovely as Excel may be, I'd rather see the proof for myself, rather than accept your method from EXCEL, since as someone who dabbles in programming a bit, I know how easy is it to overlook pieces of information.
Guest
 

Postby MC » Wed Mar 16, 2005 3:47 pm

Sorry - can't give you the dates of the puzzles that had 2 solutions because, as I said in another thread in reply to Pappocom, they were a few weeks ago and they went in the bin. The point to note is that one solution could be achieved by logic alone, while the other involved a guess. Most of the time, guesses arrive at a dead end with duplicates in the same row/column/box. These 2 didn't.

Think about it, though... if all the rows, columns and boxes add up to 45, and if there are 9 of every digit in the solution and also if each row, column and box is verified as containing one of each digit, how can the solution be anything other than a valid one? As I said, mathematically, that's over-kill, but there can be no doubt about it - it's valid.

For what it's worth, I've been programming computers in all sorts of languages for 27 years, from assembler up to C++... That's a bit more than "dabbling".:)
MC
 
Posts: 10
Joined: 11 March 2005

Postby Pappocom » Wed Mar 16, 2005 4:44 pm

... as I said in another thread in reply to Pappocom, they were a few weeks ago and they went in the bin.

Hi MC. You will remember I was asking for the two solutions and the original puzzle (or some way of identifying it - the paper, the date, the number).

In cases where people think they have found two solutions, it is nearly always because they have made a mistake in transcribing the original puzzle. If you miss out a clue, or put it in the wrong place, or put a different number where a clue should be, you will end up "solving" a different puzzle to the one which was set.

It is not surprising that "non-puzzles" have multiple solutions, or no solution. The selection of clues in a puzzle is not as random as it might seem.

Your Excel workings are telling you the truth. Everything cross-checks. But is it the puzzle that was set?

Also bear in mind that non-Pappocom puzzles do sometimes have multiple solutions, as I've documented elsewhere in these forums.

- Wayne
Pappocom
 
Posts: 599
Joined: 05 March 2005

Summing rows, cols and boxes

Postby Guest » Wed Mar 16, 2005 9:54 pm

Hate to say it MC, but there is a distinct flaw in your logic, which probably explains why you found more than one solution to a set puzzle. This is a simplified version to show the point using just the numbers 1-4 in 2x2 boxes to show the a solution that is clearly wrong, but meets your criteria:

.1......4......1......4 (10)
.3......2......2......3 (10)
.2......3......3......2 (10)
.4......1......1......4
(10) (10) (10) (10)

Each digit appears 4 times, each row adds up to 10 (1+2+3+4), as does each column and 2x2 box, but each row contains duplicates.

Time to think again perhaps! ;o)
Guest
 

Postby MC » Thu Mar 17, 2005 1:02 am

Pappacom - The 2 puzzles with multiple solutions were Pappacom puzzles from T2 in The Times a few weeks ago. This was before either the Telegraph or the Daily Mail started doing them. Therefore, they must have been Pappacom.

I elected to guess one of 2 possible numbers that I thought might unlock things. Having tried one guess successfully, I then thought I'd try the other. To my surprise, I came up with another valid solution. Knowing more now about the finer logical tricks one can use, I accept that I can now always solve these puzzles without resorting to guesswork.

I photocopy the puzzle so that (a) I can erase if necessary without ripping T2 and (b) I can start again if I really stuff it up. Transcription errors are not the issue. These puzzles occured before I designed the spreadsheet.

When I do transfer the puzzle to the spreadsheet (if I haven't managed to solve it in my coffee breaks at work) I transcribe row by row, then check once column by column, then re-check box by box. Again, transcription errors are not the issue.

IJ - Please go back and read my posts again. This is twice now that I've said that my spreadsheet has conditional formatting on the row, column and box summation cells. This turns the summation cell green IF AND ONLY IF THERE IS ONE OF EACH DIGIT in the associated row, column or box. If there are any duplicates, it doesn't turn green no matter whether it adds up to 45 or not. I appreciate the time you took making up that 4 x 4 grid to illustrate your point, but I had that possible error covered, as I stated a few posts earlier (This thread, post date - Fri Mar 11, 2005 8:21 pm). That is now the third time I've explained my logic in one thread.

For a copy of my spreadsheet, Click Here. The only cells that are unlocked are those for game entries, so I don't end up trashing my formulae by clicking in the wrong cell by mistake. There is no password on the spreadsheet, so it is a simple matter to unprotect it and see the formulae for yourself. To see the conditional formatting, highlight one of the summation cells then click on "Format" on the main menu bar, then "Conditional Formatting". Each one uses an AND statement with 9 COUNTIF conditions, one for each digit 1 - 9 in the row/column/box to which it refers. The end result of each AND statement will only be "TRUE" if all of its COUNTIF conditions are "TRUE" and it will then turn the cell green. If there are any duplicates, then one of the COUNTIF conditions will be "FALSE" and thus the AND statement will return a "FALSE" result, which means the cell stays white. When all 27 summation cells are green, the puzzle is solved. QED.

When you've finished looking at how I've prorammed the spreadsheet, close Excel without saving changes. It is very easy to mess up the conditional formatting statements if you try to use the arrow keys to see what's going on (use the mouse instead - click, hold and drag to scroll the statement in the little window). If you find that the cells don't turn green with a valid solution, then you stuffed up the formatting, so you need to download it again.
MC
 
Posts: 10
Joined: 11 March 2005

Spreadsheet

Postby Guest » Thu Mar 17, 2005 11:51 am

MC, What you actually said was...

"It also does a "COUNTIF" on each cell in the grid for each of the digits 1 - 9. If all the rows, columns and boxes each add up to 45 and if there are 9 of each digit in the whole grid, then that is a valid solution. "

And then more emphatically...

"No, you just need to set up 9 cells with the following formula:

=COUNTIF(A1:I9,N)

where N is digits 1 to 9"


No mention of conditional formatting on the columns and rows, and a specific denial of the need to count the members of each smaller box.

Later, having amended the spreadsheet you wrote...
"OK, now it's absolutely foolproof... [explains about extra tests] Mathematically, that's probably over-kill, but there's no doubt now."

The point is that this is not overkill, but absolutely necessary, because it mirrors the definition of a correct solution. Indeed the Sum=45 is completely useless as a test and totally unnecessary if you are checking for one of each digit. What I was trying to show is that before you added the correct tests the original method you described would have "passed" invalid solutions. So the fact that you didn't have these tests when you found multiple solutions means that one or more of them could easily have contained errors. It doesn't mean they did, of course, just that it is possible.
Guest
 

Postby Guest » Thu Mar 17, 2005 4:40 pm

These puzzles occured before I designed the spreadsheet.


Until I designed the spreadsheet, I had to check each row, column and box manually. There are 6 of us at work who do these puzzles and we all agreed I had found 2 solutions to one of the "Fiendish" puzzles - the second one that I found with 2 solutions, (a week or 2 later) I completed at home in the evening.

IJ - why do you think I introduced the second set of COUNTIF tests? For laughs? Or because I realised that shakers had a point, saw the fault in my logic and corrected it? (BTW, shakers - Thanks for pointing me down the right road. It took a couple of hours before the importance of what you were saying sank in and I then realised that I would need to check not just the 3x3 boxes, but also the rows and columns as well.)

If your initial post, IJ, had been along the lines of, "Your initial tests for a proof were incorrect, as you no doubt realised, but now they are, as you say, overkill," then we wouldn't be having this exchange. My reply would have been "Yup," and it would have ended there. As it is, you just seem to be points-scoring for the sake of it. This is never healthy in any forum. To that end, shall we agree that I initially didn't think things through sufficiently, that it is now sorted, thanks to shakers' prod in the right direction, and that you will let the matter rest?
Guest
 
Posts: 312
Joined: 25 November 2005

Postby MC » Thu Mar 17, 2005 4:46 pm

Hmm... Don't know quite why the previous post doesn't have my name on it. The Forum index certainly said "Log out MC" at the top, indicating that I had logged in. Maybe I opened a reply window before I logged in?
MC
 
Posts: 10
Joined: 11 March 2005

Postby Guest » Thu Mar 17, 2005 6:00 pm

MC, I don't mean to upset you old boy, but you did start this topic with a specific claim. Your original post said that T2 puzzles do not always have only one solution, and in justifying this claim you said you know because you use a spreadsheet to test your results.

All I was saying is that you should now withdraw that claim because, as you say yourself, the basis for it was insufficient.

However, you now have me really confused because the words "On at least 2 occasions to date, I have managed to solve the puzzle in 2 ways. " came at the end of a paragraph all about how you use the spreadsheet (the one without the correct tests). I assumed this meant the two subjects were connected, but now you say that you solved the two puzzles in question manually, before you designed the spreadsheet. So which was it - Excel or Paper?

I'm not trying to score points, I'm just more inclined to believe the Times if they say their puzzles only have one solution and that no guess work is necessary than someone who keeps changing their story. I say this because I have never had to resort to guess work with these puzzles (except the diabolical ones in the Telegraph) - it's always a case of "this number must go in this box".

I'm just making the point that the administrator has, though a bit more bluntly - either show us an example (i.e. The original puzzle, place and date of publication and two solutions) or admit that you may have been mistaken and drop the subject until you come across another. Call me a sceptic, but "Me and my mates saw one" has a strong pedigree amongst the proponents of UFO, Nessy, Yeti, etc.

You have said that your alternative solutions have come from pursuing guesses, so perhaps in the mean time you could just post a puzzle from the Times that forced you to make a guess (I'm assuming this is more common that finding additional solutions). Then we could have a more productive discussion about how to solve it without guessing.
Guest
 

Postby Guest » Fri Mar 18, 2005 2:44 am

For the record, the original post on this thread was originally a reply on another thread. "Admin" moved it to start this new one, so it's a bit like walking in on a conversation half-way through in some respects. It started on the "Trial & Error" thread, I think.

As to its content, yes, I'm afraid there was some sloppy thinking and construction in it and I can only plead mea culpa and the stinking cold I had last week. The 2 puzzles I guessed at and produced 2 alternative solutions for were before I started designing a spreadsheet to check for valid solutions. What I should have said was that this was the spark that prompted me to write the spreadsheet, so that it was easier to arrive at solutions more quickly. I thought that what I had was also enough of a proof of validity - as it turned out it wasn't but now it is. However, one tends to scan up/down/left/right and within the box before placing a digit and do one's checking on the fly for duplicates so you don't go haring off down a blind alley.

However, I stand by my claim which I will re-state thus: All T2 puzzles can be solved by logic alone with a unique solution. Some initially sparsely-populated T2 puzzles (aka "Fiendish"), however, do have the potential to have their grids filled in with an alternative "valid solution" that is arrived at using an element of guesswork (blind luck). By "valid solution" I mean 1 - 9 in every row, column and box with no duplicates.

Pappacom - could you please email me all the "Difficult" and "Fiendish" puzzles published in T2 from the last 9 weeks, so I can try to find one of the puzzles with a "guessed at" solution? You could bundle them up in a Library, as I downloaded the Su Doku program from the website a couple of days ago. Many thanks. I will have to try and not use the techniques I worked out over the last week or so and go back to the basic ones. <sigh>

Back to IJ... I assume your comment about being "a sceptic/..../UFO, Nessy, Yeti, etc." was meant to be amusing. What you've actually done is accuse me of being a liar and/or a fool. You then patronise me in the next paragraph. I would be grateful if you would retract both statements.
Guest
 
Posts: 312
Joined: 25 November 2005

Postby Pappocom » Fri Mar 18, 2005 3:21 am

MC, I presume? I don't mind sending one or two puzzles from The Times (I hold the copyright), but for commercial reasons I'd rather not bundle them into a Library book. Still, no harm done. If your theory is correct, the dubious puzzles are like the No. 9 bus - there'll be another one along soon.

I don't think IJ meant to upset you. In fact, he said he didn't. I hope we can enjoy IJ's comment as a witticism made without personal intent.

- Wayne
Pappocom
 
Posts: 599
Joined: 05 March 2005

Next

Return to Advanced solving techniques

cron