SudokuWiki.org
Strategies for Popular Number Puzzles
Easy Sudoku Grading - Discussion
Sunday, August 23, 2009
Comment:Regarding the Easiest Sudoku Competition. I do not think that it is possible to produce a Sudoku (within the rules) better than a grade of 3.
I have produced two solutions, but they are not as elegant as Will Gibson has produced as they are not symmetrical.
My two grade 3 solutions are
123450670000030005070000001000060009790520406840001000900018000002096053060000007
and
012340560000020004060000009700098000001075002250000006000050097670410305830009000
I have also produced a Sudoku of grade 4 as follows
012340560000020004060000009000050007670410305830009000700098000001075042050000006
David Filmer
Thursday, August 27, 2009
David,
Regards the score of 3 or lower, I will explain how the low end scores work, and how I believe a score lower than 3 is possible.
You current winner with 3 is computed from the follow:
49 * (65 / 1000) = 3
49 is as large as you can get as it is 81 - 32 clues. So 49 solutions to be found. 1000 is my fulcurm normalising value. Don't ask. 65 is your non-normalied score. This was computed in the following way.
The puzzle is solved in 'rounds'. That is, given the state of the board all candiates removed and solutions found given that state are deemed to belong to that round. Only basic strategies can be applied multiple times - advanced strategies have a knock on effect which means on success you must quit and go to the start, the next round. A puzzle is deemed more difficult if it requires more rounds than another. Another way to say this is that there are less opportunities to break through. To express this each score for each round is multipled by the round number starting with 0. The only strategy being used is naked singles which score 1 point.
In the 1st round it is possible to solve 14 cells: 14 * 0 = 0
In the 2nd round it is possible to solve 11 cells: 11 * 1 = 11
In the 3rd round it is possible to solve 18 cells: 18 * 2 = 36
In the 4th round it is possible to solve 6 cells: 6 * 3 = 18
The sum of this is 65.
To get a score of 2 you need to reduce 65 to 51. The rounding will make this happen.
I am loath to give decimals on the scores as the precision is not really warrented. I offer the grade score as a guide - I am more interested in being able to group puzzles into six large sets - grades - and many people will dispute some puzzles because there are so many ways to solve a Sudoku (but I like to think I'm taking the minimum path). Decimals would be 'drama digits'. But in the case of very low scores the precision may be useful - since none of the other heuristics and weightings (if which I will remain mystical about) need apply and the normalisation is not strictly necessary unless you go below 32 clues, which is a possible strategy.
There you go, you have a unwholesome advantage over anyone else now :)
Andrew Stuart
Saturday, September 5, 2009
Since our last correspondence, below, for which I thank you, I have struggled, but succeeded, in designing a Sudoku with a score of 51. Below you said "To get a score of 2 you need to reduce 65 to 51. The rounding will make this happen" The Sudoku is:-
....5...767.41.3.583...9...7....8....91.7..4225....9.6.1.34.56.....2..14.6.5.....
The 4 rounds are 14, 21, 12, and 2. With values of 0, 1, 2 and 3, this
gives 21+24+6 = 51. The calculation 49 * (51 / 1000) = 2.499, which rounds to 2.
(The current winner with a Grade of 3 scored 65, so the calculation was 49 * (65 / 1000) = 3.185, which rounds to 3).
However, when I click on the Grader button on your web site, it shows a grade of 3. Could you therefore put the Sudoku though your off-line program and see if you agree my calculations? If you would send me the output as you did before, I will be most grateful.
I think that you on-line grader may have a problem in the final rounding stage as I have produced another Sudoku with (33 clues), which has 4 rounds of 16, 20, 11, 1. With values of 0, 1, 2 and 3, this gives 20+22+3 = 45. The calculation 48 * (45 / 1000) = 2.16, which also rounds to 2, but your on-line Grader states 3.
Could you please have a look at this, as if you publish my Grade 2 solution, no one will believe it is Grade 2 if your on-line grader gives it a grade of 3!!
Best Regards,
David Filmer
Saturday, September 5, 2009
ATTACHMENTS: DAVID.TXT, DAVID2.TXT
Hi David
Its not rounding. Attached are two runs. David.txt is what the grader is currently doing. David2.txt is what you are doing. What you are expecting is the use of Naked Singles for every solution - which is correct in a logical way. Naked Singles being the only remaining number in all three units as opposed to Hidden Singles where it is the only remaining number in one or two units (and therefore covered by another number from the remaining unit(s)).
Naked Singles should be elemental - that is the first and simplest strategy. Looking back at my code which I now see I preceed Naked Singles with a strategy I inserted to simulate the very basic scanning a human does when "eye-balling" a sudoku for the first time. It is a sub-set of Naked Singles, that is, it will get some Naked Singles due to a certain configuration. This "Human Strategy" or "Eye-balling" takes each box in turn and scans the rows and columns intersecting the box to see if there is only one place to put N in that box.
I remember I inserted this after comments that I should be taking into concideration what humans actually do when confronted by a Sudoku, especially the order in which solutions are found. I believe it is the type of checking most players do at any stage of the puzzle. So the reasoning was that some Naked Singles are easier to find that others. If I need to demonstrate a solution I can also use this as a guide to the ORDER in which singles are picked off - as often a Naked Single can be show to be naked through several different intersections and consequences of other solutions.
Now, because I have two strategies they go into different rounds. The majority of the time "Human Strategy" (Stage:1) will not find a solution and the standard Naked Singles (Stage:2) are employed, but the scores for each are the same. Now you might think this distorts the grade by "bumping up" the round multiplier for what is a hair splitting adjudication on the simplest situations, but it doesn't because generally one or the other is used and the value of the score is the same - in the vast majority of puzzles. But it does impact extremely low value games which provke a mixture of both. An "eye-balled" puzzle ought to be easier than one cant use this method for detecting Naked Single but it is now being penalised by having two rounds rather than one.
So I'm going to have to think about this a bit. You can see where I'm coming from - back in the day when I was developing the grader I wanted to include the human experience of the puzzle in the assessment of the grade. A possible solution would be a round muliplier of less than 1.
Andrew Stuart
Saturday, September 5, 2009
ATTACHMENTS: Grade_2_Sudoku.jpg
I have studied your reply, particularly as it applies to the Sudoku I sent you. I agree with you that naked singles is the simplest and the logical way of first examining a Sudoku. It's the method I have always adopted.
I think that the "eye balling" method is open to uncertainties and irregularities, which I have discovered in the example I sent you. I have followed the off-line outputs in detail, and whilst I agree that none are available in rounds 1 and 2 (david.txt and david2.txt are identical up to that point). I question the logic of Round 3 (human strategy) in david.txt.
I attach a jpg scan of the situation to the end of Round 2.
david.txt says D4, D8 and J5 can be filled in using "human strategy", and I have indicated this in the jpg by entering the "only possible numbers" in the appropriate cell, and putting a single box round them. All 3 solutions are the only missing number left in their boxes and clearly "eye balling" would see that.
BUT "eyeballing" would also see the other 5 solutions, all of which are the entered with a double square round them. In each case they are the only missing number in a row or column. Your current program did not recognise this, so round 3 should have 8 solutions not 3.
Andrew Stuart comments: "Eye-balling" takes each box in turn and scans the rows and columns intersecting the box to see if there is only one place to put N in that box. If 'eye balling' were as you describe it would be no different to singles per se
If you recalculate the score you get 14, 21, 8, and 6 which gives 21 +16 + 18 = 55
BUT also "Eyeballing" could have also seen that A3 must be 4 because all the other numbers are in row A or col 3
Similarly A7 must be 6 because all the other numbers are in row A or col 7
Similarly A8 must be 9 because all the other numbers are in row A or col 8
Similarly J7 must be 2 because all the other numbers are in row J or col 7
If you recalculate the score again you get 14, 21, 12, and 2 which gives 21 +24 + 6 = 51, which is the same as in david2.txt
The problem with incorporating "human strategies" is that your definition of what is a human strategy (and the way you program it) may differ from other people. This could lead to endless conflict and unnecessary argument. Much better in my opinion to use a logical, simple and unambiguous solution as in your david2.txt
I always use the convention of "Occam's Razor" if there is a choice between complexity and simplicity.
In your last paragraph you say "So I'm going to have to think about this a bit" and I hope that you will take my contribution above into account. I don't like your idea of "A possible solution would be a round multiplier of less than 1". This would always lead to arguments as to what the multiplier should be. You could make the answers come out in an arbitrary way to favour our disfavour, any competitor, and you could be accused of bias. A straightforward method which cannot be challenged and is easy to explain would be my preferred option.
David Filmer
Sunday, September 20, 2009
ATTACHMENTS: Human_method_of_solving_simple_Sudokus_4.pdf
Andrew, Here is the documentation of the Human method I always first adopt when solving Sudokus without a computer It has the advantage that the individual solutions to cells can be entered directly without having to put possible candidates in cells. I attach the method as a pdf file, which with diagrams, occupies only 2 pages of A4 and is written in such a way as to be a template for computer programming.
I use the latest simplest Sudoku I created to illustrate my method: .1.34.56.....2..14.675.........5...767.41.3.583...9........8....91.7..4225....9.6
At present your grader incorporates a human strategy, which only serves to slow down the solution as the comparison between "david" and "david2" has shown. I believe that an improved human strategy, (such as the one that I am suggesting) could improve the solution speed ( and lower the score and grade). I think therefore that you should evaluate alternatives to your existing "human strategy", and I offer mine as a candidate. It employs the simplest of strategies, namely that of Intersecting Rows and Columns, much as Michael Mepham and others have advocated. I hope that you will give the attached your consideration and if you have the time, I would be delighted if you could write code for a "david3" alternative grader. I have simulated (david3.txt) the first stages of a possible output for your consideration.
Round Number 1 2 3 4 5
Grader Version
david 14 22 3 9 1 Score = 59
david 2 14 22 12 1 Score = 49
david 3 (New human) 49 Score = 0
Best regards,
David Filmer
Thursday, October 1st, 2009
Andrew, I have refined my "human strategy", which is now more effective as well as easier to understand and to program. Your current human strategy only fills the last cell in boxes where 8 cells already filled. This counts as a step and so usually increments the score. If you want to resolve this (and you may not!) there are 2 options:
1) Delete the existing human strategy as you did in the david2 version of your Grader
2) Update the human strategy to make it better reflect what humans do.
Advantages of the first are: -
a) No further programming
b) Would always give easier Sudokus a lower score
c) Would encourage Sudoku designers on your website by showing them lower more accurate grades.
Advantages of the second are: -
a) Uses the simplest strategy that even beginners will understand
b) Incorporates the principle "to simulate the very basic scanning a human does when "eye-balling" a Sudoku for the first time.� to which you referred.
I would prefer the second, but it would mean more work in programming for you or a colleague. To assist this, if this is the option you prefer, I attach a simple example, Brain Train 2.jpg as follows: - .1.34.56.....2..14.675.........5...76..41.3.583...9...7....8....91.7..4225....9.6
I explain how to solve this (by using ONLY the simplest strategy of intersecting rows and columns) in the attached .doc file. It tackles subsets of 27 cells one at a time.
I have simulated a Grader printout, which shows how the attached example is solved fully by tackling just 3 subsets in turn, namely columns 1,2,3: 4,5,6: and 7,8,9.
I have made some effort putting this together so I hope that you can find time to have a look at these ideas. Best Regards, David Filmer
Saturday, October 10, 2009
Andrew,
Here are my contributions to your "competition" for easiest Sudoku with 32 clues. I produced around 40 puzzles which scored 2 on your grader, and these are two of the easiest ones:
4..2..95.83..6.7...6.1....27.5..8.2....432........91686.....39124.5...8..1..7....
....845.72...6..9..71..23..7..253.6.928............41..4...58.365.9......3.7.1..9
They can be solved in two rounds using all independent singles, or in three rounds using only naked singles. The number of solved are 36/49-18/39/49 and 35/49-20/38/49 after each round. It is probably possible to get score 2 with less than 32 clues or score 1 with 32, but I don't have the time and tools to investigate this further, because I don't know exactly how the grader computes the score.
May I suggest, as a different rule instead of the arbitrary 32 clues, that the puzzle should be minimal (no clue can be removed without multiple solutions)? It's kind of cheating to start with a valid Sudoku and add digits to make it easier.
Method: Starting with a list of puzzles with 17 clues, I filled 15 random cells, and then counted the number of naked singles available. I suppose your grader views naked singles as easier than hidden (which I don't agree with as a general rule). From a total of more than 200 million generated, I tested around 5000 on the grader, most of them scoring 4-8. This is a tedious task, even if I don't do it manually, because using the grader over the web takes a few seconds for each puzzle (I apologize for the server work load). In all, it took me two days.
Note: It is not always true that a "partially completed puzzle will have an easier grade", at least not a lower or equal score. This example has two additional clues and scores 4, which shows how hard it is to implement a good grading algorithm.
4..2..95.83..6.7...6.1....27.5..8.2....43257......91686.....39124.5...8..1..7....
Mats Anderbok
Comments
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted - no need to use <p> or <br> tags.