Tag Archives: programming

Blog, Examples

My Sudoku Program

1 Comment

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.

Blog, Examples

Sorting Algorithms

2 Comments

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

Blog

So You Want to Program? Lets Get Started!

3 Comments

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.