Quote of the Day

The latest advise from the Advisory Council of Rabbis in Israel: "During war times it is alright for the civilians to be killed."

Interesting coincidence that this decision also acquits Hitler. Good job Rabbis! I guess the "sweet" smell of Genocide (and the sweet thought of erasing Arabic smells around Israel) finally overcame the choice of logical decision making...

Youtube

The last few days, I had been working on uploading some videos to youtube. Since I had to do a bit of a work on some of the videos, here are two helpful tips for you.

1. Conversion: I suggest you to convert the video to avi (divx) version before uploading the video. If you upload in mpg version, many times Youtube cause resolution and synchronization problems. The best tool I had used on that was Super video editing tool. Conversion does not take too much time. I suggest you to select divx settings at 320x240 resolution as Youtube suggests. You can preserve an acceptable level of quality this way.

2. Editing: To fit the limits or to remove whatever you want to cut from the videos, the best tool that I can suggest is (Advanced) Avi Splitter. Using is very easy and quick. If you want to mask some parts use Virtual Dub. For advanced editing, Blaze Media Pro is a good tool.

Three Orders from Israel

I am really tired of the hatred between the Arabs and the Jews. I guess they must have really enjoyed this suffering and pain. Here is a nice memo dedicated to Israel.

1. The most recent order by Israel: "I ask all the civilians in the southern part of Lebanon to leave their homes!"

2. The next order: "I ask all the civilians around my country to leave their homes. These countries include, Palestine, Lebanon, Syria, Iraq, Kuwait, Saudi Arabia, Jordan, Egypt, etc. Although, Iran is not exactly around my country, I also ask them to leave their homes, since they will soon be my neighbors!"

3. Final order: "I ask all the civilians in the world to leave their homes for their own sake. Due to recent achievements of Israel, and the already happened arrival of the final Prophet, the citizens of the promised land is about to be awarded the final promise of apocalypse!"

Word of the Dai

"Is it really necessary to kill at least 100,000 people, to get rid of a single Dictator?"

Dr. Mohamed ElBaradei, the Director General of the International Atomic Energy Agency.


UPDATE: Response from Sheriff of the World

"Yes. I, the ancestor of Stalin, am ready to do whatever it takes to make the world taste and feel my happiness. Mine and only mine..."

Gunun yazisi - Melih Asik'tan

Kalite dorukta!..

Meclis Başkanı Arınç, Moskova'da Lenin'in mozolesi önünde yaptığı espriyle ne kadar yüksek kalibrede bir devlet adamı olduğunu bir kez daha gösterdi:
"Lenin'i ölü olarak görmek çok güzel."

Hakkını yemeyelim, diğer AKP'li siyasiler de o ölçüde esprili ve nitelikli kişiler!..

Maliye Bakanı hayali ihracattan vergi kaçakçılığına kadar... Maliyenin her alanında deneyim ve hüner sahibi olmasa, bugün bakanlık koltuğu yerine mali suçlu olarak hapiste olmaz mıydı?..
Kültür Bakanı icraat sırasında uyuyabilen ve müzelerin soyulmasını görmezden gelebilen bir zekâ...

Milli Eğitim Bakanı imam hatip mezunlarını üniverseteye sokma konusunda başarıya doğru ilerliyor. Bunu başarınca diğer konulara da sıra gelecek...

Sağlık Bakanı, Bayındırlık Bakanı, Tarım Bakanı... Hepsi ayrı değer... Danışmanlar da öyle... Cüneyd Bey fındık ve pot kırma ustası... Basın danışmanı Beki'nin kamuoyuna yalan söylediğini dün bizzat Başbakan açıkladı...

Bu kadronun lideri Başbakanımız ise şu anda dünya siyasetinde bir yıldız gibi parlıyor... Özellikle itibarlı dostlarıyla ilgi çekiyor; Afgan mücahidi Gülbeddin Hikmetyar, Hamas lideri Halit Meşal, terör finansörü Yasin El Kadı bu muteber isimlerden birkaçı...

Danışmanı Zapsu'nun onu Washington'da "Bu adamı kanalizasyona süpürmeyin" diye savunmasından mutluluk duyuyor. Uluslararası görüşmelerde pot kırması ayağına basılarak önleniyor...

Böylesi bir kalite ve kadro zenginliği yaşıyor Türkiye...

Başbakan El Kadı'ya kefilmiş.
Fiskobirlik'e de kefil olsa da, perişan fındık üreticinin emeği çarçur olmasa!
Gülhan Elmas

Yabancıya satış...

Efendim gurbetçimiz Avrupa'da herhangi bir ülkeden ev, dükkân, apartman almıyor mu? Elbet elin yabancısı da gelip istediği yerden ev, arsa, villa, yalı alabilmeli. Ne var bunda? Üstelik yabancı sermayeye de ihtiyacımız var... Para gelsin... Yüzeysel bakınca bu mantık doğru gibi görünüyor. Acaba olay bu kadar basit mi?...

Erciyes Üniversitesi'nde yabancılara toprak satışına ilişkin bir proje yürütüldü, ayrıntılı çalışma yapıldı, bir rapor hazırlandı. Proje sorumlusu Yard. Doç. Ayşe Odman Boztosun'la konuştuk dün...

Yabancılara toprak ve emlak satışıyla ilgili olarak gözden kaçan veya kaçırılan noktalara dikkati çeken Boztosun dedi ki:

- Köşe yazarları daha çok yabancı kişilerin Türkiye'de edindikleri taşınmazlara odaklanıyor. Böylece Türkiye'de en fazla taşınmaz edinenler Yunan ve Suriyeliler, tatil yörelerinde de Almanlar ve İngilizler gibi görünüyor. Ancak 2003 - 2005 yılları arasında, 2 yıl boyunca, eski yasa Anayasa Mahkemesi tarafından iptal edilene kadar, yabancı ticaret şirketleri, Türkiye'de sınırsız şekilde taşınmaz edindi... Ne kadar? Bilinmiyor. Bu bilgi bugün maalesef Tapu ve Kadastro Genel Müdürlüğü'nde bile mevcut değil...

- Bugünkü durumda tam bir denetim var mı?

- Maalesef hayır... Kişilerle ilgli mütekabiliyet esası gibi sınırlamalar var, ama yabancılar Türkiye'de şirket kurarak tıpkı bir Türk şirketi gibi istediği kadar, istediği yerde taşınmaz edinebilir...

- Bir yabancı ülke kendi işadamlarına Türkiye'de ortak şirket kurdurdu, diyelim ki sınır bölgesinden yüzlerce dönüm arazi aldırdı. Bundan bizim haberimiz olmaz mı?

- Olmaz... Çünkü bu konuda bir denetim yok.

- Dış ülkelerde bu konuda tam bir serbestlik var mı?

- İsviçre ve Danimarka gibi ülkelerde ikâmet etmiyorsanız toprak ve emlak alamazsınız. Birçok ülke bu kuralı uygular. Türkiye'deki kadar geniş serbestlik ve denetimsizliğin benzerini bulmak zordur...

AB siyasetçilerinden Lagendijk, "Türkiye'de daha çok bölgesel özerklik gerekiyor" demiş.
Ülkenizi bölün demeyecek kadar nazik bir adam...
Haldun Ertem

Interesting Genetical/Philological Research - Are the Italians come from the Turks?

Translation of possibly another translation - so as a warning, don't forget that mistakes are also a part of the life - do not hesitate to search for the real truth if you think what given below is not.

Italians, who consider the Turks as barbarians, are in shock. Lately, it has been proven that the Italians' DNA matches the Turks' DNA with 97%. Now, it is also claimed that the alphabet of the Etrusks, who are considered to be the ancestors of the Italians, is of Turkish origin.

The first thing that comes to the mind of anyone, who is familiar with both the Italians and the Turks, is how the Turks and Italians are close to each other both physically and characteristically. It is interesting that the people of both of these Mediterrenanen countries are like friends even if they haven't met each other. In the recent years, Italian science community has started discussions to find the origins of their ancestors, or whether they are Turks or not...

What lies in the middle of those discussions is the clan/tribe of Etrusks, who are considered as part of Pre-Turks. Etrusks had established the oldest culture in Italy. It is known that the Etrusks have come from the Austrian Alpines to Siena, Napoli, and Rome in 1000 BC. After they established a glorious civilization, they had been erased from the history scene in 300 BC. The region from Florence to Napoli has been known as Etruria. Also, the people who are living in this region call themselves as Etrusk. Since the Etrusks have been considered as a mysterious tribe, there have been neverending discussions regarding their origins.

The first written document belonging to the Etrusks was found in 1780. But, what ethnicality the Etrusks have represented had been an unknown despite the archeological findings. Because, no Western researcher has been able to decipher the Etrusk writings, which were written with characters highly similar to those in Latin alphabet. Researchers from the Toscana University, who are known to do detailed researches on Etrusks, investigated the DNA of Etrusks by taking samples from the skeletons found in Etruskian graves. They have compared the samples to many races around the world. And, interestingly (but naturally), the samples had shown 97% match to the DNAs of the Turks. Italians, who have called the Turks as barbarians for centuries, who have created the slogan "Alas (or oh mama), the Turks are coming!", have been shocked by these findings. This topic has started big discussions in the Italian science community.

Now, we give the microphone to ethnologist and art-historian Haluk Tarcan, who has also claimed that the Italians come from the Turks using ethnological and archeological findings as proofs.

2nd part is coming soon...

World Basketball Championship - a small analysis of the Turkish National team

Turkish National team has always been a part of highly controversial decisions and the resulting discussions in the last few years. This year is no different. I have a couple of words (in Turkish) for some who put their personal interests above the national interest.

Dogruyu soylemek gerekirse milli takima yillarca hizmet vermis olan, ve buna ragmen her turlu basarisizlikta kinci, cikarci, ve Turk basketbolunu batiran isimler tarafindan suclanan Hidayet ve Mehmet'in (umarim son sampiyonadan sonraki Dogan Hakyemez denen kiskirtici, laf tasiyici, ve ara bozucu sahsin aciklamarina kulaklarinizi tikamamissinizdir), bu kisilerin hala takimin basinda olmasi dolayisiyla takima katilmak istememeleri acaba hic mi akliniza gelmiyor? Eger o takimdan Dogan Hakyemez atilsaydi ve antrenor olarak adam gibi birisi konulsaydi (orada alin teri dokebilecek, sampiyonadan sampiyonaya da olsa gorev yapabilecek bayagi bir isim var) acaba Mehmet ve Hidayet gerekli ozveride bulunabilirlermiydi? Bence sagliklari izin veriyorsa kesinlikle.

Ayrica gecen sampiyonada hatirliyorum acik bir sekilde "Federasyonun yalakasi" olan isimler bas sorumlu olarak Mehmet ve Hidayet'i gormuslerdi ve takima bir daha alinmamalari talep edilmisti. Ne oldu da simdi tekrar bu iki isme sarildilar, acaba Federasyonun son yillarda Turk basketboluna indirdigi hancerin etkilerini bir sure daha gizlemek icin mi (tesadufi de olsa basari olursa, basari Turgay Demirel ve Dogan Hakyemez'in olacak, basarisizliktaysa bas sorumlu NBA'li oyuncularin cikardigi huzursuzluk olacak)? Sebep ne olursa olsun bu kisilerin cikip da ortalikta Hidayet ve Mehmet'i vatan hainligiyle suclayip, halki onlara karsi kiskirtmalari hem asagilik bir davranis hem de abesle istigalden ote degil.

Ayrica hala bizden ileride olan Fransiz basketbolunun yasandigi ulkede saygiyla anilan Huseyin gibi bir basketbolcunun milli takima davet edilmemesinden dolayi acaba Turgay Demirel ve Dogan Hakyemez'in yaptigini vatana ihanet olarak gorurmusunuz? Yoksa, belli bir koronun uyesi ve cikarin temsilcisi olarak, bu gercegi gizlemek icin gozunuze uyku gozlugu, kulaginiza kulak tikaci mi takmayi tercih edersiniz?

Ben gecen sampiyonadan sonra beklenenin cok altinda performans ortaya koyduklari icin ilk olarak Hidayet ve Mehmet'i sorumlu gormustum, cunku NBA'li oyuncular olarak her kosulda ustun bir oyun sergilemelerini beklerdim. Ama Mehmet'in performans dusuklugunun sebebi belliydi ve hakli bir sebebi vardi. Hidayet'te psikolojik olarak problemlerden cok kolay etkilenen birisi. Ve gectigimiz milli takimdaki problemler ve gruplasmalar goz onune alinirsa kendini verememesinin sebebi cok rahat ortaya cikar. Ben de onun yerinde olsam problemlerden uzakta kalmak icin milli takima son haftada katilirim, diger oyuncularla iliskilerimin en azda olmasini saglarim, ve sadece verilen gorevi yerine getirip ekstradan hic bir seyle ugrasmam. Bu ne demek oluyor, sagolsun milli takimin basindakiler ve sizin gibiler benim icindeki milli takim sevgisini oldurdu demek oluyor. Ve kesinlikle hak veriyorum.

Umarim taktiginiz gozlugu cikarip baskalarinin olaya bakis acilarini da dikkate alirsiniz. Sonucta bu ne sadece sizin milli takiminiz ne de sadece benim milli takimim.

Dancing Links in Sudoku continued

Source: http://www.setbb.com/sudoku/viewtopic.php?p=6068&mforum=sudoku#6068

You should realize that DLX is not designed for sudoku. It is a generic algorithm to solve Exact Cover problems. In fact, many terms are used for different things in DLX and sudoku.

Column

A simple constraint in sudoku. There are 81 columns for each cell, 81 for 9 digits in 9 sudoku-rows, 81 for 9 digits in 9 sudoku-columns and 81 for 9 digits in 9 sudoku boxes. This creates a total of 324 columns.

Row

A candidate in sudoku. There are 9 candidates in 81 cells, creating 729 rows.

Node

An connection between a row to a column. Each row has 4 nodes, one for each of the 4 constraints that it links to.

Example

Take candidate R2C7D6.

It is represented by Row[(2-1)*81+(7-1)*9+(6-1)]
It has a Node for the column representing the cell: [(2-1)*9+(7-1)]
It has a Node for the column representing digit 6 in sudoku-row 2: [81+(2-1)*9+(6-1)]
It has a Node for the column representing digit 6 in sudoku-column 7: [162+(7-1)*9+(6-1)]
It has a Node for the column representing digit 6 in sudoku-box 3: [243+(3-1)*9+(6-1)]

When setting up a DLX grid, make sure you can address the nodes from the rows. I usually define a FirstNode property in the Row object.

729 Rows with 4 Nodes each creates 2916 Nodes in total.
324 Columns each have 9 Nodes attached.

Classes

If you are not familiar with object oriented programming, the following part may be difficult to understand.

Code:

class Node { Node Up; Node Down; Node Left; Node Right; Header Head; } class Header : Node { int Size; }

Initially, a Header has no detail nodes connected to it. You should initialize a Header like this:

Code:

this.Up = this.Down = this.Head = this; this.Size = 0;

When detail nodes are initialized, link them to their header like this:

Code:

this.Down = this.Head.Down; this.Up = this.Head; this.Head.Down.Up = this; this.Head.Down = this; this.Head.Size++;

Link-Unlink

Each column has a header node. In an object-oriented language, the Header class is inherited from the Node class. You can also implement properties like IsHeader in the Node class.

Nodes are connected to the column header using a double linked list. Each node has Up and Down properties to the adjacent nodes. The column header node is part of both lists.

All nodes belonging to the same Row are connected with Left and Right properties. Most implementations do not use Row headers. The last Node of the row links back to the first. These left-right lists are static. They will not change after the initial setup.

To unlink a node, simply connect the 2 adjacent nodes to each other with the following operation:

Code:

this.Up.Down = this.Down; this.Down.Up = this.Up; this.Head.Size--;

This removes a node from the list. Notice that the Header.Size property is also decremented.

The powerful thing about DLX is that this operation can easily be reversed. The node still 'knows' where it was located in the list. The following operation restores the original links:

Code:

this.Up.Down = this; this.Down.Up = this; this.Head.Size++;

This is only true when we can be assured that the list is in the same state it was after the node was unlinked. The recursive DLX algorithm takes care of this.

Column Headers

Header nodes use the Left and Right properties in a slightly different way. All headers are linked to each other in a doubly linked list using the Left and Right properties.

A Root will be used as the starting point for these Header lists. Initialize the Root like this:

Code:

this.Left = this.Right = this;

Additional Headers are connected to the Root like this:

Code:

this.Left = Root; this.Right = Root.Right; Root.Right.Left = this; Root.Right = this;

In DLX, you will need to remove selected headers from this list. To do this, use the following operation:

Code:

this.Right.Left = this.Left; this.Left.Right = this.Right;

Now doesn't that look familiar? We can undo this operation like this:

Code:

this.Right.Left = this; this.Left.Right = this;

Now we have everything that we need to implement DLX.

Description of the DLX Algorithm as required for Sudoku

Initialize the grid. Use the definitions as specified. Create the Root header. Create all column headers. Save them in an array for easy access. Create all Rows, and save them in an array too. I prefer a multi dimensional array for the rows. Create the Nodes for each Row. Place the first node in the rows array, and make sure they are properly connected, sideways and to the 4 column headers.

Process the clues. You can do this with existing methods. When a cell has a clue value of 1, it cannot be candidates 2 through 9. Use the unlink operation to unlink all candidates, except the clue value. You do not need to unlink all 4 nodes. Only unlink the first node (the one that you can access from the rows array). Do not forget to decrement the associated Header.Size.

Start the recursive process.

Take great care in coding this part. Everything you do must be undone in the reversed order. Sometimes switching 2 lines of code can cause error that are very difficult to detect.

Check recursion stop condition

Recursion ends when the Root has no headers attached. At this point, the algorithm has found a solution. You can save this solution at this point in the code.

Code:

if (Root.Right == Root) { // save solution // increment solution counter return; }

Find the best Column Header.

There are various ways to implement this search method. Here is the shortest version:

Code:

Header best = Root.Right; for (Header hd = Root.Right;hd != Root;hd = hd.Right) if (hd.Size < best =" hd;

It this point in the process, you have found the best column header to start with. Now there are 3 options, which are all covered by the same algorithm:

1. Size = 0. You have found a dead end. The algorithm will recurse no further and start backtracking.
2. Size = 1. This will happen at least once for each clue that you have processed. When Size= 1, the process has found a single. If you want to see that the sudoku can be solved with singles only, make sure you do not allow the size of selected columns to be greater than 1.
3. Size > 1. The algorithm tries all the alternatives one by one.

How can these 3 situation be handled by a single method?

Unlink the selected Header from the header list.
Unlink the peer nodes of the nodes linked the selected Header.

Together, we call this a Cover operation. I usually implement this as a method for the Header class, and it goes like this:

Code:

this.Right.Left = this.Left; this.Left.Right = this.Right; for (Node child = this.Down;child != this; child = child.Down) for (Node peer = child.Right; peer != child; peer = peer.Right) { peer.Up.Down = peer.Down; peer.Down.Up = peer.Up; peer.Head.Size--; }

There is also an Uncover operation to reverse it:

Code:

for (Node child = this.Up;child != this; child = child.Up) for (Node peer = child.Left; peer != child; peer = peer.Left) { peer.Up.Down = peer; peer.Down.Up = peer; peer.Head.Size++; } this.Right.Left = this; this.Left.Right = this;

Please notice that even the directions Right/Left and Up/Down are reversed.

After covering a header, the code will try each of the rows linked to the selected column. In case of a size zero column, nothing happens. For other sizes, each of the rows will be selected/deselected in turn.

This is the code to navigate the rows below the column:

Code:

for (Node nd = best.Down;nd != best;nd = nd.Down) { nd.Select(); // save info // recurse nd.Unselect(); }

This is the Select method for the Node class:

Code:

for (Node peer = this.Left;peer != this; peer = peer.Left) peer.Head.Cover();

This is the Unselect method for the Node class, that reverses the Select method.

Code:

for (Node peer = this.Right;peer != this; peer = peer.Right) peer.Head.Uncover();

The final steps in the algorithm are related to the administration.

You need to save the selected rows. The generic DLX algorithm advises to use a stack, but a simple size 81 array will do fine for sudoku. Make sure you give each Node a CellIndex and a Digit property, and prepare a int[] Selected array.

You need a way to stop the algorithm when multiple solutions are found.

The modified main routine is changed to:

Code:

for (Node nd = best.Down;nd != best;nd = nd.Down) { nd.Select(); this.Selected[nd.CellIndex] = nd.Digit; // recurse nd.Unselect(); if (this.SolutionCount > 1) break; }

Dancing Links in Sudoku - source: Wikipedia

In computer science, Dancing Links, commonly known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, brute-force algorithm that finds all solutions to the exact cover problem. Some of the better known exact cover problems include tiling, N-queens and Sudoku.

The name Dancing Links comes from the way the algorithm works, as iterations of the algorithm cause the links to "dance" with partner links so as to resemble an "exquisitely choreographed dance." Knuth credits Hitotumatu and Noshita with having invented the idea in 1979, but it is his paper which has popularized it.

As the remainder of this article discusses the details of an implementation technique for Algorithm X, the reader is strongly encouraged to read the Algorithm X article first.

The idea of DLX is based on the observation that in a circular doubly-linked list of nodes, then

x.left.right ← x.right;
x.right.left ← x.left;

will remove node x from the list, while

x.left.right ← x;
x.right.left ← x;

will restore x's position in the list. This works regardless of the number of elements in the list, even 1.

Knuth observed that a naive implementation of his Algorithm X would spend an inordinate amount of time searching for 1s. When selecting a column, the entire matrix had to be searched for 1s. When selecting a row, an entire column had to be searched for 1s. After selecting a row, that row and a number of columns had to be searched for 1s. To improve this search time from complexity O(n) to O(1), Knuth implemented a sparse matrix where only 1s are stored.

At all times, each node in the matrix will point to the adjacent nodes to the left and right (1s in the same row), above and below (1s in the same column), and the header for its column (described below). Each row and column in the matrix will consist of a circular doubly-linked list of nodes.

Each column will have a special node known as the "column header," which will be included in the column list, and will form a special row ("control row") consisting of all the columns which still exist in the matrix.

Finally, each column header may optionally track the number of nodes in its column, so that locating a column with the lowest number of nodes is of complexity O(n) rather than O(n * m) where n is the number of columns and m is the number of rows.

In Algorithm X, rows and columns are regularly eliminated from and restored to the matrix. Eliminations are determined by selecting a column and a row in that column. If a selected column doesn't have any rows, the current matrix is unsolvable and must be backtracked. When an elimination occurs, the selected row's column, other rows 'belonging' to that column, and other columns to which the selected row 'belongs' are all removed. These columns are removed because they have been filled, and these rows are removed because they conflict with the selected row. To perform the elimination, first remove the selected column's header. Next, for each row where the selected column contains a 1, traverse the row and remove it from other columns (this makes those rows inaccessible and is how conflicts are prevented). Finally, remove each column (other than the selected column, it has already been removed) in which the selected row has a 1 (they have been filled by the selected row). This order ensures that any removed node is removed exactly once and in a predictable order, so it can be backtracked appropriately. If the resulting matrix has no columns, then they have all been filled and the selected rows form the solution.

To backtrack, the above process must be reversed using the second algorithm stated above. A requirement of using that algorithm is that backtracking must be done as an exact reversal of eliminations. Knuth's paper gives a clear picture of these relationships and how the node removal and reinsertion works.

It is also possible to solve one-cover problems in which a particular constraint is optional, but can be satisfied no more than once. DLX accommodates these with primary columns which must be filled and secondary columns which are optional. This alters the algorithm's solution test from a matrix having no columns to a matrix having no primary columns, but doesn't require any further changes. Knuth discusses optional constraints as applied to the N-Queens problem. The chessboard diagonals represent optional constraints, as some diagonals may not be occupied. If a diagonal is occupied, it can only be occupied once.
[edit]

Application to Sudoku

Currently (January 2006), Sudoku is enjoying a surge of popularity amongst programmers and game enthusiasts alike. The following considers the popular 3x3-3x3 (3x3 grid of 3x3 boxes) Sudoku variant. To convert any other variant into an exact cover problem, all that is required is an adjustment of the constraint-column mapping.

The DLX matrix for Sudoku represents every possible move and the constraints those moves must satisfy in any valid solution.

Each row in a DLX matrix represents a possible move, i.e., placing a particular digit in a particular cell. Thus the DLX rows can be labeled , where d, r and c each range from 1 to 9. For example, there is a DLX row <2,5,7> for placing the digit 2 in the cell in row 5 and column 7. As there are 9 possible digits and 9x9=81 possible cells, there are 9x81=729 DLX rows.

Note: Although it is thus possible to place more than one digit in the same cell, constraints will assure that any valid solution has exactly one digit per cell.

Each column in a DLX matrix represents a constraint any valid solution must satisfy. Sudoku has four kinds of constraints:

1. Each cell in a row and column must contain exactly one digit: .
2. Each digit must occur in each row exactly once: .
3. Each digit must occur in each column exactly once: .
4. Each digit must occur in each box exactly once: .

For example, the Type 1 (row-column) constraint <5,7> is that the cell in row 5 and column 7 contains exactly one digit. The column in the DLX matrix for this constraint has a 1 in the DLX rows <1,5,7>, <2,5,7>, ..., <9,5,7>, which correspond to placing the digits 1 through 9 in the cell in row 5 and column 7. (The DLX column has a 0 in every other DLX row.) Since a valid solution will select only one of these 9 DLX rows, the cell in row 5 and column 7 will contain exactly one digit. As there are 9 possible rows and 9 possible columns, there are 9x9=81 Type 1 columns in the DLX matrix.

For example, the Type 2 (digit-row) constraint <2,5> is that the digit 2 must occur in row 5 exactly once. The column in the DLX matrix for this constraint has a 1 in the DLX rows <2,5,1>, <2,5,2>, ..., <2,5,9>, which correspond to placing the digit 2 in the cell in row 5 and columns 1 through 9. (The DLX column has a 0 in every other DLX row.) Since a valid solution will select only one of these 9 DLX rows, the digit 2 will occur in row 5 exactly once. As there are 9 possible digits and 9 possible rows, there are 9x9=81 Type 2 columns in the DLX matrix.

Similarly, there are 9x9=81 Type 3 (digit-column) constraints, one for each of 9 digits and 9 columns.

Similarly, there are 9x9=81 Type 4 (digit-box) constraints, one for each of 9 digits and 9 boxes.

Thus there are 81+81+81+81=324 DLX columns.

In summary, the DLX matrix has 729 rows and 324 columns.

Note that each DLX row contains exactly 4 1s (and 324-4=320 0s). For example, the DLX row <2,5,7>, which corresponds to placing the digit 2 in the cell in row 5 and column 7, has a 1 in the DLX columns for row-column constraint <5,7>, digit-row constraint <2,5>, digit-column constraint <2,7> and digit-box constraint <2,6> (and has a 0 in every other DLX column). (The cell in row 5 and column 7 occurs in box 6, when boxes are numbered from 1 to 9 left-to-right and top-to-bottom.)

Note that each DLX column contains exactly 9 1s (and 729-9=720 0s).

Thus the DLX matrix is sparse, and much efficiency is gained by maintaining nodes for only the 1s.

Note that the ordering of the rows and columns is irrelevant, so long as you can convert between the constraints satisfied by a move and the columns representing each constraint.

To solve a specific Sudoku problem, select the DLX rows representing the givens and then solve the DLX matrix. For example, if it is a given that the digit 2 occurs in the cell in row 5 and column 7, then the DLX row <2,5,7> is part of the solution.

For developers - here is a c code for sudoku

Source: http://www.setbb.com/phpbb/

// speed-optimized for hard 16*16s , new trick: remember how good
// column-choices were ! (see lines with a ~)

#include stdio.h
#include time.h
#include stdio.h
#include sys/time.h

#define N 4 // 16*16-sudoku
#define N2 N*N
#define N4 N2*N2
#define MWC ( (zr=36969*(zr&65535)+(zr>>16)) ^ (wr=18000*(wr&65535)+(wr>>16)) )
int A[N4 + 9], Ur[N2 * N4 + 1], Uc[4 * N4 + 1], V[N2 * N4 + 1];
int Rows[4 * N4 + 1], Cols[N2 * N4 + 1], Row[4 * N4 + 1][N2 + 1],
Col[N2 * N4 + 1][5];
int C[N4 + 1], I[N4 + 1], Node[N4 + 1], Two[N4 * 4 + 9], C0[N4 * 4 + 9], P[N4 + 9];
int M1[N4 + 9][4 * N4 + 9], N1[N4 + 9][4 * N4 + 9], Z1[N4 + 9][4 * N4 + 9]; //~
int s1, i1, t1, i4, c0, m0, m1, try, i, j, k, l, r, r1, c, c1, c2, n = N4 * N2, m =
4 * N4, x, y, s;
int sam, samples, smax, min, clues, nodes, guesses, solutions;
unsigned zr = 362436069, wr = 521288629;
char L[18] = ".123456789ABCDEFG";
FILE *file;

int solve (int);
int reduce (int);
int unreduce (int);

int main (int argc, char *argv[])
{
clock ();
//These are for out rancom number x
unsigned int seed;
struct timeval tv;

if (argc <>
m5:printf ("\nusage:suexg16f samples \n\n");
printf ("generates samples sudokus\n");
exit (1);
}
gettimeofday (&tv, 0);
x = tv.tv_sec + tv.tv_usec;
zr += x;
wr ^= x;
sscanf (argv[1], "%i", &samples);

for (i = 1; i <= m; i++) {
j = 1;
while (j <>
j += j;
Two[i] = j - 1;
}

r = 0;
k = N;
l = N2;
for (x = 1; x <= N2; x++)
for (y = 1; y <= N2; y++)
for (s = 1; s <= N2; s++) {
r++;
Cols[r] = 4;
Col[r][1] = x * N2 - N2 + y;
Col[r][2] = (k * ((x - 1) / k) + (y - 1) / k) * l + s + N4;
Col[r][3] = x * N2 - N2 + s + N4 * 2;
Col[r][4] = y * N2 - N2 + s + N4 * 3;
}
for (i = 1; i <= m; i++)
Rows[i] = 0;
for (r = 1; r <= n; r++)
for (i = 1; i <= Cols[r]; i++) {
c = Col[r][i];
Rows[c]++;
Row[c][Rows[c]] = r;
}

for (sam = 1; sam <= samples; sam++) {
m0:for (i = 1; i <= N4; i++)
A[i] = 0;
solve (1);

for (i = 1; i <= N4; i++) {
mr4:x = MWC & 255;
if (x >= i)
goto mr4;
x++;
P[i] = P[x];
P[x] = i;
}
for (i1 = 1; i1 <= N4; i1++)
if (A[P[i1]]) {
s1 = A[P[i1]];
A[P[i1]] = 0;
if (solve (2) > 1)
A[P[i1]] = s1;
}

if ((file = fopen ("sudoku.16", "at")) == NULL) {
fclose (file);
printf ("\nfile-error\n\n");
exit (1);
}
for (i = 1; i <= N4; i++)
fprintf (file, "%c", L[A[i]]);
fprintf (file, "\n");
fclose (file);

for (i = 1; i <= N4; i++)
printf ("%c", L[A[i]]);
printf ("\n");
}
printf ("%i sudokus generated in %i/%isec.\n", samples, clock (), CLOCKS_PER_SEC);

return 0;
}

int solve (int smax)
{
for (i = 0; i <= N4 >> 4; i++)
for (j = 1; j <= m; j++) {
N1[i][j] = 0;
Z1[i][j] = 0;
} //~
for (i = 0; i <= n; i++)
Ur[i] = 0;
for (i = 0; i <= m; i++)
Uc[i] = 0;
clues = 0;
for (x = 1; x <= N2; x++)
for (y = 1; y <= N2; y++)
if (A[x * N2 - N2 + y]) {
clues++;
r = x * N4 - N4 + y * N2 - N2 + A[x * N2 - N2 + y];
for (j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
if (Uc[c1])
return -1;
Uc[c1]++;
for (k = 1; k <= Rows[c1]; k++) {
r1 = Row[c1][k];
Ur[r1]++;
}
}
}
for (c = 1; c <= m; c++) {
V[c] = 0;
for (r = 1; r <= Rows[c]; r++)
if (Ur[Row[c][r]] == 0)
V[c]++;
}

m0 = 0;
m1 = 0;
guesses = 0;
i = clues;
solutions = 0;
m2:i++;
I[i] = 0;
min = n + 1;
if (i > N4 || m0)
goto m4;
if (m1) {
C[i] = m1;
goto m3;
}

c0 = 0;
for (c = 1; c <= m; c++)
if (!Uc[c]) {
if (V[c] <= min) {
c0++;
C0[c0] = c;
}
if (V[c] <>
min = V[c];
c0 = 1;
C[i] = c;
C0[c0] = c;
if (min <>
goto m3;
}
}
if (min > 1)
guesses++;

m2a:c1 = MWC & Two[c0];
if (c1 >= c0)
goto m2a;
c1++;
C[i] = C0[c1];

min = 999999;
i4 = i >> 4;
for (j = c1; j <= c0; j++) {
c = C0[j];
if (N1[i4][c] <>
min = N1[i4][c] / Z1[i4][c];
C[i] = c;
}
} //~
for (j = 1; j <>
c = C0[j];
if (N1[i4][c] <>
min = N1[i4][c] / Z1[i4][c];
C[i] = c;
}
} //~

m3:c = C[i];
I[i]++;
if (I[i] > Rows[c])
goto m4;
r = Row[c][I[i]];
if (Ur[r])
goto m3;
m0 = 0;
m1 = 0;
if (smax == 1) {
j = N2;
k = N4;
x = (r - 1) / k + 1;
y = ((r - 1) % k) / j + 1;
s = (r - 1) % j + 1;
A[x * N2 - N2 + y] = s;
}
for (j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
Uc[c1]++;
}
for (j = 1; j <= Cols[r]; j++)
reduce (Col[r][j]);
Node[i]++;
nodes++;
M1[i][c] = nodes; //~ remember nodes
if (i == N4) {
solutions++;
if (smax == 1)
return 1;
}
if (solutions > 1)
return 2;
goto m2;
m4:c = C[i];
N1[i >> 4][c] += nodes - M1[i][c];
Z1[i >> 4][c]++; //~ column-statistics
i--;
c = C[i];
r = Row[c][I[i]];
for (j = 1; j <= Cols[r]; j++)
unreduce (Col[r][j]);
if (i > clues)
goto m3;
return solutions;
}

int reduce (int c)
{ // deletes c and N[c], updates V[],m0,m1
int r, c2, k, l;

for (k = 1; k <= Rows[c]; k++) {
r = Row[c][k];
Ur[r]++;
if (Ur[r] == 1)
for (l = 1; l <= Cols[r]; l++) {
c2 = Col[r][l];
V[c2]--;
if (Uc[c2] + V[c2] <>
m0 = c2;
if (Uc[c2] == 0 && V[c2] <>
m1 = c2;
}
}
}

int unreduce (int c)
{
int r, c2, k, l;

Uc[c]--;
for (k = 1; k <= Rows[c]; k++) {
r = Row[c][k];
Ur[r]--;
if (Ur[r] == 0)
for (l = 1; l <= Cols[r]; l++) {
c2 = Col[r][l];
V[c2]++;
}
}
}