Computer Says "No": A New Sudoku Breakthrough

[Music] hello and welcome to friday's edition of cracking the cryptic where i'm still on a bit of a high after live streaming the witness last night thank you so much to those of you who joined me on that stream it was a it was a great deal of fun quite a lot of frustration with all those bird noises but anyway anyway i did manage to get a good night's sleep and i'm well i'm very much looking forward to the next attempt at the game um i'm not sure when that will be what day are we on today i've just said it's friday um so probably early next week uh and as soon as i know i will let you guys know as well but we have a quite an exciting um hopefully an exciting video in store for you today because our most popular video recently was a puzzle where i was instructed um before i started solving it to put the puzzle into a computer solver and demonstrate that the computer solver couldn't do it using any reasonable methods and that's what's happening again today this puzzle on screen is a is a classic sudoku by the constructor jovial one of the world's great constructors and apparently she has come up with a sort of another a new technique that the computers don't understand and this is tremendously exciting but it is also pressure because it means that if i can't solve the puzzle then this will never see the light of day and the breakthrough technique will be known in uh arcane places of the internet but may not be known to the wider public which would be a great shame um this is called cobra roll i've no idea why um [Music] no it means nothing to me but thanks very much to those of you who recommended this to us apparently this is something of a masterpiece and right well let's get to it let's in fact we know it's classic sudoku so we all know the rules and what i did before i started the video is i put this into this computer solver now this is andrew stewart solver you can find it just google sudoku solver and your this is what you'll find and if you look down the right hand side it lists a whole load of very complicated looking techniques many of which i have no clue what they are and certainly when you start to get down to these ones down here alternative inference chains i mean that's just the very definition of guessing it's saying guess a cell is this and then go along a whole load of steps and prove that there's a contradiction and then you can go back to where you started and say well it wasn't that after all so basically you know all this stuff initially forcing change self forcing change i don't know what they are but um they're all akin in my mind to guessing now let's just uh let's just prove to ourselves that the computer doesn't enjoy solving this puzzle so i'm clicking take step which i think i have to do a lot of times so let's see what it's going to do it's not put a digit in yet right so it's first elimination is almost quite instructive isn't it it's managed to eliminate a 2 out of the multiple possibilities left in row 8 column 2 and it's done it using some weird x cycle so let's move on let's see what it does and what what on earth is that it's managed to eliminate a seven from that cell using a grouped x cycle which i only vaguely know what that is uh it's now it's now it's doing alternative inference chains now it's doing digit forcing chains so i mean already i think we can safely say that the computer is having to resort to the absolutely bizarre weirdities that it it knows and can just devote processing power to in order to spot them there is no human being is going to be coming up with these things um that's another guess basically what on earth is that it's another very long string of things oh it's got that gave it a digit look um i'm quite enjoying actually watching what oh what's that 3d medusa whatever that is that was at least colorful um more guessing alternative inference chains more alternative inference chains and now a digit forcing chain which gave it a digit another digit 40 chain that looked like another 3d major so i'm just going to click through because i mean this is just i think what the idea was to establish that this puzzle is brutally hard even for the machine and i think that we have certainly achieved that i mean it's still what on earth is that a unit 14 okay come on i mean goodness me this this is certainly one of the this must be one of the hardest sudoku's ever created i think that this is what we have basically deduced here i am anxious to see if the computer actually does solve it in the end that was initial forcing what is oh i got purple and pink an aligned pair exclusion i did once upon a time know what that was ah look there we go and that suddenly allowed it to make some progress so and now it's finishing the puzzle so it can finish it all right the computer can do it but it's having to do it using basically a sequence of esoteric guesses that is our contention and that the challenge will be to see if we can solve it using not esoteric guesses because you know me i will not guess um do have a go the way to play is to click the link under the video um in fact i have just got a moment to say something first there were some um moments in the stream last night where i didn't read out people's donations i'm really sorry i'm going to go through all the donations and i will read them out on the channel and read well i'll read out the names of those who who donated mark emailed me to say that i should just shout out um mega lamb who apparently gifted me the cost of buying missed uh remastered on steam um which uh they were hoping might be the next game that we stream so uh thank you very much megalam that was a very inventive donation um anything else to mention we're trying to get towards 400 000 subs if you enjoy the content please do subscribe we would appreciate it and with that said let's get on to this okay cobra roll by jovial you can play by clicking the link under the video now i get to play let's get cracking and the weird thing about doing these puzzles when you've seen the computer fail or not fail but have to use extreme guessing is that it feels very hopeless at the start because you're basically faced with the prospect of not being able to do the computer remember couldn't place a digit until i think it got a two here after about eight guesses um so all i'm doing at the moment uh is trying to pencil mark the grid as i ordinary ordinarily would so when i put numbers in the corners of cells in a box like this i'm saying the two can only go in one of those two places let's double click threes uh no double click fours oh yes i see right there is a pattern there look ones and fours are looking into box three and have to go into the same two places so the computer probably picked that up instantly but i didn't right and now look at this box and you can see we've got two three pairs [Music] looking into this box and now because of these pencil marked ones and fours we've just placed the twos and the threes can only go in those squares which means those squares are seven and eight so this box actually gets resolved quite not resolved but it gets limited quite well um so maybe we look at fives now at least we have got three fives in the grid fives are in one of those two places and one of these two places and anything else maybe not uh sixes let's look at sixes we've got sixes are offset in box six look wow wow i mean even knowing the computer could just do nothing it's quite surprising to me how little i'm even managing to pencil mark here eight eights are in one of those two cells ah eights in this box are in one of those two cells i suppose what i could have done is just take the computer's initial pencil marks and go from there but actually i find this process of sort of just highlighting the grid helpful it sort of imprints the template of the puzzle on my brain somehow right so is that literally all the useful pencil marks we get that does not seem to be very helpful so now what i'm doing is i'm trying to spot weak cells in the grid and what's what do i mean by a weak cell well i mean an individual cell now like this cell this cell sees four different numbers it sees one two three and five um you can see how it does that and it sees eight nine in its columns so that square can only be four six and seven um i'm wondering if we're going to find any more weak cells as i just sort of scan the grid i'll probably miss some of them but hopefully we'll find one or two that might lead us on a trail somewhere um [Music] that cell looks a little bit weak doesn't it because doesn't that see one for in fact let's work out what this can be i think this can be two it can't be three four i think it can be five it can't be six seven it can't be eight and it can't be nine so that square is very restricted actually oh hang on that's right now i've just noticed something else which is that the puzzle has symmetry doesn't it around this diagonal the positive diagonal this diagonal here so it doesn't have rotational symmetry which is something we often see in classic sudoku's but if we imagined a line a perfect straight line going from this corner to this corner of the grid and then we folded the grid on that line all of these givens would match up in fact the threes and the twos would actually match but yeah that's quite interesting as well those four digits there would actually hit each other which is that is interesting now the other thing is other digits would hit each other they wouldn't be the same but all of these digits would hit each other as well so i'm just wondering actually now if we think about the symmetrical equivalent of this square around this diagonal no it's this cell isn't it which actually isn't quite as restricted as this one is because it sees two fives whereas this one saw ever in every way it's seeing a different digit which allows it to be reduced to just two digits this one i think can be only reduced to three digits it can be a two a seven or an eight okay um [Music] i'm intrigued actually about this that is interesting to me as much as from a setting perspective as anything because if i was trying to set a really clever puzzle you know if i found a technique that i wanted to showcase then this is the sort of thing you would build as the sort of you're the base of your pyramid you would think about early numbers and where you needed to put them and the fact they're symmetrical is well it's at least interesting to me um but anyway let's carry on looking for weak cells we've got yeah okay those two cells are interesting aren't they because they see six seven eight nine in their box and two four in their rows so these have to be one three and five and in fact that one can't be a one so that's three or five the uh the symmetrical counterpart around this diagonal of this domino is this domino and look at this domino again something similar look ones threes and nines are the only options for these squares and that square can't be a one so these dominoes i might just highlight those for a moment and just let me think about those have we got something interesting about those cells three yeah well [Music] it's certainly quite interesting to think about what's not in these for example if there's no five in this domino where does the five go in row five can't go here can't go here doesn't seem to be able to go there because of these crossing fives so the five would go there that would give us a two and then you'd be off on some sort of chain that may fail but this is somehow quite restricted isn't it um but we're not interested in chaining i wonder if there's something there as well does that affect that digits no we don't have quite the same potency do we between those two cells so the other weird thing about doing a puzzle like in this strange way where the computer sort of already analyzed it is that what i would classically do now is i would look at rows and columns and look for places where a digit can only appear in one of two places in that row or column um because that's the sort of bedrock of so many advanced techniques that i do know so i do know about x-wings i do know about skyscrapers i do know about empty rectangles all of which take us their sort of basic position that a digit can only go in two positions in a row or column um but there's no actual point doing that here because the computer would have found x-wings and empty rectangles and skyscrapers so i think we're almost almost it's beholden upon us not to do that i'm gonna think i'm gonna think about i'm gonna think about these digits i think um so well let's start with once um what do we see about once here the answer is not a great deal to be honest um [Music] ones one's in column one and row nine are a bit restricted but not not massively so so the only places for once in column one and row nine are those and i was about to say something that would have been nonsense which was i was about to say that doesn't that mean there has to be a one in one of those two positions but there doesn't so i was wondering if it was this square that was what what we were trying to get at but that's not right because i could put one in the corner and if you put one in the corner it deals with where the one goes in column one and row nine if the one is not in the corner then it is true to say you have to have a one in one of those and then that couldn't be a one um hmm okay i don't think that's uh okay but it is interesting actually because two two is also restricted actually yeah okay so let's look down this column and ask where two goes and it can go here or there or there this year this well i don't understand this but i am suspicious about it because look it's symmetrical where does the two go in row nine it's not there it could be here but if it's not here it's those cells so actually you get you get a very symmetrical position for ones and twos or possible positions and that does mean that either there must because this digit can't be escrowed in a cell it can't simultaneously be one and two whatever digit goes in there let's say it's one now the two can't go in both of those squares because it will repeat in column in box seven so there must now be a two in one of those squares so that means there is no two in that square but all we actually know is there's no one or two in this square which is and if well we would have already known there was no two in that square if indeed that is a one so this is probably nonsense um but this this is very very suspicious i just don't think i understand it one one is in one of these three and one of these three again perfectly symmetrical around this positive diagonal same thing with two don't think it's gonna work with three though because the the power of the ones and twos is the effect they have on these three cells in each of box one and box nine this does not have anything like the potency does it um oh no although oh sorry i realize this is the most inarticulate thing that anyone's ever listened to in their life but hang on a minute the threes and the falls this is interesting this is interesting because let's let's try and do something similar to what i just done with ones and twos with threes and fours but not in these cells here but but those these cells here row 4 and column 6 because this 3 and 4 rule rule 3 and 4 out of those cells this is weird right ok and i don't know what this means but it feels important so if we look let's do threes first where is the three in this row it's not in any of those three cells and it's not here so it's got one of three options we're getting a very colorful grid and if we do the same in column six look we're going to get identical when i say identical we're going to have symmetry in terms of the possible positions for threes because the threes now have either got to be here here or here and the fours let's do the fours as well so four is one is in one of those three cells and four in the column is here here or here so for all of the digits one two three and four you end up with symmetrical patterns for the possible positions of the digits around this diagonal and i have got no idea what that means but it feels it really does feel like it's putting pressure on these two cells so if you what you can't do because you can't put three in both of those cells can you because if you did put three in both of those cells you're going to give yourself a problem with ones and twos down here because you could although you could hide one of the digits one and two in the corner you couldn't hide both so you'd end up with a repeated digit either in those two squares or those two squares so you can't have threes in those squares you can't have threes in both of those squares so you must have at least one three in these which ones is it it's the green cells you've got to have at least one three in those cells got to have at least one three in those cells i'm so sorry if you're spotting what this means um [Music] got to have at least one three in these cells but it doesn't have to be here and if it was here then what happens to what happens to 4 well then there would have to be a 4 in one of those cells uh but don't think that matters does it i have a horrible feeling it does i'm not quite appreciating why oh this is so frustrating i feel my brain is just he's trying to rewire itself to understand what this means this means something i fear i just i mean i may not be able to see it how long have i had 24 minutes good grief it feels like about two minutes this is a sign of a good puzzle because it basically means your brain has completely been absorbed in it so threes threes maybe i've got to think about it differently is it yeah that's a better way of thinking about it maybe i thought i'd think about the corners rather than the actual so if you didn't have a three in one of these three cells the puzzle is broken that i can see yes that's interesting so rather than think about it the way i was before which was saying what would happen if there was double three here what would happen if there was no three in these corner cells then the puzzle's broken because you can see the only place to put a three in row four is going to be here and the only place to put a three in column six is going to be here and you're going to end up with double three in box five so at least one of those cells is a three but the same is the same is true of four of course it's exactly the same logic if if you don't have a four in one of those the force have to take those two positions and they break box five so hang on a minute so at least one of these well now we can say at least two of these three cells well not at least but one of these three cells at least must be a four and one of them must be a three and oh is this going to be it so if i then flick that round and do it down oh this is ridiculous if this is right that's gonna work isn't it that is ridiculous jovial what are you doing this is just mad wow wow so yeah the logic is the same oh good grief so the key to this puzzle is the corners of this square this is completely insane this is completely insane but utterly utterly wonderful because i think i now at least i in fact i'm gonna i can now place a digit in the puzzle if i can place two digits in the puzzle i can do it right now this is an eight that's a five why can i do this well i just managed to show at some length that at least one of these three squares is a four and at least one of these three squares is a three but now i'm going to do exactly the same now with ones and twos with these three squares so is it possible that none of these three squares is a one the answer is no because if none of these three squares is a one where do you put the one in column one well the answer is here and the one in row nine it's here well that repeats one in box seven that's wrong that's definitely wrong so at least one of these three squares is a one but if we do the same with two we get the same answer if if if if there's no two in those squares you have to put twos in both of those squares and that's going to break as well so now we've got a situation where if i highlight all of these four cells we can say the following there are four cells at least one of them is a four at least one of them is a three at least one of them is a two and at least one of them is a one and therefore those four cells must contain the four digits one two three and four because we know there must be a one and a two in these three and there must be a three and a four in those three so the so there has to be one of each in all four and therefore those squares become one two three and four and this is why i think this square cannot be an eight and the computer did not know that and well human beings do human beings do know that um now does that actually do well this is certainly a dif this is certainly different digits to what the computer got isn't it the computer did not [Music] get six up here now as well but the computer i think got a digit here and then a digit here using a variety of guessing techniques we've got these two digits and we've got strange strange pencil marks and this what we've got to remember as well is that this one two three four is a weird quadruple um so if we were for example if we if we got a one here well we're not going to get a one here but if if if this turns out to be a three we we can eliminate three from the rest of the quadruple is what i'm trying to say in the most inarticulate way ever um now six i can do look six has to be up here and therefore in the top row sorry a brief hiatus there where i was having to deal with the trampoline war that you might hear is still going on um but anyway where were we we just got that digit i think have we yeah we just got this digit so that looks like it's eliminating a digit there uh and giving us a digit there we got a six we got a 5 in box 1 and we get rid of a 5 from there oh yes in fact look where do we put 5 now in box 4 it's got to go here and therefore we get a 5 look in box 7 as well which might mean no so we get a lot of traction suddenly with fives which might matter i don't know now what do we do this square here is only it's got to be a one three or a nine and it can't be a three so that's a one or a nine and [Music] what shall we do next wouldn't it be magnificent if this just collapses at this point if the fact that this is a one two three four weird quadruple just collapses the puzzle i suppose actually one thing i should say is that given this is a weird quadruple and given that we know the one and the two are on this side of the quadruple that is not a one or a two and similarly given that we know that three and four are on this side of the quadruple that is not a three or a four so um is that going to improve anything the answer is apparently it probably is i just can't see how what an idea though um okay let's have a look at row two maybe where we need to place twos threes sevens and ah so this square can only be two or seven oh right so a simple question to ask would be where does three go in row two because the answer i think is only there so that's a 3 which means there's a 3 in one of those 3 cells and a 3 oh and a 3 in one of these two cells this is a 2 now just finishing off the pencil mark logic in box three that's a five out of nowhere where ah there's stuff going on here where does two go in box six it can only go there that removes it from this square which which means it might mean a lot of thing oh well one thing it means is there's a two here by sudoku this is gorgeous and now this is a two by sudoku which means this is not a two and this is a two by sudoku again um this is oh yeah look now that's a seven and this is a two because it's the only place two can go in the box so that's become an eight that's become a seven this has become a four oh this is gorgeous look it is just is it just giving up yeah look that's now a one this is a four this is so so brilliant to actually i mean it's it's brilliant enough to be able to construct a puzzle based on a completely new technique i mean that that is utterly brilliant remember that this is a one two three four quad so this is now a three four pair but then to do it with such a plum where basically once you've done the technique the puzzle doesn't require any more you know alternate inference chains or whatever they were it just collapses it just showcases it even you know in the most brilliant way so it's just jovial saying well look i've discovered this and if you spot it it will completely break open the puzzle and shortcut everything is just gorgeous um now come on i've lost completely lost my train of thought now which was a bit silly of me because i know i can play seven here because i do actually want to now do this in somewhat of an efficient way because that would be optimal that's a nine it's just to complete that column so that's an eight and that's a one and that's a nine and now that's a nine and this is a three and this is a one and therefore we've now done it four and three completes our our square corners this square has a one there's definitely still trampoline wars happening um now where should we look now perhaps this column where those squares are we can place five in the corner that doesn't get a song and these squares have to be a 3 8 pair which we can do though 8 and 3 go in this square here has got to be a four um one of that square's got to be a four exactly that square these squares have got to be six seven and nine which i don't think i can do but let's tidy up the pencil marks anyway six goes after that one seven goes out of this one so this is three six or seven and it's not three or six so this is seven which means that's three and this is six and that's nine and this is seven these squares have got to be one and six which we can fill in and these squares have got to be eight and nine which we can't fill in although it does give us a nice eight nine pair in this column which means that that square there ought to be something else uh is it three it is three okay so that means that's seven this has got to be an eight that's a nine this is a nine and this is an eight and that is how to solve a puzzle of staggering staggering genius no words jovial are going to do um justice to that that is quite sublime the computer had no earthly clue what was going on a human being um you know if forced to use those methods would i don't think get any satisfaction out of solving this because it would seem like just a series of continuous guessing but this one two three four symmetry around this diagonal and what it means for these four squares is one of the most gorgeous pieces of logic we have ever shown on the channel i'm so thrilled i actually spotted it and thank you so much for staying with me and watching um yeah we'll be back later with another edition of cracking the cryptic [Music] you

Channel: Cracking The Cryptic

Views: 85,254

Keywords:

Id: rxxn0F1TPe0

Length: 37min 43sec (2263 seconds)

Published: Fri Aug 27 2021