View previous topic :: View next topic 
Author 
Message 
nataraj
Joined: 03 Aug 2007 Posts: 1029 Location: Vienna, Austria

Posted: Mon Dec 17, 2007 9:34 pm Post subject: nataraj's animated sudoku walkthru 


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 


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

Posted: Wed Dec 26, 2007 2:43 am Post subject: 


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 twocandidate (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 XYwings. 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 XYZwings. Also look for possible remote pairs and WWings.
Still not done? Well, my friend, it is time to fill in all the candidates and start slogging. (Man, I hate looking for Xwings!) But, coloring is fun!
Keith 

Back to top 


nataraj
Joined: 03 Aug 2007 Posts: 1029 Location: Vienna, Austria

Posted: Fri Jan 11, 2008 6:43 pm Post subject: 


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 )
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 




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
