Example Sudoku Board

My Sudoku Program

Earlier this week, I was able to write a script that solves the popular Sudoku game. It was a fun experience because along the way I learned about a new way to implement the backtracking algorithm on exact cover problems.

Say we have a set of items. They could be practically anything, but for the sake of understanding lets think of something specific, like school supplies. In particular lets say that school is starting back and you have a checklist of things you need to buy:

  • a pencil
  • a pen
  • a notebook
  • a spiral tablet
  • a ruler
  • a calculator
  • a lamp
  • a bookbag (or knapsack as I just learned people call them)
  • and some paper

Suppose also that as you’re shopping for these items you also see that stores sell the items as collections. In order to spend less money, you think it may be best to buy the items in collections instead of individually. Say these collections are:

  • a pencil, a notebook and a ruler
  • a pen, a calculator and a bookbag
  • a spiral tablet a lamp and some paper

The exact cover problem is a very important problem in computer science because many other problems can be described as problems of exact cover. Because the problem is in general pretty difficult to solve most strategies for solving these problems still generally take a long amount of time to solve. A common technique for solving these problems is called backtracking. This is basically a trial and error way of solving the problem. We try to construct a solution to the problem, and each time we realize our (partial) solution will not work, we realize the error, backup by eliminating part of the current solution and try to solve the problem by constructing another solution. This is basically how the backtracking procedure works. The main caveat to it is that we need to keep track of the partial solutions we have already tried so that we do not continuously retry the same solutions over and over again.

Example Sudoku Board
This is an example of a Sudoku board

In particular Sudoku puzzles can be described as exact cover problems. Doing this involves translating the rules of Sudoku into exact cover statements. There are four basic rules of Sudoku that we need to take into consideration.

  • Each cell in the grid must receive a value
  • a value can only appear once in each row
  • a value can only appear once in each column
  • a value can only appear once in each pre-defined 3 by 3 subgrid.

In actuality these statements are joined together and what happens is that each position in the grid we (try to) fill in actually has effects in all four sections. We can set up the Suduko problem as an exact cover problem by noting these effects.

  • If a cell (i, j) in the grid receives the value v, then we also need to note that row i,  column j, and the pre-defined subgrid have also received its proper value.

We can keep track of this by defining a table.

An Exact Cover Representation of a Sudoku Move
This is how we construct the new table from a given Sudoku move.
  • The first 81 (81 = 9*9) columns in the table will answer the question of does row i, column j have anything in that position. This will tell us whether the cell is empty or not, but will not tell us the value in the cell.
  • The next 81 columns in the table will answer the question of does row i (of the Sudoku grid) have the value v in it yet.
  • The next 81 columns in the table will answer the question of does column j (of the Sudoku grid) have the value v in it yet.
  • The final 81 columns in the table will answer the question of does the (3×3) subgrid containing (i, j) have the value v in it yet.

Notice that individually these columns do not give us much information about the grid, but because each value we place into the grid also has a precise location, a row, a column, a value and a subgrid we link together these columns of the new table and are able to understand more about the implications of each Sudoku operation. There are 9 possible rows, 9 possible columns and 9 possible values for each move, creating 729 possible moves. For each possible move, we create a row in the new table which links the columns of this new table together as follows:

  • row[i*9+j] = 1
    (this says that cell (i, j) is nonempty)
  • row[81+i*9+v] = 1
    (this says that cell row i has value v)
  • row[81*2+j*9+v] = 1
    (this says that column j has value v)
  • row[81*3+(Math.floor(i/3)*3+Math.floor(j/3))*9+v] = 1
    (this says that the 3 x 3 subgrid of (i, j) has value v)

Our goal is to choose a set of moves that fills in the grid. In the exact cover representation of the problem, this means we need to select a set of rows of the new table such that each column of the new table has exactly one 1 in our solution.

In my script I solve this problem using backtracking and the dancing links representation of this exact cover problem. The way dancing links works is that the exact cover version of this problem is translated from being a simple table to a graphical one where each cell becomes a node with pointers to the rows above and below it and the columns to the left and to the right of it. There is also a header row of column headers which contain information about that column, particularly the column number and the number of cells in that column that can cover it (basically the number of 1′s in the table form of the exact cover version of the problem). There is also a head node which points to the first column.

Once the graph version of the matrix is set up, the algorithm recursively tries to select a column and then a row in that column. Once these values have been chosen it tries to solve the new version of the problem with fewer cells remaining. If this is possible then it continues, if not then it goes back and chooses another row or another column and row.

I hope that was an understandable overview of the procedures I used to implement this algorithm. Otherwise I hope you enjoy the script and use it freely to help with your Sudoku   puzzles.

Sorting Algorithms

I just added a script which executes and gives examples of some basic sorting algorithms. Its accessible at Sorting Algorithms

Right now, the algorithms consist of BubbleSort, InsertionSort, MergeSort and SelectionSort.

BubbleSort works by comparing items that are next to one another. If the items are not in proper order, they are swapped. The process continues until we pass through the list without making a swap.

InsertionSort divides an array into two parts, a sorted part and an unsorted part. In each iteration, a new element is compared to all the elements of the sorted part of the array to find where it belongs in this subarray. The algorithm terminates when all elements have been inserted into the sorted part of the array.

MergeSort is based on the divide and conquer algorithm. It works by calling itself (the function mergesort) on two smaller arrays: the elements in the first half of the array, and the elements in the second half of the array.

QuickSort is another divide and conquer algorithm. It is based on first choosing a pivot element (we choose the middle element, but it can be any element) and ensuring that all elements that are less than the pivot element are to the left of it in the array, and all elements greater than the pivot element are to the right in the array. Then the quicksort algorithm is recursively called on each part of the array.

SelectionSort repeatedly finds the minimal value in the list and places it in the first (remaining) position in the (unsorted) array.

http://www.learninglover.com/examples.php?id=9

So You Want to Program? Lets Get Started!

I can still remember when I first tool Algebra II. This was a class where it seemed like every week we were learning a new formula or law or procedure, and it was so easy to confuse the law of sines with the law of cosines or forget a step in a procedure and leave yourself at the mercy of the teacher as to how much credit you will receive. I remember making so many mistakes on the homework assignments and being frustrated with the whole process. At the same time, I had just convinced my mother to buy me a TI-81 calculator like all the other kids in my class. THe big thing then was using calculators to play games, but when I learned that I could make the calculator do these complicated procedures for me, it changed my life.

Maybe your motivations for wanting to program are different from mine. Maybe you’ve realized the extra dimension that a programming language will give to an accountant’s resume or a lawyer’s resume. Maybe you have an idea that you think is too good to share so you’d rather work on it yourself. Or maybe you just want to keep busy at work instead of looking at youtube and facebook all day at work. Whatever your reason, hopefully this writeup can help.

One of the first questions you need to answer is what language you want to learn. Different languages have different properties, so you want to know what you’re getting into. For example, if you plan to write programs to be part of a web page, C++ is probably not a good option because its programs are executable files which cannot be put into a web page. If you were to ask my opinion on a first language to learn in this day and age, I’d recommend JavaScript for a few reasons:

  • Its a simple language (when compared to C++ or Java for example), but it can still do some powerful things.
  • Its syntax (the rules of the language) is very similar to Java and C++, so those languages can become next steps after gaining an understanding of JavaScript. It also connects to other languages like Ajax and PHP, which can also become next steps.
  • It is can be interpreted by almost any browser. One of the biggest drawbacks to people learning programming or a programming language is the first step of finding the compiler/interpreter. With JavaScript all you need is the browser you’re currently using.

Other languages have their own benefits, so don’t get too caught up if you’d rather start with a language other than JavaScript. I don’t mean to discourage any options. 

My plan over the next few weeks is to go over a few concepts of programming in some popular languages.

The first program one generally writes in a new language is called the “Hello, world!” program. If you think of this programming language as a new part of you, then the “Hello, world!” program is introducing this new part of you to the world. From a programmers prospective, we use it to understand the basic structure of a program in this new language – ala it introduces the programming language to us.

There are certain things to try to take notice of in a “Hello, world!” program:

  • The case of the alphabetic characters. One of the biggest programming errors for beginners is understanding case sensitivity – i.e. that ‘int’ and ‘Int’ can be interpreted totally differently.
  • The location of non-alphanumeric characters. Many languages use parenthesis, semicolons, brackets, etc., and gaining an understanding of how to use these symbols is important.
  • How to output text. By definition, this program outputs “Hello, world!”, so understanding how this is done is important.
  • What does each line do? These programs are generally pretty short, so we should gain some understanding of the important parts of a program in this new language.

Having stated that, lets introduce a few “Hello, world!” programs in different languages.

JavaScript

<html> 
<body>
<script type="text/javascript">
document.write("<p>Hello, world!</p>");
</script>
</body>
</html> 

JavaScript programs are embedded inside an HTML web page. This is why the first two lines of the JavaScript look like an HTML file – because thats exactly what it is. The third line tells the browser to expect JavaScript code for the next few lines (until the ‘</script>’ tag). The function document.write() writes text to the web page. In this case, that text is “Hello, world!”. Notice that the fourth line ends in a ‘;’. Just like we use a period to end sentences in English, we need a way to end statements in JavaScript. The ‘;’ character does this. We then close the script with ‘</script>’ tag. Then we use the html again to reach the end of the file. 

I encourage users to try this program out. To do so, copy the above JavaScript and  paste it in a text editor and save it as “hello.htm”. Then open the file with Internet Explorer (my favorite browser for editing JavaScript), Chrome, Firefox, or whatever web browser you currently use. You should see something similar to: 

 C++

#include <iostream.h>

void main()
{
     cout << "Hello, world!";
     return;
}

Our C++ program starts with an ‘#include’ statement. This tells the compiler that our program will need resources that are included in another file (in this case, ‘iostream.h’ – we use this file for basic input and output). Notice that the ‘iostream.h’ file is included inside ‘<>’ brackets. Take note of that now. After that, we see the main function. Every C++ program must have a main function. This is where the program begins. Notice the statement ‘void’ in front of the word ‘main’. This says that the ‘return’ statement will not have a value after it (we could have instead said ‘int main()’, in which case we would need to have put ‘return 0;’). Notice next the (). This tells the compiler that main is a function (of no arguments). Then there is a ‘{‘ which shows that we are starting the main function. To output the “Hello, world!” statement, we use the statement ‘cout’ followed by ‘ << ‘. This is standard output syntax. Notice again that the statement is followed by a ‘;’. Like JavaScript, every statement in C++ must be followed by a ‘;’. Finally, the program closes with a ‘}’ closing the earlier ‘{‘.

If you would like to compile this C++ program, you’ll need a C++ compiler. Downloading a C++ compiler depends a lot on your operating system and your preferences. You can go to http://en.wikipedia.org/wiki/List_of_compilers to select a proper compiler.

Java

public class HelloWorld
{
     public static void main(String [] args)
     {
          System.out.print("Hello, world!");
     }
}

Java is an object oriented programming language, where everything must be inside an object – in this case the object is the class ‘HelloWorld’. The ‘{‘ indicates the beginning of the class. Notice that Java (like C++) has a main function, but it also has the keywords ‘public’ and ‘static’ in front of it. Every Java application must have a main function. Inside the parenthesis after the main function is the statement “String [] args”. This is the input to the program from the command line. We will discuss that more later. Then after the curly bracket ‘{‘, we have a call to the function ‘System.out.print()’. This is the basic output statement statement in Java. It writes things to the command line. What is passed to this function is the string “Hello, world!”. Following that, we have a semicolon to end the statement, a curly bracket to close the main function and a curly bracket to close the class HelloWorld.

Again, if you would like to compile this Java program, you’ll need a Java compiler. I recommend Eclipse, but getting a Java compiler will depend on your operating system again. The same link as above (http://en.wikipedia.org/wiki/List_of_compilers) also lists a selection of Java compilers.

Until next time, I would recommend going to a few sites that have helped me out.

  • One of my favorites is http://www.w3schools.com. They have a pretty good introduction to JavaScript as well as some other languages.
  • I also love the “Programming with C++” and “Programming with Java” books by Schaum’s outlines (actually I recommend just about everything they put out. Its quality material for a good price).
  • I recommend looking at source code and making modifications to it to see how the changes affect the output.

Next time, I’ll try to go over variable types and user input, which make programs interactive. 

What Can I Do to Help End the Recession?

I was reading through am article at UrbanCusp on Occupy Wall Street and it really got me to thinking about myself and my involvement in this movement. I’ve never attended an ‘occupy’ rally and rarely read the reports. I did attend the “One Nation” rally last year as well as the Jon Stewart/Stephen Colbert “Rally to Restore Sanity”, but does that really mean anything?

In the midst of this recession, I have a few friends that are unemployed and others who feel underemployed. A large part of me wonders what I should be doing to help with this? Ultimately, I guess I would like to help end the recession, but how? And to what end? The OWS movement shines light on the growing wealth disparities between the different economic classes in America. There is also a large wealth gap between White family income and Black family income. These are problems I grew up learning about, and, honestly, feeling helpless in terms of doing something about it, and a large part of me wonders what I can do about it. A large part of me feels helpless, like there’s not much that I can do to help drop the unemployment rate or increase property values or help to solve a ton of other problems that America is currently facing.

But as always, I guess there’s a little voice in my head telling me that maybe I can’t end poverty in itself, but I can do things to help those I come in contact with to help find jobs or to become better equipped on the job search, or to just keep their heads up during these tough times. I mean, that’s partially why I created this site.

I don’t like hearing people, particularly my friends, say that they are limited by what their teacher/book/class is teaching them. Some of my friends are finished with school and are not interested in going back to take classes (or paying more money), but would still like to learn new material. We live in a world where information and new material is only a click away. So while a more ‘formal’ means to building your resume may be through classes and certifications, another comes through simply taking initiative and being aggressive and willing to try new things and to learn new things.

I’ve found that there’s a certain feeling that comes along with learning something new. I don’t know about you, but suddenly I feel like I can take on the world. Doors that we didn’t know existed are suddenly opened and avenues that once seemed shut out suddenly become open.

But a big part of the ‘learning game’ is understand that you are not limited by your teacher or your book. In the process of learning, especially learning online, you’ll come across many sources that you do not understand. Maybe its your first source, maybe its your first five or first 50 sources, but the key is to understand that its a process and never lose hope. All you need is one source to learn new material. And I also stress not to be afraid to ask questions – whether these are questions to yourself, questions to an informed friend, or just posting them at a message board. One of my largest frustrations with the teacher / student model for learning is that some teachers shun questions, which makes students feel unintelligent for asking questions. But one of my favorite musical lyrics goes “even the genius asks his questions”, which I constantly use to inspire me throughout this learning process.

But that’s enough talking on my end, my question is what are you going to do to help end the recession?

 

The Degrees of Consciousness of a Black Nerd

The great W.E.B. Du Bois may have underestimated things a little with his theory on double consciousness that he proposed in “Souls of Black Folk” – especially when it comes to Black nerds. There’s definitely the double-consciousness that of being both Black and American and loving a country that allows many of her children to dwell in the slums without caring much about them. But there’s also a treatment in America in general and Black America in specific that makes nerds feel like outcasts, like we’re weird or abnormal. In relationships, we’re stereotypically thought of as weak, or as the counter to the macho – testosterone images seen in movies. In school, the supposed sanctuary of a nerd, we’re often ignored – until mid-terms and finals when people beg for us to help them pass. These are just some things that come to mind as I sip my morning coffee, but I know that others can think of more.

And what’s more is that we endure much of this in silence. We’ve learned to simply smile when people compare us to Urkel or Carlton. Many of us have learned to ‘look the part’ as we walk down the streets. We think to ourselves, “Don’t think too much about that problem you were working on earlier today, you’ll look like you’re talking to yourself.” or “No matter how excited you are about finishing that program, don’t talk about it in the bar cause you’ll just get cold stares and confused faces”.

But is that really how we should respond to this? Should we hide from out intellect or our habits? I find that hard to do, bordering on the impossible. One thing is that I’ve been this way for so long that subconsciously I always find myself acting this way, analyzing patterns in things I see, looking for connections. But the more important thing is why should I care if you care about it? If it relaxes me, then why should I stop doing it? Just to please somebody (some people) who probably don’t like me anyway?

This brings up an alternative approach which is to just stop hanging around these people? But how can I disconnect myself from my community that practically raised me? Who else can I connect with about the plights of being Black in America and the challenges we still face? I’m not naive enough to think that I could just walk into another community and and share these struggles. This approach leaves the nerds in a life of isolation because nobody quite understands our struggle.

Unfortunately, I see countless examples of Black nerds taking these two approaches – either deciding that fitting in is more important, and thus living this secret life as a nerd, or simply deciding that they’d be better off outside of the harassment of our community. So the next time you see a Black nerd, try to understand that he’s struggling with a lot more than just some number crunching.

User Generated Flash Cards

When I originally started LEARNINGlover.com, I had the idea in my mind that I would utilize my skills in programming and mathematics to help others. While this remains an important goal of mine, I remain curious about how I can use this site in other ways. One thought that has occurred to me for a while is how do I expect to handle users who want to learn things that are not currently offered by the site? I do plan to regularly add sections, data and programs to the site, but what about people who don’t want to wait, or who don’t want to learn the things that I have been studying? My thought process on this is that I’d like to provide users with tools that I believe can be used to help learn, in particular to help teach yourself, just about anything – as long as you have a good source. We live in an age where information is everywhere. With just the click of a mouse we have the power to download an online textbook, read journal articles, learn a new language and a host of other things – if we know how to use this information correctly.

The concept of flash cards has been around much longer than I have. That said, I don’t see flash cards used outside the realm of vocabulary often. When I began studying theoretical mathematics, I found the number of vocabulary words offered in each class intimidating. So by instinct, I just used flash cards to learn these words. The class, though, also consisted of theorems, lemmas, proofs, corollaries, etc that do not fit into the vocabulary ‘box’ that I had seen flash cards used for. Nonetheless, I needed to study these concepts if I was going to do well in my classes.

What I found is that in my notes, not only are the notes themselves important, but there is also a question – ‘Why is this line that I just underlined important?’ Or phrased differently, ‘What question was this line written to answer?’ Take for example the following note which may come up in a class on Graph Theory:

The complexity of Kruskal’s algorithm is O(E log V).

This is certainly an important fact, as we are interested in how well algorithms perform and would like to compare these complexities. But once I have underlined it in my notes, I want a way to remember it. I know the question that will come to me during an exam or in real life practice is:

What is the complexity of Kruskal’s algorithm?

So I create a flash card with this question and answer pair.

I don’t have any ‘rules’ for creating these questions, but here are some things that come to mind:

  1. In general I try to make my questions open-ended (not yes/no questions).
  2. For definitions, I generally ask “What is the definition of <insert word>”.
  3. Many times, things such as theorems, lemmas, or corollaries will connect two things together (either in one direction or two), so I ask questions like “What is the relationship between <insert concept 1> and <insert concept 2>?” for these.
  4. Other times, theorems simply state facts (like the example above), or link a well known function (complexity) to a particular object (Kruskal’s algorithm). For these I form questions like “What is the value of <insert function> on <insert object>?”
Of course I don’t live by these rules and feel free to change or add to them as you like. I have used similar concepts on reading and understanding journal papers as well as some philosophy books. I hope this helps you as much as it has helped me.