dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

nataraj's animated sudoku walkthru

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Test
View previous topic :: View next topic  
Author Message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Mon Dec 17, 2007 9:34 pm    Post subject: nataraj's animated sudoku walkthru Reply with quote

Wouldn't it be nice ...

... to see solving techniques in action ?
... "real" time ?

... to watch while the solving process is going on ?

This test might well develop into a full tutorial. For now, I am experimenting with animation support in PhotoDraw / ImageReady.

Showcase: dailysudoku.com puzzle of Sept. 13 (very hard).
Code:

+-------+-------+-------+
| . . . | . . . | . . 7 |
| . . . | 1 . 8 | . . 3 |
| . 4 . | . . 9 | 6 . . |
+-------+-------+-------+
| . 1 . | . 8 4 | . 3 . |
| 9 . 6 | 3 . 7 | 8 . 4 |
| . 3 . | 6 5 . | . 1 . |
+-------+-------+-------+
| . . 2 | 5 . . | . 8 . |
| 6 . . | 8 . 1 | . . . |
| 4 . . | . . . | . . . |
+-------+-------+-------+

It has a lot of different techniques - from very basic to rather advanced.

A) The Beginning

goal is to fill as many cells as possible without starting on pencil marks (yet), except when it comes "natural".

We start building the solution like we would build a house:

A1 - First Floor

"floor": three boxes in a row. "First Floor": The lower 3 rows (rows 7,8,9)
We look for 2 occurrences of a number in those 3 rows. This method is called "squeezing" (cf. http://www.sudocue.net/guide.php#squeezing)

Each of the two clues occupies a row and a box. What remains is a very small rectangle 1 row high and 3 cells wide. If two of those cells are already occupied we can fill the empty cell. If only one or none of the cells are occupied we place a "possibility marker" like we would place a bet on the roulette table.

Let's try it. Click on the thumbnail.



Now that wasn't so hot. Just one measly candidate - in two possible cells !

Let's see what we can do on the next floor...

A2 - Second Floor

Same technique. But this time we can do a little better. Whenever there are two or three possible cells for our candidate, we check what's going on in the rest of the house, namely on floors one and three. Because if one of the columns is alredy occupied we just might be able to place our candidate...

Maybe not the first time, but things change while solving a sudouku.



A3 - Third Floor

Now that is real easy!
No numbers occur more than once - nothing to do!

But since we feel quite comfortable now with the "floors" of our house, let's move on to higher buildings: "towers".

A4 - The Three Towers

Just like a floor is a set of 3 rows next to each other, a "tower" is a set of three columns. The method of squeezing works exactly the same way.

Click the thumbnail to continue:



B - Quick Wins and Little Helpers

B1 Quick Wins

Houses (row, column, box) with only 2 empty cells.

Box 5
Row 6

B1 Little Helpers

Row 5 - first pencil marks.
Box 6

Full rows / full columns within a box - squeezing with help.



C - Interlude - Loose Ends

So far into the process we've already solved nn cells.

Let's go check to see if we can squeeze some more, using these nn cells...


<animation>

That was good! We solved another cell and placed two more "bets" on neighbouring cells. It is good practice to always check for squeezing possibilities every time a cell is solved.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA

PostPosted: Wed Dec 26, 2007 2:43 am    Post subject: Reply with quote

Nataraj,

Merry Christmas!

This is very interesting! I looked at your message a couple of times before I figured out to go and click on the thiumbnails. Tha animations are great!

What you are showing is how I start a puzzle. First, I sweep the floors - sweeping is carrying two candidates into the third house. Next, I sweep the towers. Except, if I find a candidate in the towers, I sweep that floor again.

Then, I do it again. Sweep the floors. Except, now I am also looking for pairs of candidates. If you find a pair, pencil it in. Then, sweep the towers for pairs.

Next, go row by row. For any row that has four or more solved cells, consider the candidates for the unsolved cells. Look at how those candidates occur in the box and column, seeking candidates that can only be in one cell of the row. Do the same for the columns. Only pencil in candidates if they are pairs.

Now, go box by box. Look at each box that has four or more solved cells, for the candidates in each unsolved cell. Pencil in the candidates for each cell that has only two candidates.

Then, row by row, again. Pencil in candidates for cells that have only two. And, for the columns.

Now, look at the grid. You should have pencil marks in most of the two-candidate (bivalue) cells. Are there pairs you have not yet recognized?

I find it helpful to write the numbers

123
456
789

outside the puzzle, and to black out each candidate as it is solved in all 9 houses.

Look at each candidate. If it is solved in eight houses, you MUST be able to complete the ninth. If it is solved in most houses, look to see how you can complete the solution in the others.

With the above, you can solve almost any "easy" to "hard" puzzle, that requires only singles.

If you have a hard puzzle requiring more than basic techniques:

Scan the pairs to find possible triples, UR's and XY-wings. Look for intersections.

Then, go back to sweeping. Except, now fill in candidates in those cells that have three. Examine the grid for possible triples or quads, and for XY- and XYZ-wings. Also look for possible remote pairs and W-Wings.

Still not done? Well, my friend, it is time to fill in all the candidates and start slogging. (Man, I hate looking for X-wings!) But, coloring is fun!

Keith
Back to top
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Fri Jan 11, 2008 6:43 pm    Post subject: Reply with quote

Very Happy Very Happy Very Happy

Thanks for the encouragement, keith - glad you liked the animations! Unfortunately (luckily?), right now I have a lot of work so very little spare time... The animations were fun to do, too. Sooo, for the moment, consider this the pilot but don't hold your breath for the next episode (although it might well be worthwhile, what with naked pairs appearing and hidden singles in the closet - uh oh Wink )

I like your phrase "sweeping the floors". It is very graphic and actually much better than "squeeze". Only problem: "sweep" seems to be already used (in the "play online" section of daily sudoku) in the sense of "Sweep - show all possible numbers for each cell, overwriting your current pencil marks." which is definitely what I DO NOT do at this stage. Maybe we can settle for "mopping up" ? nah, no good.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Test All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group