Solving Sudoku in Swift

0 0

um welcome today we are going to be where twist a little bit we're going to write a Sudoku solver in Swift so this is me this is my blog it's boring and fine so I just want to get like a kind of a temperature of the room who here knows what Sudoku is almost everybody okay basic rules you kind of you get this board and this board has a bunch of open holes in it and you got to make sure that you fill in these holes with the numbers one through nine every row must have one through nine once and exactly once every column must have one through nine exactly once and every little mini grid here that you see also has to have one through nine exactly once so we're going to write a program that takes in this board in a specific format and tries to figure out what all the correct numbers are to put in all the holes so cool so a little bit more just gauging where everybody is who here is written any swift before two people three people five people all right cool some people who here is written like a like a language in the same generation and swift maybe like a rust like a Kotlin maybe even Scala anybody a couple people okay who here is familiar with like mapping and filtering lists most people okay cool you don't need to know any Swift to follow along I think the concepts are pretty well expressible and I'll try to try to walk everybody through them as we go along it will help to understand the maps and the filters and stuff so okay cool so that is it and I think we're basically ready to go this is an Xcode playground this is sort of a live coding environment when you sort of hit run or when you change the code it will run for you expressions get evaluated and their values come over here so you'll see like we have this board here the board gets initialized into a board object which we'll look at in a moment and we fire up a solver for that board we check if the solver and solvency false and we run the solve function and then we see the default that the board is still not solved that's because our solver solved function doesn't do anything yet so we're going to be writing that whoops and yeah so when this runs they're well settled so down here which we're kind of prints the status of the board up here you can see it will sometimes say compiling and since that sometimes they running and that will represent just like where we are some of that stuff takes a minute or a few seconds at least and so just be patient I'll try to tell jokes in that in the interim and you can see in this console we have like our pretty printed board with all the representation of how it looks so let's look at some of the sort of domain stuff that we have set up everything is built on the back of this thing called a cell a cell is sort of this object that represents this it represents one little tiny box in the pseudo-code rid and it can be in any number of values it might be the values one through nine where we don't have any idea what it could be it could be one specific value if it is one specific value would call that settled which means we know what this value is and we're good and we're not changing it it's got a little bit of like the ability to check if it's equal to another cell it's got the ability to print itself out if it's settled it'll print just a string of the number and if it's not it'll print an underbar which you'll see down here and then we have two little convenient centralizers one to create a settled cell with just a value and then one to create a cell that could represent any number which is represented by this range here one through nine and then the cells like come together to form this board the board is fundamentally backed by an array of arrays of cells those are just calling rows this function is pretty boring it just kind of takes our string and maps over it to make our row arrays we won't we won't to have too much into it but you can basically see we have like if a character as a period means that's a blank will make that cell about anything that can be internationalized we had before and if the value is convertible to an int that means that it is settled and otherwise it's malformed and we're just going to crash the whole thing so a couple helpers here so cells just returns rows joined this is like flattening if you're familiar with Ruby or Scala and it will just take an array of arrays and turn into one big array description prints out this lovely lovely little picture that you see here is solved checks if all the cells are settled that means the whole board is solved we'll be using and quite a bit and here we have three little helper functions these helper functions will basically given in it will give you the whole row given it will give you the whole column and given it will give you the mini grid the Row one is not too bad because we already have an array of rows the column one is also not super bad the mini grid one is a complete nightmare um we could walk through this but just it works and I don't want touch it so that's the mini grid the row in the column and we use those to basically write two functions down here one of them is called Ken update which will essentially given an index and a set of values that you want to update there it will create a cell for that those particular values that you passed in find the correct row index and column index and set that in your in your like backing array it does one extra thing which is that it checks to make sure that there are no consistency err it's a consistency error in this case oh sorry I did this backwards I did update a set of can update can update just makes sure that you can give in your row give in your column and given your index the value that you're trying to update to does not exist already if it did exist that would mean that this board would be invalid and so we can't update that that update function our sake mark uses that can update method to check if it would be a legitimate you know change to make this board and if not it will throw an error that we will catch and handle later that is more or less everything you need to know I made a consistency error it doesn't really do much cool that is more or less everything that we need to know to get cracking when I solve Sudoku puzzles I thought that the kind of strategy that I would approach normally would be basically look at a cell and figure out what possible values it could be using the the row that it's in the column that it's in and the mini-grid that it's in and if there's numbers exist in those rows column in egrants we can eliminate them from the possible values and if we have one left that means that we are in good shape and and we can update that value to some settled value and then move on to the next one so to do that let's kind of build a big loop so if the thing is solve we're done but if until it's solved we just want to federating on this thing and as we'll see in a little bit there are some puzzles that actually can't be solved using this technique and I'll go into why that is in a little bit but just in case this puzzle is unsolvable by this technique we're going to create a little sentinel value called found something this iteration and this sentinel value is basically whoo all right this dental value basically just ensures that we did update something this whole loop through the studio keyboard we didn't that means like we could keep iterating and keep trying but we'd be doing the same thing over and over again and that's the definition of insanity so we are just going to bail out if we did not find something this iteration just build a little whole thing we leave the board in an unsolved state but that's ok because we won't be able to solve it using this technique so what we want to do is we want to go we want to iterate through all of the array all of the cells in the board and we want to basically take a look at each one and find which possible values that could have so we'll have you know a cell and if that cell is settled then we're good and we can just return and this return is is bound to this block so it will just return that sort of loop iteration and so let's let's go ahead and write a little something to check among all the possible values it could be from 1 through 9 which ones are valid so we want to basically ask even 1 through 9 filter through those and and what we really want to know is can this cell be updated to this value so to do that we wrote our front nice little function can update and we need an index we don't have that yet but we want this value we want to check if this value would be valid here essentially we're looping through all 1 through 9 and if this returns true then that means that is the possible value so the result of this is going to be possible values the first Swift weirdness that we run into is this let versus var let represents a reference that's immutable that can't be changed and var represents a reference that will need to be changed later this one will need to be changed we're going to leave it a lot but we'll have other ones in the future that will be so to get this int we need to we need a way to basically say when I get the cells I also want them to be sort of zips together with their with their indexes so there's a handy function in the standard library called enumerated which will not only give you the cell but it will also give you the index this is like a monotonically numbers monotonically increasing number starting from zero for a raise that does correspond to index is zero one two three but if it's not an array it doesn't really correspond to anything other than sort of way right in this case we're going to rain so it's fine and now we have an index that we can stick in that spot so now we have this array here and this represents to the represent anything until its compiles uh it represents an array of integers which is the possible values that we could operate update this cell to so let's let's run a couple of quick sanity checks if the possible values is empty then we will just return because that means like some kind of consistency err has already happened and enough this can't be updated to anything something's wrong really wrong and if the possible values has exactly one object in that array that means that we found something definitively and we know what that value is and so we're going to say we did find something consideration thank you so that's going to makes me make sure that we keep iterating and we keep going through and then the last thing we're going to do is we're going to try updating the board with at that index with those possible values with the things so this question mark essentially just ignores the error that comes back from it we know that that update is going to be valid because we checked if those if those values could be updated there so we're not going to worry too much about that error which can discard it and not worry about it so now that we've written this this solve function this is pretty much the whole thing we're going to run back we're gonna step back to our main area and we're going to run this solve function and see where we are and if I didn't screw this up this is going to work ready cool so we see our original board here and we see our solves board here we basically solve this the way that I thought all Sudoku puzzles could be solved just figure out what could go in each hole and then just put it in the hole turns out that that does not actually solve all puzzles here's a harder puzzle and we're going to solve it using the same technique same code and let's run this and the first one runs and solves the second one runs and does not solve so we can see here is solved as false before we run solved and it is solved is still false so this is not a solvable puzzle using this technique and I didn't really understand how that could be like I thought that's how I did all Sudoku puzzles but I think there's a blockbuster by Peter Norvig and he does a really good job explaining why this is the case he says there are more sophisticated strategies let's see if we can zoom this to chance the right amount he has that there are more sophisticated strategies you can use for example the next two twin strategies strategy if a five and a six are both limited to options two and six we know that everything else in that row a can't be two and six that we can eliminate it and and that's like an effective strategy could use to solve a Sudoku board but there's lots of some like lots of such strategies and programming them individually is going to be kind of a drag so let's just write one function that can just do it no matter what as he says let's make sure that we can solve every puzzle so for those following at home what this means is we are going to brute force it now if you want the brute force like in the traditional sense of just try every single combination it would take hundreds of billions of years and I only have 14 minutes left so that's not going to work but because our sort of naive approach limits each cell to its possible number of values or its possible values we already like have eliminated that space that we need to search by a lot because we know some of the values that are automatically invalid and kind of we kind of just get those entirely so we can get this down to a pretty manageable sort of space that we have to search so to do that first we kind of call our naive solver function I'm going to change this to brute-force real fast so that this is ready to go and to do this we're going to call our naive solver and that's going to fill in every cell with the correct number of like possible values it will only like contain values that would be valid in that spot even if we don't know which of those values it is so that's that first thing that happens if that solves the puzzle then great I'm out of here if it doesn't solve the puzzle puzzle we need to basically we need to yeah so when we're forcing we basically want to take some given cell try all of its possibilities generate a board from each of those and then attempt to solve that as though that were the correct value if that solves then great we know that that value that we pick subtract if it doesn't solve then we know we need to try another one so to effectively do that we basically need to know we need the first we need a cell that is not settled yet so to do that let's talk to the board let's ask for itself and let's get the first cell where that cell is not settled is not settled and we're going to put a bang here this bangin swift is for handling optionals because this function first where if nothing passes this test nothing will be returned and so switch does make that it's a type system into something they called optional and so it means you basically need to check hey is this thing know before you start working with it this Bank says trust me I know what I'm doing and forces it to unwrap if that fails then it will crash the application but I'm pretty sure that this won't fail because I've already checked it it's not solved so there must be an unsettled cell in there somewhere so real application I might you know do a little bit more work to make sure that this degrades more gracefully but in this case a bang is fine so we've got our cell and we want to explore every value that that cell can be right we know there's more one because it's not a settled cell and this next step is where some of the real Swift magic happens because the board and the cell when we define them we define them as struct which has basically two two two two patterns for making objects one of them is a class which is what our solver is and the other one is destruct instruct is a value type which means that if you have a reference to a value type you are the only parent or owner of that value type and if you mutate it it won't affect anybody else's copy of that of that object and what that means is by basically by just creating a new reference to this board we've actually created a full deep copy to the entire board and all of its cells with this copy we basically have a scratch pad that we can probably play around with and say hey if I change this thing will that lead to a solvable board if so great and if not let's slow this out and try another one so copy is going to be sort of our scratch pad that we work with we are going to just try updating that that copy and we don't have an index yet again where we do have a value which is the like sort of current value that we're checking and and if that throws our consistency error if we're going to catch that error find that error to a value if it throws a consistency errors and that means that the value that we're attempting to insert there is not going to work it's going to cause an inconsistency and so we just want to discard this whole board describe this whole attempt and move on right so we need this index we're going to do the same trick that we did up here which is basically to enumerate the cells with their indexes so we are going to pop this here and now instead of getting a cell we're going to get a cell and an index and it means that this will have to put a little element in here so that we are noting that we are not referring to that offset we're referring to the cell specifically and that should work fine and now we have an index to put in here which is sort of the index of course is that cell that we're taking a look at and then once we have a board that is we know it's consistent because it didn't throw an error we have a board it's consistent but it's not really solved yet so we can apply a fun little technique called recursion and try solving that board assuming that that value that we set was correct so create a new solver acid2 copy that we've mutated attempt to brute force that copy and then check if the solver is solved it in solve ourselves we can copy that solvers board back over to our our own board and then when we sort of loop back around and we check these things solved they will have been solved this again is copied back this is again because of those value types we're making sure we're not updating our own board we're dealing with basically a totally new value until we copy it back to our own board explicitly which sort of ends the process this oughta work cool let's give this a shot and see what happens I'll actually do one more thing and just to make a nice little animation I'm going to print the board out as we go along through this process assuming that this works so it's compiling this is the part that will take maybe a minute or so to run the whole thing but you'll have a delights a little animation and if it's all working I may have a chance to share a fun little San Francisco story who hears from San Francisco who years visiting San Francisco people if you'd like to make a third and every day listening okay so the print didn't work our that's running up a bit so you can see it's attempting all kinds of different things it runs into a brick wall and then kind of dial themself back and it just keeps iterating through this thing until it's until it like gets to a state where you can fall themselves the fun San Francisco thing is there's a start up here called scoot and it they let you basically rent electric scooters and they're all over the city and so pretty much for the past two days all I've been doing is scooting around the city and just like exploring and it's like it's more fun than uber because you get to control where you're going and like the wind is in your hair it's a lot of fun um and it's like it's a little cheaper than uber twos in an advertisement I just found these guys on the internet and I don't know it's just been great if you have a couple of extra days and you can sign up for this thing it's really fun um it's like I know it's the best way that I've found to get around San Francisco you don't have to worry about Hills on a bike because it's got a little motor and it's great so now our puzzles solved and we saw it like kind of step through all of the processes and through each of these iterations and until I found one that the naives flower could just trivially solve and it solves it and we have a valid circuit board you can kind of spot check this with your eyes and make sure every mini grid and row column check out but I'm just going to assume that it worked um so yeah so that's our brute force method I'm going to add one more I'm going to add one more optimization to this which is that if you imagine what we're doing is basically we're searching through a big tree right the first thing that we check maybe it can be one of seven different elements so we're going to try the first one and then that one can maybe we're gonna try the second 7th unsettled and maybe that one isn't one of five elements and one of seven of us and all the way down to make a huge tree once we hit a brick wall we kind of get the dial back and jump back up and if something is something inconsistent happened there we know that that value is wrong and we can kind of cut out a whole portion of that tree so the tree that we're building is very sensitive to how wide it is at the top if we can start with smaller choices then we will basically be able to eliminate more of the tree at the same time if that makes sense and our depth-first search because we're trying to get to one of these nodes where all the values are set will go much faster so to basically what we want to do is instead of finding the first one that it's unsettled where in this case it looks like you know there would be this one and then it would check this one we want to find the first one that is unsettled and has the fewest number of possible values and so the easiest way to do that is is after we enumerate ourselves we're just going to sort that entire array of all the cells and we're going to we'll have a left and a right this is how your right sorts and Swift and then we're basically just want to know oops sorry this wants to know are the elements in increasing order I know that's a bit hard to read but they want to know if the elements are in increasing order so we gotta use the less than operator so um we just want to know if the left value dot element dot values count which is annoying but that is less than the right element values dot count so this will basically sort our array by the by the cells that have the least protect these number of potential options and we'll find an inconsistency faster and we'll be able to eliminate more of that tree when we run this compiling compiling when we run this even with the print turned on which actually slows it down quite a bit we can see how much faster it is cool and you can see like it no longer is starting sort of from the top it's starting from different places and it's already done and even have time to share any stories about scooters much faster to to search through that that way so that's in essence how you solve Sudoku this is an example written in Swift we reused a couple swift features that I think are pretty good and I want to go through some of them so swished is a pretty new language it's only about three years old and it has a lot of rough edges so like string handling in particular is pretty bad regex is a subset of that that's like even worse they're figuring a lot of that stuff out but one thing that they got right very early on with sequence and collection handling if you can boil something and switch down to a sequence you can you get a whole bunch of tools that you can use to manipulate it and work with it so for example all this mapping that we're doing to like build our build our sort of board up from our string when we print our description that's a map and another map when we build our mini grid that's a flat map and some array slicing and this stuff makes it so it's much easier to work with with these objects and even in our in our solver we use like this enumerated function which is this built-in function for getting the index and the and the objects at the same time so switch selection handling is really nice and makes this project a lot better the sort it is another good example of that another thing that we take advantage of is Swit air handling system right here so this because this function can throw says it's a throwing function we have to call try and catch its error explicitly or handle it in some way and a lot of people don't like Swift's error system because they want exceptions and they wanted to be able to throw from anywhere and catch from anywhere but switch type system forces you to be really strict about what errors you throw and recover from them in meaningful ways it's it's a hard system to use but once you get used to it there are a lot of interesting places that basically get a lot better when you when you can use stuff like this you can essentially have a secondary pass out of a function as marks like sort of arrow path and the last feature of Swift's that we used was this this value type system by treating the board and the cells as values rather than as references as as sort of like reference types that we you know that multiple objects can hold on to the same reference of we are able to trivially make a new copy of our board in ourselves without having to you know do any extra work it just sort of happens out of the box and we can mutate that copy and do what we want to it and only when we explicitly choose to do we do we like copy that back so those are some of the swift features that we use to sort of build this to docker solver my name is Suresh and it was a real pleasure talking to all of y'all today and I will hopefully see some of you later all right [Applause]