27160 total geeks with 3531 solutions
Recent challengers:
 Welcome, you are an anonymous user! [register] [login] Get a yourname@osix.net email address 

Articles

GEEK

User's box
Username:
Password:

Forgot password?
New account

Shoutbox
MaxMouse
It's Friday... That's good enough for me!
CodeX
non stop lolz here but thats soon to end thanks to uni, surely the rest of the world is going good?
stabat
how things are going guys? Here... boring...
CodeX
I must be going wrong on the password lengths then, as long as it was done on ECB
MaxMouse
lol... the key is in hex (MD5: of the string "doit" without the "'s) and is in lower case. Maybe i should have submitted this as a challenge!

Donate
Donate and help us fund new challenges
Donate!
Due Date: Nov 30
November Goal: $40.00
Gross: $0.00
Net Balance: $0.00
Left to go: $40.00
Contributors


News Feeds
The Register
Get a job in
Germany ? where
most activities are
precursors to
drinking
BIG FAT Lies: Porky
Pies about obesity
Culture CLASH:
Wuzhen Declaration
spurned at World
Internet Conference
in China
Pitchfork-wielding
villagers hunt
hairy shapeshifters
in One Night
Ultimate
Werewo
Post-pub nosh
neckfiller:
Bryndzové halu?ky
What We Do In
The Shadows
?
Laugh ourselves
silly, mostly
UK"s non-emergency
police and NHS
Vodafone systems go
titsup NATIONWIDE
Yahoo!
blames!
MONSTER!
email!
OUTAGE!
on!<
Criticism of Uber"s
journo-Data
Analytics plan is
an Attack on
DIGITAL FREEDOM
Ford"s B-Max:
Fiesta-based
runaround that goes
THUNK
Slashdot
Great Firewall of
China Blocks
Edgecast CDN,
Thousands of
Websites Affected
Judge Unseals 500+
Stingray Records
Samsung Seeking To
Block Nvidia Chips
From US Market
Doubling Saturated
Fat In Diet Does
Not Increase It In
Blood
Ask Slashdot: Best
Practices For
Starting and
Running a Software
Shop?
Eizo Debuts Monitor
With 1:1 Aspect
Ratio
Upgrading the
Turing Test:
Lovelace 2.0
Profanity-Laced
Academic Paper
Exposes Scam
Journal
Ukraine"s IT
Brigade Supports
the Troops
Extreme Shrimp May
Hold Clues To Alien
Life On Europa
Article viewer

Solving sudoku with C#



Written by:sfabriz
Published by:thinkt4nk
Published on:2006-06-15 10:10:36
Topic:Dot.Net
Search OSI about Dot.Net.More articles by sfabriz.
 viewed 56771 times send this article printer friendly

Digg this!
    Rate this article :
This article shows you how to solve any Sudoku using a C# implementation of Knuth's DLX algorithm.

Introduction
I have to thank my mother for always complaining about sudoku programs you can download from the net. This pushed me to build a sudoku program tailored on her preferences and doing this I discovered the DLX algorithm.
Bear in mind that I'm not giving here a complete explanation of the DLX algorithm, since it took Knuth 26 pages to explain that. If you want to understand the DLX just download Knuth's paper from his site. Here's a link

Topics
  • What is a sudoku?
  • What is the DLX algorithm?
  • How can I apply the DLX algorithm to sudoku problems?
  • How the C# code for all this may look like?


Part I: Let's play Sudoku!
Sudoku is a japanese game based on numbers and logic. If you want to learn more about it's origins and details in general, I suggest you to visit the sudoku page on WikiPedia.
The aim of the game is to fill in a 9x9 square grid with numbers from 1 to 9 starting from an incomplete grid.
The 9x9 square grid is also partitioned into 9 3x3 grids (boxes from now on).

You must follow these rules:
  • Each row must contain all the numbers from 1 to 9 in some order.
  • Each column must contain all the numers from 1 to 9 in some order.
  • Each 3x3 box must contain all the numbers from 1 to 9 in some order.

Also, the purists of this game are very picky on these rules too:
  • The starting grid must present numbers with some simmetry (center simmetry)
  • The solution must be unique.
  • It should be possible to solve the sudoku using just logic (no guessing)

In sudoku jargon the numbers that you already have when you start playing sudoku are called "givens".

Here you can see an example of an evil sudoku starting grid and its unique solution.

==> solution ==>

You can notice the symmetry of the starting grid. This sudoku was taken from the www.websudoku.com site, where you can play to 4 different difficulties sudokus. I chose an evil one for my example.

I'm not going long with an explanation about how to play sudoku here. That's not the aim of this article.
If you're not familiar with sudoku please take your time to surf the net a while and become familiar with it before reading the rest of this article. To become familiar with sudoku is a matter a 5 minutes. The rules are simple and few and you need no math skills to play it.

Part II: Thank you Donald Knuth!
Man, if you're a programmer or simply an addicted to i.t. you must get yourself a copy of Knuth works. On my bookshelf I'm proud to expose his "The art of computer programming" entire collection and I must tell you, reading those books gives you an understanding of this subject that really goes beyond any aspectation.
So, what is this DLX algorithm? Basically is a very cool algorithm used to quickly solve the "Exact cover" problem. A problem which is well known to be NP-complete. Basically the exact cover problem is simple to understand, but not so simple to solve as the problem size grows up a little.
You have a matrix, filled with 0's and 1's and you want to know if there is a subset of it's rows that leads to have just one single 1 for each column.
A very small example:

Row 1 : 0 1 0 0
Row 2 : 1 0 0 0
Row 3 : 1 1 1 0
Row 4 : 0 0 1 1

As you can see, rows 1,2,4 summed altogether present a 1 in each column, representing a solution to this particular matrix.

The algorithm that solves the exact cover problem is described in knuth papers so I'll just quickly report it here with no explanation.

Algorithm X on Matrix A:

If A is empty the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically)
Choose a row, r, such that A[r,c]=1 (nondeterministically)
Include r in the partial solution
foreach j such that A[r,j]=1
   delete column j from matrix A;
   foreach i such that A[i,j]=1
      delete row i from matrix A
Repeat this algorithm recursively on the reduced matrix A

Let me just tell you a couple of things:
It's best to choose deterministically the column c using the minimum search. I mean, it's better to choose the column c such that the number of 1's un that column is the minimum you can find for every column. This way you'll reduce to the min the number of branches the algorithm has to do.

So what we do is: we pick a column, choose a row where there is an 1 in correspondence of the column and delete that row (after including it in the partial solution), then we delete each column that present a 1 on the row we are deleting. We also delete all other rows that have one 1 on column c.
After these deletions we have a reduced matrix on which we run this algo recursively again and again, until we have a null matrix or an impossible to solve matrix.

Algorithm X on our small example would yield:

Row 1 : 0 1 0 0
Row 2 : 1 0 0 0
Row 3 : 1 1 1 0
Row 4 : 0 0 1 1

I choose column 4 (since it has just one 1), this provokes the deletion of column 3 and row 3 leaving me with this reduced matrix (first 2 rows, first 2 columns).

Row 1 : 0 1
Row 2 : 1 0

So now I just pick the first column and I remain with just a 1x1 matrix with a 1 inside. I pick it and I have got my solution: Rows 4,2,1 or in order if you prefer, 1,2,4, since the order has no particular meanings.

So, what about a 1000x1000 matrix? or 100000x100000? Hehe, having a problem of that size leads to a non negligible computation time and size too. (Please note that it's not required for the matrix to be a square one)
What can we do? Well, we can read Knuth papers and implement the Dancin Links Algorithm (DLX).
Basically the DLX is the transposition of the exact cover problem matrix on a double linked list.
A double linked list is a two-dimensional list where each element is linked to it's neighbours and also wraps around horizontally and vertically.
To give you a small letter example:

A B C D
E F G
H I

Let's examine node F.
It has B as Up neighbour, I as Down neighbour, G as Right neighbour and E as Left neighbour.
What about B though?
Since the double linked list wraps around it has I as Up neighbour, A as Left neighbour, C as Right neighbour and F as Down neighbour.
Last we examine node I:
It has F as Up neighbour, B as Down neighbour, H as Left neighbour and H also as Right neighbour, since the list wraps also horizontally.
This should be clear enough.

So, we build a list like this with some Node objects, and we put a Node where in the matrix we find a 1. We don't put anything where we find a 0.
This would yield a sparse matrix made up by Node objects where 0's are not represented. This surely brings down the load of the problem since we have less data to keep alive.
This also let's us using the DLX to manipulate very quickly this structure in order to solve the exact cover problem.
The DLX is basically the using pointers version of the X algorithm.
Nobody can explain it better than Knuth obviously, so I suggest you to run read his paper before continuing here.

Part III : Making the trick
To solve sudoku using DLX we have to map the sudoku problem to an equivalent exact cover problem.
To do this, let's see what meaning the matrix columns and rows will have.
Each row represents a placement. I mean, when you decide to write e.g. 7 in cell (3,5) you have made a placement. This decision has some effects on the game since now in row 3, column 5 and box 2 (boxes are counted from 1 to 9 from top left to bottom right reading in row major order) you can't put another 7. Also, putting a 7 in (3,5) means that in (3,5) you can't put another number.
This is pretty everything you have to consider. Hence we have 4 conditions to respect:

  • You can't put more than one number in each cell (row,column condition)
  • You can't put the same number twice or more in a row (row,digit condition)
  • You can't put the same number twice or more in a column (column,digit condition)
  • You can't put the same number twice or more in a box (box,digit condition)

Our matrix columns will represent these four conditions and our matrix rows will represent each different placement you can do on the 9x9 grid.

Ok, since there are 9x9=81 cells in the grid and there are 9 different numbers you can place in each cell, the number of the possible placements you can do is 81x9 = 9^3 = 729.
For the columns let's check each condition (1 to 4):

Condition 1: Cell taken
The are 9x9 = 81 possible cells that can be taken (a cell is "taken" after you place a number in it) so first condition yields 81 (matrix)columns of (r,c) kind. R will be the major index for this condition.
So, (matrix)columns from 1 to 9 will represent putting a number in row 1, columns 1 to 9.
(Matrix)columns from 10 to 18 will represent putting a number in row 2, columns 1 to 9 and so on...
Basically if you want to place a number in row r, column c you will place a 1 in column r*9+c.

Condition 2: Row, digit condition
There are 9 rows and 9 possible different numbers you can place in each row so, 9x9 = 81 and we have again 81 (matrix)columns for condition 2. Also this time r is being the major index so placing digit d in row r will place a 1 in (matrix)column r*9+d +[81].
81 are the first condition related columns.

Condition 3: Column, digit condition
As for the rows, there are 9 columns with 9 possible different numbers you can place each one of them.
Again, 9x9 = 81 (matrix)columns and this time the column index is the major one, so placing digit d in column c will place a 1 at (matrix)column c*9+d +[81]+[81].
81+81 are the first + second condition related columns.

Condition 4: Box, digit condition
As for rows and columns, same for the boxes. 9 boxes, 9 digits, 81 more (matrix)columns. Box index is the major one, so placing a number d in box b will place a 1 in (matrix)column b*9+d +[81]+[81]+[81].
81+81+81 are the first + second + third condition related columns.

We have 81x4 = 324 condition columns at all.
Hence, a 729x324 matrix is enough to transpose a sudoku problem into an exact cover one:

This is something you must have clear in mind in order to understand what's coming now.
After struggling with this transposition I found out in WikiPedia a page that explains these concepts in a similar way I did. I don't remember the url so please search on your own (keywords: sudoku, DLX).

Let's examine a couple of rows to give you an example.
Say you want to place number 7 in cell (3,5).
So, d=7, r=3, c=5 and b=2.
Our row will have 4 1's placed in each correspondent condition column.
Placing number 7 in cell (3,5) will make this cell unavailable for other numbers hence we put a 1 in (matrix)column 3*9+5=32.
Also, we have put a 7 in row 3 so we'll have to put a 1 in (matrix)column [81] + 3*9+7=115.
Notice that [81] I summed. Those are the first 81 (r,c) conditions.
Let's check third condition:
I'll place a 1 in (matrix)column [81]+[81] + 5*9+7=214.
First 81 + 81 (matrix)columns are cell taken conditions and row-digit conditions.
Last 1 is at column [81]+[81]+[81] + 2*9+7=268.
Obviously first 81 is cell taken conditions, then row-digit conditions, then column-digit conditions.

Another quick example:
Say you want to place number 1 in cell (5,2).
So, d=1, r=5, c=2 and b=4.
Our row will have four 1's again and they will be:
(Matrix)Column 5*9+2 for cell taken condition.
(Matrix)Column [81] + 5*9+1 for row-digit condition.
(Matrix)Column [81]+[81] + 2*9+1 for column-digit condition
(Matrix)Column [81]+[81]+[81] + 4*9+1 for box-digit condition.

So we have placed four 1's and we'll place four 1's for each row (in different columns), not less, not more, in fact there will be a 1 for each condition that that placement has to satisfy.
Now, having 729*4=2916 1's instead of 729*(320 zeros + 4 ones)=236196 is a little better isn't it? Indeed.

Please notice that (matrix)column I wrote. That's not a cast! I used this notation to distinguish between an exact cover matrix column and a sudoku grid column. Anyway, once you understand the whole trick you shouldn't have problems recognizing what I am talking about.

Solving a sudoku is then simply a matter of making a translation.
You pick a sudoku exact cover matrix placing all 729 rows with some ordering. For example you can place every digit for cell (1,1), then every digit for cell (1,2) and so on until you're at cell (9,9).
You then have to select some rows using the givens. Selecting some rows (with the X algo I mean) means you cover those rows and relative columns as you were choosing that row at run-time with algo X. This will simulate the choice of the givens. When you have all the givens selected you run the real algorithm on the matrix you have left.
For example, placing number 2 in cell (1,1) as you see in my example image, yields the selection of the row # 2.
Selecting this row will make impossible to select other rows where for example cell (1,1) is taken. Or where there is a 2 in first row or column or box.

Shortly resuming:
1-Build a sudoku matrix
2-Select the rows that correspond to the givens
3-Solve the matrix with DLX algorithm.

You're now ready to see how to do this with C#.

Part IV: Let's code!
Note: I'm not one of those guys that like to reinvent hot water. If I find some useful code somewhere I just grab it and use it (giving credits to the author obviously). Searching for a decent DLX sudoku implementation was painful. I found tons of code in java, C/C++, javascript, etc. but none of them was enough clear for me. The only one implementation in C# I found was for a palm and implemented DLX using arrays, not objects.
After a week spent on researching I chose to code my own application following Knuth's guidelines as close as possible. So, the code you're about to read it's been written by me line by line.

Ok. We have some classes here (5 classes to be precise):

  • Node class: this class represents a Node in the matrix. It's the representation of the Knuth's DLX Nodes.
  • NodePointer class: an helper class I used to quickly retrieve the first node in a row.
  • Header class: derived by the Node class. It's a head node, and has a Name (the column index) and the size (the number of 1's in the column it is the head of)
  • DLX class: the main class. This class solves an exact cover problem.
  • SudokuSolveDLX class: derived by DLX class, this class extends it's base class methods in order to quickly adapt a sudoku to an exact cover problem and solve it.

I'm not going to show them completely here since it would be too much to read. I'll just highlight the most important things but don't fear, I'll provide you a link where you can download the complete source code and a compiled assembly to test the application.

So, let's jump the first 3 classes. Basically they are just obect classes, with references for the neighbours and the column headers. Column headers nodes also have a name (the index of that column) and a size which represents the number of 1's in that column. As I told you before choosing the column that has the minimum number of 1's reduces the number of branches that DLX does, so we need the size field in order to achieve the minimum at each step.
To quickly find rows and columns I have wrapped my double linked list within a couple of arrays. One of Header objects to retrieve columns and one of NodePointer objects, to retrieve rows.
For example NodePointer[200] points directly to the first Node object of 200th row.
It's a bit of space required but helps with time. Ok, let's have a look to some DLX methods:

This is the BuildSkeleton method. It builds up the arrays that wrap the matrix.

public void BuildSkeleton(int r , int c) {
            columns = new Header[c];
            rows = new NodePointer[r];
            // columns
            for (int i=0; i<c; i++) {
                columns[i]=new Header(i);
                columns[i].Left=h.Left;
                columns[i].Right=h;
                h.Left.Right=columns[i];
                h.Left=columns[i];
            }

            // rows
            for (int i=0; i<r; i++) {
                rows[i]=new NodePointer();
            }
        }

After this I have a couple of AppendRow methods, that simply append a row putting a Node object where it should go a 1 in the matrix.

Here there is the CoverColumn method as suggested by Knuth.

protected void CoverColumn(Header c) {
            // header unplugging
            c.Left.Right=c.Right;
            c.Right.Left=c.Left;
            
            // nodes unplugging
            Node i=c.Down;
            Node j=null;
            while (i!=c) {
                j=i.Right;
                while (j!=i) {
                    j.Up.Down=j.Down;
                    j.Down.Up=j.Up;
                    j.Head.Size--;
                    j=j.Right;
                }
                i=i.Down;
            }
        }

Covering a column means we're selecting it and we have to unplug all the nodes related to that and also related to the rows that have a 1 in the column we're covering. The unplugging takes places always in vertical direction since we need to keep at least the horizontal structure to reconstruct the whole thing.

Let's check the most important method of this class: SolveRecurse().
As you can see I don't like to use variables like a,b,c and I give proper names to fields so it's quite intuitive to imagine what the SolveRecurse method does. It solves the DLX problem recursively.

protected virtual void SolveRecurse() {
            if (h.Right==h) {
                totSolutions++;
                return;
            }
            Header c=FindMin();
            
            if (c.Size==0) return; // not a good solution

            CoverColumn(c);
            Node r=c.Down;
            Node j=null;
            while (r!=c) {
                sol.Push(r);
                j=r.Right;
                while (j!=r) {
                    CoverColumn(j.Head);
                    j=j.Right;
                }
                SolveRecurse();
                r=(Node)sol.Pop();
                c=r.Head;
                j=r.Left;
                while (j!=r) {
                    UncoverColumn(j.Head);
                    j=j.Left;
                }
                r=r.Down;
            }
            UncoverColumn(c);
        }

The method is declared protected virtual since I want it to be accessible in any derived class and I want to be able to override it. This let me create classes that solve any kind of problem using the DLX class structure.
I could have used Stack<Node> from System.Collections.Generic namespace in my code, but some of you are probably not familiar with these new features of C# 2.0 yet and I preferred not to go too hard with this code.
Anyway, the algorithm calls itself recursively. It covers the column it has chosen using the FindMin method and then executes the DLX algorithm using the CoverColumn and UncoverColumn methods. When it selects a row to be included in the solution, it pushes it's first Node into a Stack. From these nodes you can easily take out the solution when the algo is done with it's job.

After testing this class and seeing it worked well, I derived from this the SudokuSolveDLX class. I added some methods to this class to easily format a sudoku into an exact cover problem style and solve it. Let's see some code snippets:

This is the foremost method which you'll always call. It builds the sudoku matrix ready to be manipulated with your grid of givens:

public void BuildSudokuMatrix() {
            // skeleton first
            BuildSkeleton(dim*dim*dim , 4*dim*dim);

            //appending all the rows then
            int b=0;
            for (int r=0; r<dim; r++) {
                for (int c=0; c<dim; c++) {
                    // set the block
                    b=(r/bDim)*bDim+(c/bDim);
                    for (int d=0; d<dim; d++) {
                        AppendRow(new int[] {r*dim+c, dim*(dim+r)+d, dim*(c+2*dim)+d, dim*(b+3*dim)+d }, r*dim*dim+c*dim+d);
                    }
                }
            }
        }

After building the matrix you have to select the rows corresponding to the givens you have:

public void SetStartingGrid(int[,] grid) {
            try {
                for (int r=0; r<dim; r++) {
                    for (int c=0; c<dim; c++) {
                        if (grid[r , c]!=0) {
                            SelectRow(r*dim*dim+c*dim+(grid[r , c]-1));
                        }
                    }
                }
            } catch (Exception ex) {
                System.Diagnostics.Trace.WriteLine("From SetStartingGrid(int[,]):n"+ex.Message);
            }
        }

You can pass a 2D array with the givens (and 0's where you have empty cells) or you can pass a string[] array for I provided a useful overload to this method.

When you have selected the rows corresponding to the givens, you have your ready-to-be-solved exact cover problem. So you just have to call the base class Solve method.
I have provided 4 different ways to call it based on an enumeration. It's all very easy to understand so I'll let this task up to you.
All the code is commented and shouldn't be too hard to understand it.

The complete source code is HERE.
I provided also an assembly that lets you test the whole thing. Please do care about the fact that you must install version 2.0 of the .Net framework (search in the download section of Microsoft's site).


So, this is the end.
I really hope you enjoyed the trip and I hope that my code will help you build your own sudoku programs if you like to.

Peace for the world.

sfabriz

Did you like this article? There are hundreds more.

Comments:
red477
2006-06-16 06:28:16
Nice tutorial...
Anonymous
2006-08-23 15:51:10
sfabriz, pretty good.
But why implement the class NodePointer?
That class is completely reduntant - trust me.
Replace it with class Node.

public class NodePointer {
private Node n;

public Node N {
get { return n; }
set { n = value; }
}
}

Regards
/alec
sfabriz
2006-08-23 19:31:51
Thank you.
For what concerns the NodePointer class, I implemented it because I didn't want to use the node class. Every node object has many more vars than a NodePointer so in this way you save some memory.
Cheers
Anonymous
2006-09-08 05:22:00
Anonymous
2006-09-08 05:26:42
sfabriz, I should maybe add that if Node was implemented as struct and not a class, you would of course be correct (as long as NodePointer is a class)
regards
/a
sfabriz
2006-09-08 11:06:05
Dear anonymous,

I get your point. I rewiewed my code and yes, you are right. But unfortunately I didn't see that when I wrote the app, several months ago. Don't have time to change it now since I'm working on something else but thank you for pointing that out.

Cheers
Shaolan
2006-11-25 08:08:21
Good tutorial but the link of the source code doesn't work :|
Anonymous
2007-01-04 09:57:41
It works now.
Anonymous
2007-02-22 17:04:25
ranjan_prog
2007-06-11 15:25:40
i also have made a sudoku solving prog in simple C in almost 70 lines....i used backtracking.....its fast alright....i will like some challenge
Anonymous
2007-11-22 00:23:26
Looks like the zip is now empty. Any chance I could get the source?
Anonymous
2007-12-09 06:58:04
The zip file is empty, can I get the source code please because I need it today
Anonymous
2007-12-13 22:08:33
Zip file is still empty!
Anonymous
2007-12-22 10:23:51
Download is still not working correctly: sudoku.1.321C02.efw is an empty file.
aaminian
2008-02-20 23:45:36
The Zip file for the source code is empty!
Anonymous
2008-06-17 21:27:09
This is a crazy good explanation, but unfortunately the source link is empty. Any chance of this being fixed?
sfabriz
2008-06-19 00:22:43
Allright, it's fixed. I uploaded again the images too. Cheers
Anonymous
2009-01-14 16:52:46
sfabriz would you like to help of my project?
my project is to make a sudoku game in c#..
plsssss,...send me the source code of your magnificent sudoku solver,...
thx,,....god bless,...
Anonymous
2009-01-15 20:41:58
You can download the source code from the link on the bottom of the article.
Also, my code could be improved a lot, but unfortunately I don't have the time right now to do it.
Cheers,
sfabriz
Anonymous
2009-01-19 22:12:44
Hi
Was using algorithm to validate user input to a sudoku program. Found that with dumb input your program goes into an infinite loop. Still think it's excellent.
Anonymous
2009-01-19 22:21:38
PS When I say dumb input, I submitted 81 numbers in the correct input format. There were 9 integers >0 and <=9, rest were zero --- trying to catch silly input.
Anonymous
2009-02-21 01:21:07
What could cause to FindMin to give - number?
I tried to convert to other language and FindMin somehow going down to minus and to infinite loop...
Anonymous
2009-03-23 21:01:05
&#1593;&#1605;&#1604; &#1585;&#1575;&#1574;&#1593; &#1580;&#1583;&#1575;&#1611; &#1608;&#1605;&#1580;&#1607;&#1608;&#1583; &#1605;&#1605;&#1578;&#1575;&#1586; &#1575;&#1587;&#1578;&#1601;&#1583;&#1606;&#1575; &#1605;&#1606;&#1603;&#1605; &#1575;&#1604;&#1603;&#1579;&#1610;&#1585;

&#1588;&#1603;&#1585;&#1575; &#1604;&#1603;&#1605;
CodeX
2009-03-23 23:17:06
fix of the above post:
عمل رائع جداً ومجهود ممتاز استفدنا منكم الكثير

شكرا لكم

which I belive roughly translates into
Very excellent work and excellent effort benefited a lot from you

Thank you
courtesy of Google :P
Anonymous
2009-09-01 15:26:32
sabari..can u tell me where u suffered a lot while designing this program...
Anonymous
2009-09-06 18:46:33
h
Anonymous
2009-11-15 20:28:05
Thanx a lot. A very good explanation. Wikipedia lacks examples.
Anonymous
2010-02-20 21:26:38
I think the formula for condition one is incorrect. Shouldn't it be: r*n-n+c gives the column number where we will place the one? i.e. in an n by n puzzle let's say 9 by 9, for placing a 7 at 3,5 you would have: 3*9-9+5 = 23. Isn't this the column where you would place the one for the "taken" constraint? Let me know if I'm wrong... but in all, your explanation finally helped me to visualize this as Wikipedia could not. Thank you!
Anonymous
2010-02-20 22:29:32
I think the formula for condition one is incorrect. Shouldn't it be: r*n-n+c gives the column number where we will place the one? i.e. in an n by n puzzle let's say 9 by 9, for placing a 7 at 3,5 you would have: 3*9-9+5 = 23. Isn't this the column where you would place the one for the "taken" constraint? Let me know if I'm wrong... but in all, your explanation finally helped me to visualize this as Wikipedia could not. Thank you!
Anonymous
2010-02-20 22:29:54
All the formulas are wrong.
constraint 1 = columns 1-81
constraint 2 = columns 82-162
constraint 3 = columns 163-243
constraint 4 = columns 244-324

condition 1 (cell contains a value) formula is:
row*n-n+column = matrix column
condition 2 (row contains instance of value) formula is:
row*n+(n^2)-n+value = matrix column
condition 3 (col contains instance of value) formula is:
col*n+(n^2)*2-n+value = matrix column
condition 4 (box contains instance of value) formula is:
box*n+(n^2)*3-n+value = matrix column

Sincerely,
-Patrick
Anonymously add a comment: (or register here)
(registration is really fast and we send you no spam)
BB Code is enabled.
Captcha Number:


Blogs: (People who have posted blogs on this subject..)
bb
ASP.NET RadioButton GroupName when inside a Repeater on Sun 10th Jun 8am
I was thankful on finding this nugget of code, which makes the groupname work out when slamming in radiobuttons in an asp.net repeater. http://www.codeguru.com/csharp/csharp/cs _controls/custom/article.php/c12371/


     
Your Ad Here
 
Copyright Open Source Institute, 2006