Before I even explain how I tried to solve Suodku, you can download and install the code from my sudoku repository. After you have tried a few unsolved Sudoku boards, and are convinced that this application does really solve Sudokos, you may continue reading to find out the design and implemenation details. Representing the boardHere I describe my attempt at solving Sudoku using Lisp. Since Lisp is my favorite programming language, it is but natural that I choose to use it to solve Sudokus. Enough lisp adulation and before I digress too much, let us find out what the solution looks like. Please note that the code is tested only on SBCL. Since a Sudoku is a 9 * 9 grid, I decided to use 2D array to represent the sudoku board. Of course sometimes such natural choice of a data structure could be wrong, but if we follow the rule of ”write code fast, then write fast code” (by PG of course) and naturally supported by Lisp; it should not be very difficult to change the underlying data structure if we get to atleast a reasonable approach initially to solve the problem at hand. Sudoku ConceptsWhen I am bored and naturally procrastinating, I indulge in mindless activities like Sudoku. And I am no expert at solving it with pencil and paper. But over a period of time, we pick up some concepts/terms from the problem without even realizing them. The most important such concept in the Sudoku problem for me was that a square could not have any number that appeared in any other square of the row, column or the box to which the square belonged. We could call these other squares as ’friends’ of the square s; though the quality of not sharing seems hardly friendly! It was then obvious that I would need to find out the squares of a given square s. Since our sudoku is a 2D array, the subscripts (i j) of the array would represent each sudoku square. So given the square in the first column, first row the subscripts of which would be (0 0) what would be the friends of the square? In the process of finding the friends of a square; I ended up with the constant friends. It should be noted that this is a refined (after write fast code stage) code; intially all of what you see as constants were functions. Later while optimizing, it was evident that it would be prudent to compute them at compile time and do lookups via hash tables where keys are the subscripts of a square on the 2D array’ed sudoku. This also leads to other 2 corollary concepts of filled and unfilled square. A filled square is that which has a single value assigned to it. An unfilled square is that which has no value assigned to it yet or has one among many possible values none of which are those assigned to any of its friends. Filling up the input boardWhile solving a given partially filled Sudoku (the most natural case; I treat fully unfilled sudoku as a special case) I decided to first fill every unfilled square with the possible choices for it by not considering the values that any of its friends has. Natuarlly here I consider only those friends which have been filled. At this point, we could end up with a few unfilled squares with only one possible choice. Thus it would make sense to update the board. We update the board till no more updates are possible or a contradiction is found. Here comes the rule/concept/constraints of the Sudoku game into play again. The rule states that every row, every column and every box must be filled with each of the digits 1 to 9 without being repeated. So if a square on a row has 1, the column and the box to which the square belongs cannot have any other square with a value 1. If there is a square with value 1; it means there is a contradiction. Aha, now we can write some code to figure out a contradiciton on a sudoku board. This code checks that for every filled square of the sudoku board, none of its friends has the value that it has. The code for checking contradictions is shown here. (defun contradictions? (board) The fact that a sudoku is solved implies there are no contradicitions on the board or the number of squares counted by contradictions should be 81. The function which checks if the board is solved is shown here. (defun solved? (board) Now you can see how we can update the board. (defun update-board (board) At this stage I choose to call the sudoku board as initialized board. The code which initializes the input board is here. (defun update-board (board) With an initailized board we are in a position to find a solution to the sudoku. But how? We know that on the initialized board, every unfilled square has been assigned valid possible choices. So one of the choice for any such unfilled square has to be true. Otherwise, there is a bug in the code which is assigning incorrect possible values to an unfilled square. Thus we could choose at random an unfilled square and assign it one of the possible choices. If we could find whether this assignment is true or false, we could find a solution! How do we find if the attempted assignment is correct?By now it is clear that if the attempted assignment is correct, it will lead to no contradictions and finally to a solution. Otherwise it will be false and lead to a contradiction, so we drop that from the possible values and assign the next possible value and try again to find a solution. Now, can we make use of the discared values as well? Yes. If an assignment is valid; then the rest of the choices are invalid. But each of this choice does exist as a value in some friend. So we find if there exists only a single friend which has among its possible choices; any of the ones we just discarded. Then obviously that discarded choice is the value for that unfilled friend. Similary for a invalid assignment, we check it the value we just discarded can be assigned to any unfilled friend. The code to use discarded values is shown here. (defun use-discarded (val board min) So what unfilled square do we choose? Naturally we want to find a solution as fast as possible. Hence it makes sense to choose an unfilled square with the minimum number of choices. In the worst case, we will find a solution when the last possible choice AlgorithmThe heart of the algorithm can be now described: Assign the next possible choice to the unfilled square with minimum possible choices till we find a solution. After assigning a value, update the board which returns a new board if no contradictions are found.For both valid and invalid assignments, make use of discared values. All this is captured in a function called as try. (defun try (board) Using the cl-utilitiesI use this package in order to copy the 2D array’ed sudoku board as I need to revert back to the old board in case of invalid assignments. Writing fast codeAfter writing a first version of the sudoku solver, I used the time macros and sbcl deterministic profiler as explainedhere. The most important changes made were the conversion to constants of functions dealing with finding friends. That resulted in friends as a hash table with the key being the subscripts for each square of the 2D Sudoku. Some test runsI used the following as samples from Web Sudoku. Easy Sudoku* (setf easy #2A( Medium Sudoku* (setf medium #2A( Hard Sudoku* (setf hard #2A Evil Sudoku* (setf evil #2A( Empty Sudoku* (setf empty #2A( As expected, the empty sudoku got solved in 0.117 seconds. This code seems to have a reasonable performance without any compiler optimization declarations. The entire code can be found here. At the end of the file is code for using sbcl profiler which has been commented. If you test this on SBCL, you can use this profiler or use the profiler available on your lisp implementation. ObservationsThis code is a great fit for using the non deterministic choose and fail operators along with continuations so that I will not have to maintain the copies of the board. I will try updating this code using PG’s macros that add continuations and non-deterministic opeators to CL. That will make the code only more elegant (and may be slower). But all this can be surely concluded only after writing that code!
Further I have not done the algorithmic analysis. Here the candiate would be the try function and as it is recursive, I would have to use recurrence relations. Ideally the path should have been writing a solution using continuations and choose, fail operators and then move to the solution above based upon profiling results! I will update the post when I follow up on the above observations. Feel free to try to solve a sudoku with this code and kindly let me know in case of any comments/suggestions.
0 Comments
The primary purpose of learning is to acquire a new skill. Learning itself is a skill that is hard to master. So when you try to acquire a skill that is hard in itself, your task has just become harder. I am not talking about things that you do not want to learn. Even easy to acquire skills are hard to do so if you are not inclined. I am talking about learning in the context of acquiring a skill so that you become proficient at it or even better: master it. But why is learning hard and why is it that it is even harder to learn something that is hard? When do we exactly realize that learning anything hard is hard? I think we realize that learning is hard when we become adults and take up work. At that point of time we are all supposed to acquire new skills all by ourselves. But most of us till we begin work, are learning even without realizing that it is difficult. Why? Because we are learning at school, college where our primary responsibility is to learn, though most education systems can even hardly claim that to be their primary motive. So there we are, the education system provides us with the learning support system. What does this system provide you?Everything basically. From books to teachers to lectures to peers to evaluations. Everything is set in stone for you. You just have to follow the route. So what this system does is makes it easy for you to learn new skills. But what does it take away from you? The process of learning itself! And I think that is a big take away. Years and years of habit of using ready made systems to learn new skills would I think subconciously condition you to assume such systems would be in place for you always. And the absence of such systems when you being your career or take up work makes learning hard without us even realizing it. The only such system then that you have at your disposal is you, hardly a comforting idea. (I hardly consider training departments at any workplace to be comparable to schools, colleges; so you cannot rely on them as support systems!) So by the time we have grown up to work we learn to read, write, do math and much more, but we hardly ever learn to learn unless and until you were fortunate enough to have met some enlightened soul who has imparted the gospel of learning. Let us try to verify with examples if all this is true. Take any hard subject that you learnt at school. For example, Calculus is something that most find hard. Even with the learning system in place, we find it hard. So how harder would it be if you were left all alone to learn Calculus? How would you even figure out what books to learn from, who are the good teachers of the subject that you could turn to and how to even verify that you have become good at it? This is an example from within the system. Replace the subject Calculus with your favorite(?) hard subject and the results should be the same. An example from outside the system that you would identify with is making presentations. Most of us at work have come across situations where we have to make presentations. What if it is an integral part of your work? So you would have to acquire that skill. Sounds hard doesnt it? It is. No wonder you may find most of your presentations suck (if you are honest to yourself). Thus now we have come halfway. We know that till we take up work, we are conditioned to assume that readymade systems are in place to help us learn a new skill, which is hardly if at all the truth. Thus when we encounter situations after taking up work, we come unstuck due to two reasons: earlier, we had only one job and that was to learn; and now with work, we have two jobs - one is to work and the other is to learn. Unfortunately we are found wanting in both and ironically the reason is the same ”lack of experience”. I could easily sense this when I began work and I had to learn quite a few things on my own (if I wanted to be good at what I did). And that when you learn on your own, you have to build that support system which was there for you. You have to decide how much to learn, what material to learn from (books, tutorials and they hardly come good); getting hold of experts to have a word with them (again experts are rare and to have a word with them is even more rare!). So the point is it is an extremely difficult process. And when faced with difficulties, only focus can help you stay afloat and sail through.
But focus does one other thing that is very hard otherwise: it tends to provide you with the energy and motivation to do the thing that you are trying to learn. And we all know that learning by doing is one of the best ways to learn, but hardly ever get to it. When you are focused, doing will happen automatically. Doing is the most important supplement that learning needs and focus provides it. Focus also forces you to review your learning and that is the way you improve. Thus focus works like a nourishment, an energy provider without which you cannot ’really’ learn. So if you are focused enough you will end up becoming proficient at both calculus and making presenations. You will not be deterred when you stumble, you will persist, you will solve a lot of calculus problems, you will make a lot of presentations. You will continually review how you fare (or self evaluate, again a part of the learning system at school) and finally become proficient. The best part about self learning is that the more skills you acquire via this route, the better you become at the skill of learning itself. Eventually, I realized that learning new things on my own was not that difficult as long as I was Focussed, kept doing it and had a regular feedback loop. You might find the same. Along the way you might start enjoying the process of learning itself and would look forward to acquire new skills alinged with both your personal taste and professional demands.’Stay Focused, Keep Learning’ now seems to make sense. |
MeI am a 3D graphics software engineer. Archives
December 2011
Categories
All
|