Suppose an initial grid has some symmetry property. Then if you validly place a new digit using any type of logic, a symmetrical analogue of that logic will place another digit(s) in the symmetrical position(s) in the grid (or the digit you placed at first was at a fixed point of the symmetry in which case we're still fine). After placing those digits, we still have a grid with the same symmetry property we started with. Then by induction, the puzzle keeps that symmetry property throughout the solving process. Therefore the final grid has the symmetry property, so we may assume the whole puzzle has that symmetry property from the outset. That's my take on how to think about this theorem.
Good to find this channel. I was alerted by a fan. I'm fascinated to learn about Gurth's theorem only now and I will attempt to add this as a strategy option to my solver as soon as possible. I will also add Shining Mirror to the list of examples since it's an excellent puzzle. My first thoughts are that there are quite a number of symmetries to check but the computer is good at that. The solver already has the rotation buttons. I might add a permutation button as well. I will interested to find what proportion of randomly created puzzle Gurth's theorem can apply to. Uniqueness is already a requirement of many strategies and I believe it's a natural property of a Sudoku puzzle anyway, non-unique puzzles are different entities. Will post further when done. Thanks for making this video,
Pleasure is very much mine. I'm happy to announce that the solver is now Gurth 'aware'. It will trigger the strategy if the puzzle is detected to be compliant. I've written an article on the topic here www.sudokuwiki.org/Gurths_Theorem My suspicion is that the pattern is very unlikely to appear in an every day puzzle. The number of symmetries that produce results is quite limited and because the candidate spread is also symmetric - this leads to no new eliminations except on the axis of reflection (9 cells) or rotation (1 cell, E5). I would appreciate more examples, perhaps I've underestimated the scope.
@@syndicatedpuzzles no i don't think you have. everything else you can do with it you would have been able to do without it. Diagonal reflection and 180 rotational symmetry seem to be the only ones that work. For rotational symmetry, you can remove all numbers that don't map to themselves from the central square, which usually will leave one number, and for diagonal reflective symmetry, you can remove all numbers that don't map to themselves from the diagonal. that's all you can do with it, though solving goes quicker after because you can fill in corresponding cells, and you can eliminate from the corresponding cells every time you do any other elimination, which can end up quickly revealing naked singles you would have taken more time to get to.
Well as a mathematician I can say that it definitely is easier to explain the proof. It has to do with relabelling problem. In sudoku you can always relabel digits. In effect you can relabel them with any permutation permuting digits from 1-9. Therefore, if there would exist a nonsymmetric solution, relabeling would yield another solution.
Not exactly. I think it is not about arbitrary permutations of digits from 1~9. (How can you permutate your own solution to get another solution when your givens are fixed?) Instead,you need to apply the symmetric rule which the given numbers used to get a contradiction,just like what Simon did. (Maybe I misunderstood what you said.Then I will be grateful if you explain your idea more clearly!)
@@郭泰慶-z3m One example of relabelling could be to swap all the 3s and 7s. Another could be to add 1 to every digit, wrapping around so that the 9s become 1s.
Relabeling symmetrical solutions is a difficult problem if you want to make exact computations. For example on wikipedia the number of essentially unique solutions cannot be derived from the number of sudoku grids in any simple way. Probably if knowing the types of symmetry on either side of this, then maybe it would be computable. But how to compute those numbers in the first place? I think a research paper might answer that
@@郭泰慶-z3m It is about permutation. The key point to notice is that the rules or constraints of sudoku are still valid under reflection and relabeling(permutation). So to construct another solution from the asymmetrical solution, one can argue as follows: Assume that we obtained an asymmetrical solution, then there exists at least one pair of corresponding reflection cells which do not follow the symmetry of given clues, let's call it X-Y. Next, we apply the relabeling that preserves the symmetry of given clues (In our case, 35, 67, 19, 22, 44, 88). Then from the asymmetric assumption, in this new configuration, X-Y pair is mapped to say W-Z and at least one of W or Z equals to neither X nor Y. Next, we reflect this sudoku configuration. From this we reach to a configuration where the given clues are the same as before due to the symmetry they satisfy, but the two cell locations where X-Y pair used to occupy are now replaced by W-Z pair, and we know one of W, Z can not be X and Y. As what we did was only relabeling and reflecting, the the constrain of sudoku is still valid, so this new configuration is a valid solution which is different from the original.
The way I understand Gurth's Symmetrical Placement is as follows: If the puzzle has a unique solution, and the givens are completely symmetrical in one sense, then applying one technique (let's call this technique T) on one part of the grid which is reflected or rotated by the symmetry, then the same exact technique T is valid for the reflected or rotated area of the grid for the corresponding digit which the digits of the technique T change to. So say you have the "reflection pairs" (where a reflection pair is a pair of digits x and y such that x always becomes y and y always becomes x during the reflection or rotation) (1, 7), (3, 9), (2, 4), (5, 6), with the 8 not reflecting onto anything but itself, and there's a technique T that you can use to deduce something about the interaction between 1's and 3's somewhere in the part of the grid that rotates or reflects. Then that same technique T is valid for making the identical deduction, just a mirrored or reflected version of it, for the digits 7 and 9, where the deduction for the 1 carries over to the 7 and vice-versa for the 3's and the 9's. Likewise, the reason the digit which reflects or rotates to itself has special status is because if this 8 in our example was to be placed __anywhere where it would rotate to yield an illegal position__, then the puzzle __cannot have a solution because otherwise the other eight digits would not be symmetrically placed from the given digits__. Likewise, with the mirror example you showed __there must be three digits, in this instance 2, 4, and 8, that always map to themselves__, or else you could run into the issue of having one technique T1 being valid for one digit, say the 6, in one part of the grid that reflects, but not have it be valid for the 7 in the reflection where you need to use technique T2. But that breaks the symmetry of the givens, for in the __given position without any solved digits in the grid, for every possible deduction about a number in a reflection pair there must exist a symmetrical deduction for the corresponding digit in its reflection pair__. Now, that's all fine and dandy. But why would any of this reasoning hold any later in the puzzle? Well, because when you write __any digit__ then you must be able to write down the other symmetrical digit (or no symmetrical digit, if it "maps to itself"). You can then imagine setting a new puzzle, this time with every digit you've managed to solve as additional givens and then solve that new puzzle. The same reasoning as in the above paragraph still holds true. You can keep doing this for as long as you desire until you have a solved grid. I hope this was interesting, and I hope RUclips doesn't mess up my comment too much!
This is one of the few times that I understood a proof by contradiction during the first time hearing its explanations, thank you for the helpful visualisations!
One consequence of Girth's: If a sudoku has diagonal symmetry (like this one), but only one of the nine digits maps onto itself (like the 9 in the rotational example given), there can be no unique solution. There must be at least three, so that the boxes along the diagonal can have three different digits to go along it,
Dedicated CTC subscriber and "classic" (preferred) solver .. Shining Mirror was easily the most satisfying solve of any that you have posted .. as much in appreciation and in awe of the elegance and cleverness of the puzzle .. as it was the relief of achieving the "looks good!" at the end! Bravo!
What a puzzle!! I'm Obviously late but I tried the puzzle before Simon explained what it even was and stuck for a while. After giving up and resuming the video and now understanding the symmetry, I continued filling the entire grid with marks, and ending with 1:09:38. (Still haven't seen him do it yet as I just finished it myself)
If I tell my partner I've spent the morning applying Gurth's theorem to Mauricio's "Shining Mirror" she's going to tell me to stop playing World of Warcraft, hand me some Windowleen and throw me outside.
This took me an hour. I first couldn't get any digits in by snyder notation, so I expanded and eventually ended up writing in every possible number for every possible square. Still couldn't do it, so I watched the beginning of this video, and even after understanding the theorem, it took me a good 40 minutes. What a mind-boggling puzzle, but what satisfaction when I finished!
I went from "what is Simon on about today?" to "I think this might be black magic from beyond the cosmos" to "hmm pretty simple, makes a lot of sense" so good on ya lad for a right proper breakdown.
The other day I gave up once notation failed to give me anything, now with this symmetry shennanigans I think it was a pretty good puzzle. Thanks for showing us something interesting once again.
Another way to explain it is by contradiction: If a puzzle starts as symmetric, to end with an unsymmetric solution would require something to break that symmetry, but by definition there's nothing in a symmetric puzzle that can break it's own symmetry and any numbers that can be added can always be added in the symmetric position to keep it's symmetry. Therefore the solution must always continue being symmetric no matter how it's solved.
@@郭泰慶-z3m it could probably be simplified to say there is nothing in the rules that allows symmetry breaking, so if a puzzle start out symmetric it must end up symmetric too
Wow I can't believe I managed to get through this. I barely recognised the symmetry and remembered your puzzle from last week where the 5 was forced into the middle, so I figured I needed a non-symmetrical number to go into the middle. The only one that fit was the 4, which meant that later on I could rule out the 4 from two corner boxes in the same box, and after that it all unravelled. Finally watching all your sudoku tips videos is starting to make a difference in my sudoku solving!
I thought about Gurth when I tried to solve this one the other day, looked for rotational symmetry, didn't see any, and figured I was barking up the wrong tree. RIP
Wow. I had gotten basically nowhere. Even after quickly grasping the symmetrical idea, I only got two digits. Only after revealing the (logical) clue that only 2s, 4s, and 8s could go on the diagonal was I able to get off and running. I would never, ever had gotten this one without this video. Thank you.
2:02 - Explanation of Gurth's theorem... For a puzzle to be symmetrical, a few conditions must be met. A) The puzzle MUST be symmetrical around a diagonal. This should make sense given a bit of thought. IF you were to attempt to make a puzzle vertically symmetrical around column 5 or horizontally around row 5, then that column/row would have to include all digits 1 through 9. If all digits are included on the line of symmetry then it is impossible to substitute one digit for another and have symmetry. Using a diagonal makes it so that you can use the minimum number of self-reflecting numbers without interfering with each other. B) The puzzle MUST have at least 3 digits that map onto themselves (possibly exactly 3, but I have not worked out the rest of the reasoning just yet). Why? Because those are the 3 numbers that will be needed to complete the diagonal line of symmetry. Exactly 3 numbers on the diagonal will share a 3x3 box so they must be unique from each other. Now consider a grid with a diagonal - as in this video - made up of 2s, 4s, and 8s... If you fold the puzzle across the diagonal, then the top right half of the diagonal squares map onto the bottom left half of themselves... so the numbers in that diagonal must map to each other. That is why those 3 numbers must map to each other. AHHA - yes, there must be EXACTLY 3 digits that map to each other. It works because they are part of the diagonal and must fill in any spaces left empty by the 3 paired numbers. In this example the paired numbers are 1 with 9, 3 with 5, and 6 with 7. If they tried to map with themselves, then the 3x3 boxes along the diagonal line of symmetry would not work. You must have all 3 pairs represented in each of those boxes on the diagonal line of symmetry. So that answers the unknown from B above. 3 and only 3 digits must map onto each other, and the remaining 6 must be in 3 pairs. Given enough starting digits (my math is not strong enough to know what this minimum must be OR how many - if any - of those must be part of the diagonal line of symmetry), there will be only one solution. Consider for a moment taking any valid, one solution sudoku grid and switching the 1s for 9s... by definition the puzzle would still work. The 1s did not interfere with each other in the original, so the 9s will not interfere with each other when they are put in their place and vice versa. Now consider a Gurthian grid that is symmetrical around a diagonal line of symmetry. If the 1s on the top right half did not interfere with each other, then the 9s on the bottom left half will not interfere with each other... and if the 1s on the bottom left half don't interfere with each other, then the 9s on the top right half also will not interfere with each other. Reflecting across the diagonal line of symmetry effectively switches the 1s for the 9s as with the non-symmetrical sudoku grid in the example above, but it does it across the line of symmetry rather than with a separate grid. So the only way to solve a grid with symmetrical givens wherein 3 numbers map to themselves along a diagonal line of symmetry and 3 pairs of numbers map to each other, is for the solution to be symmetrical. NOTE: The reason that the other puzzle tested does not work is because it does not meet conditions A and B above. It only had one digit that maps to itself. That makes it impossible for there to be only one solution. If enough givens were included to limit to one solution, then those givens would no longer be symmetrical. It is not possible to have the 3x3 boxes along the diagonal line of symmetry work unless there are EXACTLY 3 digits which map to themselves. If there are fewer, then those digits along the line of symmetry violate the rule of mapping to each other - the top right half of the box would have to map to the OTHER number in the bottom left half of the same box - that makes no sense. If there are MORE than the 3 digits which map to each other, then the digits NOT along the line of symmetry would violate the rule of having the same number in the same 3x3 box more than once.
I was very happy to be able to solve the puzzle without help in about 27 minutes, though I had watched a previous video of yours that mentioned Gurth's symmetry law. I didn't fully understand all its applications and definitely would not have come up with something like the proof by contradiction you cover in this video, but I did have a rather simple way to intuit what was going on. Basically the idea is logical symmetry. When the givens are symmetrical, whatever logic you use to make a deduction on one side of the grid, the same can be made on the other with the other digits. Eventually as whatever logic you use makes its way around the puzzle, it will converge in the middle with a symmetric solution. It's not a proof, but it was a good way for me to wrap my head around the idea of symmetry.
I solved this in 22 minutes... i realized the mirroring after 5 minutes trying to figure out what to do next... now I am going to actually look at the video if I could do it in a better way.
Theorem: Suppose there is a substitution transformation and a symmetry transformation that both preserve the rules of sudoku. Then suppose there is a puzzle where the givens remain the same after these transformations are applied in sequence. Then, if there is one solution, the transformations must also transform that solution to itself. Proof: Assume there is a solution that does not transform to itself. Transform the solution. It must still be a solution to the puzzle as it still respects the sudoku rules. Also, the givens do transform to themselves, so the transform of the solution gives another solution to the initial puzzle. But then there are two solutions, which contradicts the condition that there is only one solution. Therefore by contradiction, there is no solution that does not transform to itself and, the solution must transform to itself.
The notion of symmetry is that the givens are in symmetrical positions in regards to some kind of positional symmetry, which would be rotation by 90 degrees in any direction, 180 degrees, or mirroring horizontally, vertically or along any of the diagonals OR ANY COMBINATION. And then if for all givens of digit A got swapped into a position where there was previously a B, and all B's got swapped into positions where there was previously an A, then the whole condition is satisfied. Note that A and B are allowed to be the same. If all the givens are symmetrical, then when you have enough information to make a deduction, you will by symmetry also have the information required to make the symmetrical deduction. The only new information given to you by Gurth's theorem is that if the symmetry is mirroring along a line, then since there's a unique solution, the 3 numbers that map onto themselves, and there can only be 3 such numbers, have to be located on the line of symmetry.
Reminds me of this brain teaser I once made, where you know the solution only because you know there is only 1 solution :-) - Person X wants to guess the number Person Y picked, between 8 and 100. - X asks to Y: Is your number >50? B answers, but lies. We doesn't know the answer, and X doesn't know that Y lies. - X asks to Y: Is your number a multiple of 4? Y answers, but we don't know if Y lies or not. - X asks to Y: Is your number a square number (e.g. 1, 4, 9,...)? Y answers, but we don't know if Y lies or not. - X asks to Y: Is 3 the first digit of your number? Y answers, but we don't know if Y lies or not. - X says: Now I know your number!! X shared his guess with Y, but Y says that X guessed the wrong number... With all this, YOU have enough information to know exactly the number Y picked!! ----------------------------------- SPOILER / SOLUTION ----------------------------------- - Q1: a=50 - Q2: a=multiple of 4 ; b=no multiple of 4 - Q3: a=square number ; b=no square number - Q4: a=first digit is a 3 ; b=first digit is not a 3 - For each number between 8 and 100, write out the possible way to get to that number. E.g. for the number 10: Q1=a (=50).
That's not the same... In a sudoku, the uniqueness of the solution does not depend on knowing it's unique. That only influences the technique we use. In your problem, it's not sufficiently defined, and telling us that there is a unique solution doesn't change that. There's nothing stopping Y from picking any number that's >50 as Y has the freedom to lie or tell the truth when answering. All we know is that Y answered no for Q1 and yes for Q2 and Q3, which left X with the options 16 or 36, in which Q4 rules out for X, but we don't know which, and we don't know which of those answer are true. TED X has presented a similar riddle, but there we know whether each answer is true or false, which allows us to deduce the number Y had in mind based on the established properties of the number from the answers. The given answers to the questions are deduced from a path that would narrow it down to one solution exactly by the time X guessed it.
Restatement of Gurth's: Within a valid Sudoku, if the givens have a symmetry, their complement must also have the same symmetry; if it did not, then by reflecting the complement over the axis of symmetry that the givens have would create a second solution, which is impossible. It's probably not implemented in any solver anywhere, because it assumes uniqueness rather than proving uniqueness.
At the same time the solver, when using pure brute force to count the number of solutions, came up with exactly 1. Probably used uniqueness along the way. That was the one small part of the video that did not make sense.
@@57thorns Brute force doesn't rely on uniqueness, it proves or disproves uniqueness. Since there are 6,670,903,752,021,072,936,960 valid Sudoku grids, it isn't quite feasible to just compare all of them to the givens, but it is feasible to take the givens, use the first-order Sudoku rules to enumerate the values that haven't been ruled out yet, and then try a proof by contradiction on one of the cells with the fewest possible remaining values, and recurse.
@@danpowell806 Normally when using uniqueness this is to avoid bifurcating into something that will lead to a contradiction. What I did not pick up on is that the sudoku grid between 4:22 and 11:30 is under specified. It has multiple solutions. You never need to assume symmetry or uniqueness to solve a correct sudoku if you are prepared to bifurcate and start exploring different possible partial solutions, it is just a fast way to avoid false leads.
A better restatement, that doesn't need to assume validity: For any transformation of the grid that preserves a valid Sudoku, is it's own inverse functon, and can produce its input as its output, if applying that transformation to the givens produces the input, there exists a solution where applying that transformation to the completed grid produces the input. I can't figure a formal proof at the moment, but I think generalizing to 'any transformation that preserves validity and is its own inverse' has interesting effects. Even more so if it also holds for a transformation which takes three iterations to reverse (e.g. take the top three rows, roll them around by one, and adjust each number to +3, mod 9)
How can we check there is a unique solution though without just assuming it? It seems the diagonal still must be bifurcated without using 2 4 and 8 to prove this? Or a fancy logic solve with multi chains and nets?
Lol! God it’s been a while since I saw that website. I wrote the Sudoku Wiki iOS app about 8 years ago. It was one of the first iOS apps I ever wrote and got me my first iOS development job. It is still one of the most complex apps I’ve ever written. Mainly down to all the graphics that are drawn over the grid when displaying each step solution.
Understood. However, I would add one corollary to make Girth's Hypothesis valid in every situation: Corollary: A symmetrical puzzle must be further defined to have GIVEN ALL 9 digits along with their corresponding mapping counterparts, at the start. Conversely: If any digits are missing in the original puzzle, therefore the puzzle CANNOT be a guaranteed to have a unique solution. e.g. if the above puzzle was missing all 3's and all 7's, then there would not be a guarantee that this was a symmetrical puzzle. Therefore, a symmetrical puzzle must first and foremost have all the 9 digits represented.
I tried it without you pointing towards symmetry and gave up. You pointed to symmetry, and I could solve it. Knew something interesting was going on there with some sort of symmetry when I first tried it but hadn't had any idea how to approach it until I saw that red line.
I recognized there was symmetry, but I wasn't sure of all the digits and I wasn't sure of the diagonal, but now I think I must have been an idiot not to see it. I did a couple of trial and error and hit upon a 23/25 pair on the diagonal pulled the 2 and I was able to solve the puzzle with another pair that had matching 35. But in both instances, I was guessing and happened to be lucky which was really very unsatisfying. You promised a logical solution and clearly delivered. I look forward to more symmetry puzzles, as now I have a better feel as to what to look for.
The best public solver is Sudoku Snake. This tool is on higher level than anything else including any human ;). It doesn't include this type of symmetry though so it rates this puzzle as 12.2 which would by far the hardest one ever (of course that's not the case as Simon nicely demonstrated). The reason is that it solves it by finding 2 dynamic unit nested forcing chains. Something totally impossible for any human to ever spot.
15:49 I didn't realize I paused the video accidentally, I've been watching this frame for like 30 seconds, wondering why Simon is still and hasn't pencil-marked anything
Thanks so much for this explanation. I'm a linguistics kind of person, and a chess player with no affinity for math, but hugely interested in logical reasoning; in fact, I solve sudokus recreationally, so puzzles of this particular difficulty hold no interest to me.
It is really very simple. If there existed a non-symmetrical solution, you'd have to break symmetry at some point. Well what on earth could tell you where and how to do that‽ You need asymmetry to seed further asymmetry
@@CrackingTheCryptic Selfishly, I have to thank you for being of this category! Because people who "just get it" seldom can deliver as helpful and valuable explanations of certain (at least for me) tricky things, as they don't fully see what might need explaining in the first place, as it is "obvious".
I figured the 2,4,8 down the line. Then somehow couldn't get my head wrapped any further around the problem. Even the second try with this I got stuck until he pointed out the single 8 in row 1. After that it broke down for me.
Conveniently we need *not* presume uniqueness to apply Gurth's Theorem, as there is a generalization which holds true via essentially the same proof, and can be applied to any symmetrical sudoku no matter how many solutions it has. To wit:
ack, whoops. ANYWAY. TO WIT: For any Sudoku with symmetrical (defined as per Gurth's) givens, the set of cells whose value is the same among all solutions must be symmetrical. Obviously for a puzzle with a unique solution, that is equivalent to Gurth's, and we can apply the exact same proof by contradiction logic (take a solution, transform it, any cells that weren't symmetrical in that solution must change, therefore those cells can't have the same value among all solutions.) to show that this generalization holds. That means that if, when solving a puzzle with symmetrical givens, you prove any cell must have a specific digit (that is, you can place it without having presumed uniqueness or applying bifurcation), you can apply this principle to conclude that the symmetrical mirror of that cell must have the symmetrical mirror of that digit in all solutions to the puzzle, and thus place that digit too. And if you do this and otherwise restrict yourself to logic that doesn't presume uniqueness, then any solution you can reach will be correct - and if the puzzle so happens to be unique, you will have the correct, unique, solution.
Hrmn, This feels less like a technique and more a hidden restriction on the solution. Once you know the restriction (the rotation or reflection) the single solution becomes clear.
Made a sudoku solver not long ago, and I've poured some hours into watching this channel because of it. I have to say that the interesting solves I've seen are ones that use the property that there is a single solution because it's one thing to work out the logical constraints from the rules, it's another bit to pick up on logical constraints given we know there's only one completed state. When I originally made the solver, I don't think I was aware that a real sudoku by definition had only one solution. What I've been curious about for ages though is what the minimal set of algorithms / strategies that would guarantee a solve (assuming a proper sudoku). Because at least from the few techniques I'd implemented, it seems some algorithms subsume others in solving the puzzle. I'm trying to work out in my head what's going on here, because I'd love to try to implement this.
The guy that runs the solver often shown in his videos set out to do exactly what you have stated. You see how many steps he has progressively added to it in his findings. As for how to model this, have the computer first check each 45 degree split for -if {_&_!=0} -then consider symmetry. I'm not sure a nice way to do the full rotation check, but it would fall similar. Then do simple coloring, start by highlighting given (1s) and proceed to highlight (2s-9s) until a pattern becomes valid for (1s), if none, set color then change to next color. Continue through until all numbers establish a pair, not pair. Set eliminations and proceed.
Amazing. Well done. But I must say, as soon as you recognize the symmetry, and that the main diagonal must be solved for 2-4-8, if you are looking at ALL the remaining Candidates, it becomes a "BABY" Puzzle, and can be easily solved after that, in less than 2 minutes. Nonetheless, your application of Gurth's Theorem was astonishing. :-)) Hats off.
Take a look at Sudoku Susser written by Robert Woodhead (google it) It found the solution to this immediatley and it is a great way to learn the techniques to solving these puzzles. alaoing with tutorials like this of course.
Does the computer solver not actually brute force the puzzle? Any sudoku with a unique solution can be solved by brute force, and computers are really good at doing it, compared to humans. I would have thought the computer solvers would do so, at least as a last resort.
Only Hoduko resorts to brute force, neither Andrew's nor Duncan's sudoku solvers resort to brute forcing. Besides, not even Bowman's Bingo can save a solve here because one application of Bowman's Bingo is not enough to yield a contradiction, you need multiple and nestled Bowman's Bingos and at that point the computer gives up, and understandably so because the complexity of that calculation is staggeringly massive.
@@RandomBurfness I see, it's not that they can't do it it would just take an impractical amount of time. I don't think I instinctively comprehend the sheer number of possible ways to make a fully filled out sudoku board, even though now that I think about it it's probably astronomical.
@@flodorf64 even I could tell you the number of solutions if you have me a pencil and some time. The difficulty lies in systematically actually going through each and every possibility to see if it works as the unique solution.
I quit here: i.postimg.cc/bwC8hN5j/Sudoku.png I ran through each number, only got a handful of Snider notations for my effort, and can't use any techniques that I've learned to make any further progression. I'll watch the video, but I have no true interest in this puzzle.
This is not really a true Sudoku puzzle, it is an exercise in futility. Are we really using "logic" to solve this puzzle, or are we just playing 'pattern politics' with this so called "Gurth's Theory". That is not Sodoku. Sorry, not a fan of this puzzle. I like your explanation of the theory, but This is not a true puzzle. Sorry.
If you can prove that there is a puzzle out there that starts symetrical and doesn't end symetrical then I'll agree with you. However saying it isn't a sudoku just cause you don't like the logic is extremely selfcentered and narrowminded way of thinking. "Oh I don't like this logic, therefor it is not a Sudoku". I'm not a fan of killer sudoku's but they are still sudokus. The fact is, is that with the Gurth's Theorum, this puzzle becomes a lot of fun to solve. having to use both standard sudoku methods and the extra information gathered from the symetry to slowly work towards a solution. You're allowed to dislike a puzzle, but don't go disregarding something that is true, just because you don't like it.
@@draconicdusk5911 First off, never said I didn't like the puzzle or it's logic. I did solve it. Just like Simon say about the 'world's hardest sudoku' "this is not a true puzzle." A puzzle he didn't even try to solve because it has a real logic to it, and neither does this. A logical puzzle is something most people can solve, a pattern reconnection puzzle is not really something everyone can do. Just look at the comments for this puzzle a couple of day ago, almost everyone, who said they solved the puzzle, said they use all kinds of X wings, X wings of 4's. Simon solves the puzzle, no x wings. I solved this puzzle with brute Force, which is a fancy way of saying I guessed. We can agree to disagree, but this is NOT a true puzzle.
Suppose an initial grid has some symmetry property. Then if you validly place a new digit using any type of logic, a symmetrical analogue of that logic will place another digit(s) in the symmetrical position(s) in the grid (or the digit you placed at first was at a fixed point of the symmetry in which case we're still fine). After placing those digits, we still have a grid with the same symmetry property we started with. Then by induction, the puzzle keeps that symmetry property throughout the solving process. Therefore the final grid has the symmetry property, so we may assume the whole puzzle has that symmetry property from the outset. That's my take on how to think about this theorem.
Good to find this channel. I was alerted by a fan. I'm fascinated to learn about Gurth's theorem only now and I will attempt to add this as a strategy option to my solver as soon as possible. I will also add Shining Mirror to the list of examples since it's an excellent puzzle. My first thoughts are that there are quite a number of symmetries to check but the computer is good at that. The solver already has the rotation buttons. I might add a permutation button as well. I will interested to find what proportion of randomly created puzzle Gurth's theorem can apply to. Uniqueness is already a requirement of many strategies and I believe it's a natural property of a Sudoku puzzle anyway, non-unique puzzles are different entities. Will post further when done. Thanks for making this video,
We're honoured to have you here Andrew!
Pleasure is very much mine. I'm happy to announce that the solver is now Gurth 'aware'. It will trigger the strategy if the puzzle is detected to be compliant. I've written an article on the topic here www.sudokuwiki.org/Gurths_Theorem
My suspicion is that the pattern is very unlikely to appear in an every day puzzle. The number of symmetries that produce results is quite limited and because the candidate spread is also symmetric - this leads to no new eliminations except on the axis of reflection (9 cells) or rotation (1 cell, E5). I would appreciate more examples, perhaps I've underestimated the scope.
There's also the puzzle that uses 4 symmetrical X-wings to solve, on this channel as "the best puzzle ever?"
@@syndicatedpuzzles no i don't think you have. everything else you can do with it you would have been able to do without it. Diagonal reflection and 180 rotational symmetry seem to be the only ones that work. For rotational symmetry, you can remove all numbers that don't map to themselves from the central square, which usually will leave one number, and for diagonal reflective symmetry, you can remove all numbers that don't map to themselves from the diagonal. that's all you can do with it, though solving goes quicker after because you can fill in corresponding cells, and you can eliminate from the corresponding cells every time you do any other elimination, which can end up quickly revealing naked singles you would have taken more time to get to.
Girth's theorem for mirrors and rotations will be programmed into my solver now. Great stuff really interesting!
Well as a mathematician I can say that it definitely is easier to explain the proof. It has to do with relabelling problem. In sudoku you can always relabel digits. In effect you can relabel them with any permutation permuting digits from 1-9. Therefore, if there would exist a nonsymmetric solution, relabeling would yield another solution.
Not exactly.
I think it is not about arbitrary permutations of digits from 1~9.
(How can you permutate your own solution to get another solution when your givens are fixed?)
Instead,you need to apply the symmetric rule which the given numbers used to get a contradiction,just like what Simon did.
(Maybe I misunderstood what you said.Then I will be grateful if you explain your idea more clearly!)
@@郭泰慶-z3m
One example of relabelling could be to swap all the 3s and 7s. Another could be to add 1 to every digit, wrapping around so that the 9s become 1s.
Relabeling symmetrical solutions is a difficult problem if you want to make exact computations. For example on wikipedia the number of essentially unique solutions cannot be derived from the number of sudoku grids in any simple way. Probably if knowing the types of symmetry on either side of this, then maybe it would be computable. But how to compute those numbers in the first place? I think a research paper might answer that
@@郭泰慶-z3m It is about permutation. The key point to notice is that the rules or constraints of sudoku are still valid under reflection and relabeling(permutation). So to construct another solution from the asymmetrical solution, one can argue as follows: Assume that we obtained an asymmetrical solution, then there exists at least one pair of corresponding reflection cells which do not follow the symmetry of given clues, let's call it X-Y. Next, we apply the relabeling that preserves the symmetry of given clues (In our case, 35, 67, 19, 22, 44, 88). Then from the asymmetric assumption, in this new configuration, X-Y pair is mapped to say W-Z and at least one of W or Z equals to neither X nor Y. Next, we reflect this sudoku configuration. From this we reach to a configuration where the given clues are the same as before due to the symmetry they satisfy, but the two cell locations where X-Y pair used to occupy are now replaced by W-Z pair, and we know one of W, Z can not be X and Y. As what we did was only relabeling and reflecting, the the constrain of sudoku is still valid, so this new configuration is a valid solution which is different from the original.
The way I understand Gurth's Symmetrical Placement is as follows:
If the puzzle has a unique solution, and the givens are completely symmetrical in one sense, then applying one technique (let's call this technique T) on one part of the grid which is reflected or rotated by the symmetry, then the same exact technique T is valid for the reflected or rotated area of the grid for the corresponding digit which the digits of the technique T change to. So say you have the "reflection pairs" (where a reflection pair is a pair of digits x and y such that x always becomes y and y always becomes x during the reflection or rotation) (1, 7), (3, 9), (2, 4), (5, 6), with the 8 not reflecting onto anything but itself, and there's a technique T that you can use to deduce something about the interaction between 1's and 3's somewhere in the part of the grid that rotates or reflects. Then that same technique T is valid for making the identical deduction, just a mirrored or reflected version of it, for the digits 7 and 9, where the deduction for the 1 carries over to the 7 and vice-versa for the 3's and the 9's. Likewise, the reason the digit which reflects or rotates to itself has special status is because if this 8 in our example was to be placed __anywhere where it would rotate to yield an illegal position__, then the puzzle __cannot have a solution because otherwise the other eight digits would not be symmetrically placed from the given digits__. Likewise, with the mirror example you showed __there must be three digits, in this instance 2, 4, and 8, that always map to themselves__, or else you could run into the issue of having one technique T1 being valid for one digit, say the 6, in one part of the grid that reflects, but not have it be valid for the 7 in the reflection where you need to use technique T2. But that breaks the symmetry of the givens, for in the __given position without any solved digits in the grid, for every possible deduction about a number in a reflection pair there must exist a symmetrical deduction for the corresponding digit in its reflection pair__.
Now, that's all fine and dandy. But why would any of this reasoning hold any later in the puzzle? Well, because when you write __any digit__ then you must be able to write down the other symmetrical digit (or no symmetrical digit, if it "maps to itself"). You can then imagine setting a new puzzle, this time with every digit you've managed to solve as additional givens and then solve that new puzzle. The same reasoning as in the above paragraph still holds true. You can keep doing this for as long as you desire until you have a solved grid.
I hope this was interesting, and I hope RUclips doesn't mess up my comment too much!
Thank you for reminding me why i hated maths lol but great explanation
This is one of the few times that I understood a proof by contradiction during the first time hearing its explanations, thank you for the helpful visualisations!
One consequence of Girth's: If a sudoku has diagonal symmetry (like this one), but only one of the nine digits maps onto itself (like the 9 in the rotational example given), there can be no unique solution. There must be at least three, so that the boxes along the diagonal can have three different digits to go along it,
there must be EXACTLY 3 digits that map to themselves, with the other six filling the middle square.
More than 2 years since I got to know this channel, but yet first time hearing about this theorem, and all thanks to today's GAPP from Philip Newman 👌
I absolutely love that he couldn't resist finishing the puzzle 😄☺️
Dedicated CTC subscriber and "classic" (preferred) solver .. Shining Mirror was easily the most satisfying solve of any that you have posted .. as much in appreciation and in awe of the elegance and cleverness of the puzzle .. as it was the relief of achieving the "looks good!" at the end! Bravo!
Here for an explanation after Shye's puzzle, Antidote.
What a puzzle!! I'm Obviously late but I tried the puzzle before Simon explained what it even was and stuck for a while. After giving up and resuming the video and now understanding the symmetry, I continued filling the entire grid with marks, and ending with 1:09:38. (Still haven't seen him do it yet as I just finished it myself)
If I tell my partner I've spent the morning applying Gurth's theorem to Mauricio's "Shining Mirror" she's going to tell me to stop playing World of Warcraft, hand me some Windowleen and throw me outside.
This took me an hour. I first couldn't get any digits in by snyder notation, so I expanded and eventually ended up writing in every possible number for every possible square. Still couldn't do it, so I watched the beginning of this video, and even after understanding the theorem, it took me a good 40 minutes. What a mind-boggling puzzle, but what satisfaction when I finished!
I went from "what is Simon on about today?" to "I think this might be black magic from beyond the cosmos" to "hmm pretty simple, makes a lot of sense" so good on ya lad for a right proper breakdown.
The other day I gave up once notation failed to give me anything, now with this symmetry shennanigans I think it was a pretty good puzzle. Thanks for showing us something interesting once again.
Another way to explain it is by contradiction:
If a puzzle starts as symmetric, to end with an unsymmetric solution would require something to break that symmetry, but by definition there's nothing in a symmetric puzzle that can break it's own symmetry and any numbers that can be added can always be added in the symmetric position to keep it's symmetry.
Therefore the solution must always continue being symmetric no matter how it's solved.
You made a msitake called circular argument.
You already used the result in your proof ,then,of course it will be true LOL.
@@郭泰慶-z3m it could probably be simplified to say there is nothing in the rules that allows symmetry breaking, so if a puzzle start out symmetric it must end up symmetric too
Wow I can't believe I managed to get through this. I barely recognised the symmetry and remembered your puzzle from last week where the 5 was forced into the middle, so I figured I needed a non-symmetrical number to go into the middle. The only one that fit was the 4, which meant that later on I could rule out the 4 from two corner boxes in the same box, and after that it all unravelled. Finally watching all your sudoku tips videos is starting to make a difference in my sudoku solving!
Gurth's Symmetrical Placement.... just the very name scared crap outta me!!! And then he started EXPLAINING it! * thud *
I thought about Gurth when I tried to solve this one the other day, looked for rotational symmetry, didn't see any, and figured I was barking up the wrong tree. RIP
Wow. I had gotten basically nowhere. Even after quickly grasping the symmetrical idea, I only got two digits. Only after revealing the (logical) clue that only 2s, 4s, and 8s could go on the diagonal was I able to get off and running. I would never, ever had gotten this one without this video. Thank you.
2:02 - Explanation of Gurth's theorem...
For a puzzle to be symmetrical, a few conditions must be met.
A) The puzzle MUST be symmetrical around a diagonal. This should make sense given a bit of thought. IF you were to attempt to make a puzzle vertically symmetrical around column 5 or horizontally around row 5, then that column/row would have to include all digits 1 through 9. If all digits are included on the line of symmetry then it is impossible to substitute one digit for another and have symmetry. Using a diagonal makes it so that you can use the minimum number of self-reflecting numbers without interfering with each other.
B) The puzzle MUST have at least 3 digits that map onto themselves (possibly exactly 3, but I have not worked out the rest of the reasoning just yet). Why? Because those are the 3 numbers that will be needed to complete the diagonal line of symmetry. Exactly 3 numbers on the diagonal will share a 3x3 box so they must be unique from each other.
Now consider a grid with a diagonal - as in this video - made up of 2s, 4s, and 8s... If you fold the puzzle across the diagonal, then the top right half of the diagonal squares map onto the bottom left half of themselves... so the numbers in that diagonal must map to each other. That is why those 3 numbers must map to each other.
AHHA - yes, there must be EXACTLY 3 digits that map to each other. It works because they are part of the diagonal and must fill in any spaces left empty by the 3 paired numbers. In this example the paired numbers are 1 with 9, 3 with 5, and 6 with 7.
If they tried to map with themselves, then the 3x3 boxes along the diagonal line of symmetry would not work. You must have all 3 pairs represented in each of those boxes on the diagonal line of symmetry.
So that answers the unknown from B above. 3 and only 3 digits must map onto each other, and the remaining 6 must be in 3 pairs.
Given enough starting digits (my math is not strong enough to know what this minimum must be OR how many - if any - of those must be part of the diagonal line of symmetry), there will be only one solution.
Consider for a moment taking any valid, one solution sudoku grid and switching the 1s for 9s... by definition the puzzle would still work. The 1s did not interfere with each other in the original, so the 9s will not interfere with each other when they are put in their place and vice versa.
Now consider a Gurthian grid that is symmetrical around a diagonal line of symmetry. If the 1s on the top right half did not interfere with each other, then the 9s on the bottom left half will not interfere with each other... and if the 1s on the bottom left half don't interfere with each other, then the 9s on the top right half also will not interfere with each other.
Reflecting across the diagonal line of symmetry effectively switches the 1s for the 9s as with the non-symmetrical sudoku grid in the example above, but it does it across the line of symmetry rather than with a separate grid.
So the only way to solve a grid with symmetrical givens wherein 3 numbers map to themselves along a diagonal line of symmetry and 3 pairs of numbers map to each other, is for the solution to be symmetrical.
NOTE: The reason that the other puzzle tested does not work is because it does not meet conditions A and B above. It only had one digit that maps to itself. That makes it impossible for there to be only one solution.
If enough givens were included to limit to one solution, then those givens would no longer be symmetrical. It is not possible to have the 3x3 boxes along the diagonal line of symmetry work unless there are EXACTLY 3 digits which map to themselves.
If there are fewer, then those digits along the line of symmetry violate the rule of mapping to each other - the top right half of the box would have to map to the OTHER number in the bottom left half of the same box - that makes no sense.
If there are MORE than the 3 digits which map to each other, then the digits NOT along the line of symmetry would violate the rule of having the same number in the same 3x3 box more than once.
I was very happy to be able to solve the puzzle without help in about 27 minutes, though I had watched a previous video of yours that mentioned Gurth's symmetry law. I didn't fully understand all its applications and definitely would not have come up with something like the proof by contradiction you cover in this video, but I did have a rather simple way to intuit what was going on. Basically the idea is logical symmetry. When the givens are symmetrical, whatever logic you use to make a deduction on one side of the grid, the same can be made on the other with the other digits. Eventually as whatever logic you use makes its way around the puzzle, it will converge in the middle with a symmetric solution. It's not a proof, but it was a good way for me to wrap my head around the idea of symmetry.
One word. Amazing. Thank you truly so much.
I solved this in 22 minutes... i realized the mirroring after 5 minutes trying to figure out what to do next... now I am going to actually look at the video if I could do it in a better way.
Theorem: Suppose there is a substitution transformation and a symmetry transformation that both preserve the rules of sudoku. Then suppose there is a puzzle where the givens remain the same after these transformations are applied in sequence. Then, if there is one solution, the transformations must also transform that solution to itself.
Proof: Assume there is a solution that does not transform to itself. Transform the solution. It must still be a solution to the puzzle as it still respects the sudoku rules. Also, the givens do transform to themselves, so the transform of the solution gives another solution to the initial puzzle. But then there are two solutions, which contradicts the condition that there is only one solution. Therefore by contradiction, there is no solution that does not transform to itself and, the solution must transform to itself.
The notion of symmetry is that the givens are in symmetrical positions in regards to some kind of positional symmetry, which would be rotation by 90 degrees in any direction, 180 degrees, or mirroring horizontally, vertically or along any of the diagonals OR ANY COMBINATION. And then if for all givens of digit A got swapped into a position where there was previously a B, and all B's got swapped into positions where there was previously an A, then the whole condition is satisfied. Note that A and B are allowed to be the same.
If all the givens are symmetrical, then when you have enough information to make a deduction, you will by symmetry also have the information required to make the symmetrical deduction. The only new information given to you by Gurth's theorem is that if the symmetry is mirroring along a line, then since there's a unique solution, the 3 numbers that map onto themselves, and there can only be 3 such numbers, have to be located on the line of symmetry.
Reminds me of this brain teaser I once made, where you know the solution only because you know there is only 1 solution :-)
- Person X wants to guess the number Person Y picked, between 8 and 100.
- X asks to Y: Is your number >50? B answers, but lies. We doesn't know the answer, and X doesn't know that Y lies.
- X asks to Y: Is your number a multiple of 4? Y answers, but we don't know if Y lies or not.
- X asks to Y: Is your number a square number (e.g. 1, 4, 9,...)? Y answers, but we don't know if Y lies or not.
- X asks to Y: Is 3 the first digit of your number? Y answers, but we don't know if Y lies or not.
- X says: Now I know your number!! X shared his guess with Y, but Y says that X guessed the wrong number...
With all this, YOU have enough information to know exactly the number Y picked!!
-----------------------------------
SPOILER / SOLUTION
-----------------------------------
- Q1: a=50
- Q2: a=multiple of 4 ; b=no multiple of 4
- Q3: a=square number ; b=no square number
- Q4: a=first digit is a 3 ; b=first digit is not a 3
- For each number between 8 and 100, write out the possible way to get to that number. E.g. for the number 10: Q1=a (=50).
That's not the same... In a sudoku, the uniqueness of the solution does not depend on knowing it's unique. That only influences the technique we use.
In your problem, it's not sufficiently defined, and telling us that there is a unique solution doesn't change that. There's nothing stopping Y from picking any number that's >50 as Y has the freedom to lie or tell the truth when answering.
All we know is that Y answered no for Q1 and yes for Q2 and Q3, which left X with the options 16 or 36, in which Q4 rules out for X, but we don't know which, and we don't know which of those answer are true.
TED X has presented a similar riddle, but there we know whether each answer is true or false, which allows us to deduce the number Y had in mind based on the established properties of the number from the answers. The given answers to the questions are deduced from a path that would narrow it down to one solution exactly by the time X guessed it.
very nice, very pleasing, you did well explaining it and thanks to girth x
Restatement of Gurth's:
Within a valid Sudoku, if the givens have a symmetry, their complement must also have the same symmetry; if it did not, then by reflecting the complement over the axis of symmetry that the givens have would create a second solution, which is impossible.
It's probably not implemented in any solver anywhere, because it assumes uniqueness rather than proving uniqueness.
At the same time the solver, when using pure brute force to count the number of solutions, came up with exactly 1. Probably used uniqueness along the way. That was the one small part of the video that did not make sense.
@@57thorns Brute force doesn't rely on uniqueness, it proves or disproves uniqueness. Since there are 6,670,903,752,021,072,936,960 valid Sudoku grids, it isn't quite feasible to just compare all of them to the givens, but it is feasible to take the givens, use the first-order Sudoku rules to enumerate the values that haven't been ruled out yet, and then try a proof by contradiction on one of the cells with the fewest possible remaining values, and recurse.
@@danpowell806 Normally when using uniqueness this is to avoid bifurcating into something that will lead to a contradiction.
What I did not pick up on is that the sudoku grid between 4:22 and 11:30 is under specified. It has multiple solutions.
You never need to assume symmetry or uniqueness to solve a correct sudoku if you are prepared to bifurcate and start exploring different possible partial solutions, it is just a fast way to avoid false leads.
A better restatement, that doesn't need to assume validity:
For any transformation of the grid that preserves a valid Sudoku, is it's own inverse functon, and can produce its input as its output,
if applying that transformation to the givens produces the input, there exists a solution where applying that transformation to the completed grid produces the input.
I can't figure a formal proof at the moment, but I think generalizing to 'any transformation that preserves validity and is its own inverse' has interesting effects. Even more so if it also holds for a transformation which takes three iterations to reverse (e.g. take the top three rows, roll them around by one, and adjust each number to +3, mod 9)
How can we check there is a unique solution though without just assuming it? It seems the diagonal still must be bifurcated without using 2 4 and 8 to prove this? Or a fancy logic solve with multi chains and nets?
Wow! I'm very impressed with your mind Simon!
I let you guess how he lost his hair : it gets too hot under the hood
I colored boxes which are the same as box 3,7 green and box 2,4 orange and box 6,8 blue It really helped me a lot.
When I tried it, I gave up after an hour.
awesome work
Does Girth's theorem apply to 90 degree rotations and top-bottom, left-right mirrors or only 180 degree and diagonals?
The puzzle linked to is different from the one in the video.
Lol! God it’s been a while since I saw that website. I wrote the Sudoku Wiki iOS app about 8 years ago.
It was one of the first iOS apps I ever wrote and got me my first iOS development job. It is still one of the most complex apps I’ve ever written. Mainly down to all the graphics that are drawn over the grid when displaying each step solution.
Understood.
However, I would add one corollary to make Girth's Hypothesis valid in every situation:
Corollary: A symmetrical puzzle must be further defined to have GIVEN ALL 9 digits along with their corresponding mapping counterparts, at the start.
Conversely: If any digits are missing in the original puzzle, therefore the puzzle CANNOT be a guaranteed to have a unique solution.
e.g. if the above puzzle was missing all 3's and all 7's, then there would not be a guarantee that this was a symmetrical puzzle.
Therefore, a symmetrical puzzle must first and foremost have all the 9 digits represented.
You can run this in the modern SudokuPad by just replacing the puzzle ID at the end of the URL into a modern URL.
I solved it
I tried it without you pointing towards symmetry and gave up. You pointed to symmetry, and I could solve it. Knew something interesting was going on there with some sort of symmetry when I first tried it but hadn't had any idea how to approach it until I saw that red line.
I recognized there was symmetry, but I wasn't sure of all the digits and I wasn't sure of the diagonal, but now I think I must have been an idiot not to see it. I did a couple of trial and error and hit upon a 23/25 pair on the diagonal pulled the 2 and I was able to solve the puzzle with another pair that had matching 35. But in both instances, I was guessing and happened to be lucky which was really very unsatisfying. You promised a logical solution and clearly delivered. I look forward to more symmetry puzzles, as now I have a better feel as to what to look for.
The best public solver is Sudoku Snake. This tool is on higher level than anything else including any human ;).
It doesn't include this type of symmetry though so it rates this puzzle as 12.2 which would by far the hardest one ever (of course that's not the case as Simon nicely demonstrated). The reason is that it solves it by finding 2 dynamic unit nested forcing chains. Something totally impossible for any human to ever spot.
This still leaves the question of whether there are other pairs of asymmetric solutions to the puzzle.
... Cheeky Bastards. To think I spent 2 hours of my life on this puzzle! :P
Now understanding the relationship, I managed it in 8 minutes. *facedesk*
I did it the hard way in 90, but it took me 15 once I got the gist of what the symmetry required. 8 minutes is amazing.
For some unknown reason I get nothing like the starting grid as you show it??.
Guessing the technique from an other video (Phistomefel's Killer XXL on May 25th 2020), it took me 14:05, but I have no proof it's a unique one
15:49 I didn't realize I paused the video accidentally, I've been watching this frame for like 30 seconds, wondering why Simon is still and hasn't pencil-marked anything
Tbf it’s a really tough puzzle :^P
Thanks so much for this explanation. I'm a linguistics kind of person, and a chess player with no affinity for math, but hugely interested in logical reasoning; in fact, I solve sudokus recreationally, so puzzles of this particular difficulty hold no interest to me.
It is really very simple. If there existed a non-symmetrical solution, you'd have to break symmetry at some point. Well what on earth could tell you where and how to do that‽ You need asymmetry to seed further asymmetry
What did you study at uni? I know you went to Cambridge and if I had to guess I would say maths or physics
Economics - with a heavy dose of maths. I would have done maths but things like Gurth mess with my head too much and some people just "get it" :)
@@CrackingTheCryptic Selfishly, I have to thank you for being of this category! Because people who "just get it" seldom can deliver as helpful and valuable explanations of certain (at least for me) tricky things, as they don't fully see what might need explaining in the first place, as it is "obvious".
@cracking the Crytic: How can I send a puzzle to you?
There's nothing stopping you. They have an email address for a reason ^^
Their email and their Twitter are in the description
I figured the 2,4,8 down the line. Then somehow couldn't get my head wrapped any further around the problem. Even the second try with this I got stuck until he pointed out the single 8 in row 1. After that it broke down for me.
If the sole solution is asymmetrical, the puzzle must have enough asymmetry to disprove all possible reflections of that solution.
beautiful :)
Conveniently we need *not* presume uniqueness to apply Gurth's Theorem, as there is a generalization which holds true via essentially the same proof, and can be applied to any symmetrical sudoku no matter how many solutions it has. To wit:
ack, whoops. ANYWAY. TO WIT:
For any Sudoku with symmetrical (defined as per Gurth's) givens, the set of cells whose value is the same among all solutions must be symmetrical.
Obviously for a puzzle with a unique solution, that is equivalent to Gurth's, and we can apply the exact same proof by contradiction logic (take a solution, transform it, any cells that weren't symmetrical in that solution must change, therefore those cells can't have the same value among all solutions.) to show that this generalization holds.
That means that if, when solving a puzzle with symmetrical givens, you prove any cell must have a specific digit (that is, you can place it without having presumed uniqueness or applying bifurcation), you can apply this principle to conclude that the symmetrical mirror of that cell must have the symmetrical mirror of that digit in all solutions to the puzzle, and thus place that digit too.
And if you do this and otherwise restrict yourself to logic that doesn't presume uniqueness, then any solution you can reach will be correct - and if the puzzle so happens to be unique, you will have the correct, unique, solution.
The mathematics of sudoku Wikipedia page gives a far simpler and easy to follow explanation with an example.
Hrmn, This feels less like a technique and more a hidden restriction on the solution. Once you know the restriction (the rotation or reflection) the single solution becomes clear.
Made a sudoku solver not long ago, and I've poured some hours into watching this channel because of it. I have to say that the interesting solves I've seen are ones that use the property that there is a single solution because it's one thing to work out the logical constraints from the rules, it's another bit to pick up on logical constraints given we know there's only one completed state. When I originally made the solver, I don't think I was aware that a real sudoku by definition had only one solution.
What I've been curious about for ages though is what the minimal set of algorithms / strategies that would guarantee a solve (assuming a proper sudoku). Because at least from the few techniques I'd implemented, it seems some algorithms subsume others in solving the puzzle.
I'm trying to work out in my head what's going on here, because I'd love to try to implement this.
The guy that runs the solver often shown in his videos set out to do exactly what you have stated. You see how many steps he has progressively added to it in his findings. As for how to model this, have the computer first check each 45 degree split for -if {_&_!=0} -then consider symmetry. I'm not sure a nice way to do the full rotation check, but it would fall similar. Then do simple coloring, start by highlighting given (1s) and proceed to highlight (2s-9s) until a pattern becomes valid for (1s), if none, set color then change to next color. Continue through until all numbers establish a pair, not pair. Set eliminations and proceed.
Amazing. Well done. But I must say, as soon as you recognize the symmetry, and that the main diagonal must be solved for 2-4-8, if you are looking at ALL the remaining Candidates, it becomes a "BABY" Puzzle, and can be easily solved after that, in less than 2 minutes. Nonetheless, your application of Gurth's Theorem was astonishing. :-)) Hats off.
Take a look at Sudoku Susser written by Robert Woodhead (google it) It found the solution to this immediatley and it is a great way to learn the techniques to solving these puzzles. alaoing with tutorials like this of course.
Hoduko managed it only by two "brute force" digits, and very complicated chains later on ... you, Sir, are evil! ;)
Does the computer solver not actually brute force the puzzle? Any sudoku with a unique solution can be solved by brute force, and computers are really good at doing it, compared to humans. I would have thought the computer solvers would do so, at least as a last resort.
Only Hoduko resorts to brute force, neither Andrew's nor Duncan's sudoku solvers resort to brute forcing. Besides, not even Bowman's Bingo can save a solve here because one application of Bowman's Bingo is not enough to yield a contradiction, you need multiple and nestled Bowman's Bingos and at that point the computer gives up, and understandably so because the complexity of that calculation is staggeringly massive.
@@RandomBurfness I see, it's not that they can't do it it would just take an impractical amount of time. I don't think I instinctively comprehend the sheer number of possible ways to make a fully filled out sudoku board, even though now that I think about it it's probably astronomical.
Not entirely sure, but would the computer not have to brute force to count the number of solutions?
@@flodorf64 even I could tell you the number of solutions if you have me a pencil and some time. The difficulty lies in systematically actually going through each and every possibility to see if it works as the unique solution.
@@RandomBurfness I needed three bifurcations, interacting, to get any where.
You know when you say "rotational symmetry" .. when it's just a line of symmetry on your puzzle... that kinda grates .. just saying :/
I would like you to solve this without using the symmetry trick.
The computer solver wasn't able to do it. How do you expect a human to do it?
I quit here: i.postimg.cc/bwC8hN5j/Sudoku.png
I ran through each number, only got a handful of Snider notations for my effort, and can't use any techniques that I've learned to make any further progression. I'll watch the video, but I have no true interest in this puzzle.
This is not really a true Sudoku puzzle, it is an exercise in futility. Are we really using "logic" to solve this puzzle, or are we just playing 'pattern politics' with this so called "Gurth's Theory". That is not Sodoku.
Sorry, not a fan of this puzzle.
I like your explanation of the theory, but This is not a true puzzle. Sorry.
If you can prove that there is a puzzle out there that starts symetrical and doesn't end symetrical then I'll agree with you. However saying it isn't a sudoku just cause you don't like the logic is extremely selfcentered and narrowminded way of thinking. "Oh I don't like this logic, therefor it is not a Sudoku". I'm not a fan of killer sudoku's but they are still sudokus.
The fact is, is that with the Gurth's Theorum, this puzzle becomes a lot of fun to solve. having to use both standard sudoku methods and the extra information gathered from the symetry to slowly work towards a solution.
You're allowed to dislike a puzzle, but don't go disregarding something that is true, just because you don't like it.
@@draconicdusk5911
First off, never said I didn't like the puzzle or it's logic. I did solve it. Just like Simon say about the 'world's hardest sudoku' "this is not a true puzzle." A puzzle he didn't even try to solve because it has a real logic to it, and neither does this.
A logical puzzle is something most people can solve, a pattern reconnection puzzle is not really something everyone can do. Just look at the comments for this puzzle a couple of day ago, almost everyone, who said they solved the puzzle, said they use all kinds of X wings, X wings of 4's. Simon solves the puzzle, no x wings.
I solved this puzzle with brute Force, which is a fancy way of saying I guessed.
We can agree to disagree, but this is NOT a true puzzle.
Just because you couldn’t solve it without guessing doesn’t mean it’s not a puzzle.