GameDev/c++/WP7/and more…

Project Euler problem 96~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of the 3-digit numbers found in the top left corner of each solution grid: ");
  6: 
  7:             TestBenchSetup(); 
  8:             TestBenchLoader(using_DLX_alogorithm_and_code_from_sfabriz);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13:         /// <summary>
 14:         /// read about knuth's DLX algorithm which can be used to solve sudoku problem long time ago
 15:         /// found this awesome link http://www.osix.net/modules/article/?id=792 and code which implemented the algorithm
 16:         /// in c#. the following is pretty much direct copy of the code from the site, which helped me understand how
 17:         /// the algorithm works tremendously!
 18:         /// http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
 19:         /// http://en.wikipedia.org/wiki/Dancing_Links
 20:         /// http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm
 21:         /// http://en.wikipedia.org/wiki/Exact_cover#Sudoku
 22:         /// </summary>
 23:         static int using_DLX_alogorithm_and_code_from_sfabriz()
 24:         {
 25:             var index = 0;
 26:             var accum = new List<string>();
 27:             var result = 0;
 28:             foreach (var line in File.ReadAllLines("sudoku.txt"))
 29:             {
 30:                 if (index % 10 == 0)
 31:                 {
 32:                     if (accum.Count != 0)
 33:                     {
 34:                         result += solve(accum.ToArray());
 35:                         accum.Clear();
 36:                     }
 37:                 }
 38:                 else
 39:                     accum.Add(line);
 40:                 index++;
 41:             }
 42:             if (accum.Count != 0)
 43:                 result += solve(accum.ToArray()); // for last puzzle grid
 44:             return result;
 45:         }
 46:         static int solve(string[] grid)
 47:         {
 48:             // ---- define and initialize variables ----
 49:             var dimension = 9;
 50:             var block_dimension = 3;
 51:             var header = new Header(0);
 52:             var solution = new Stack<Node>();
 53:             var total_solutions = 0;
 54:             var row_count = dimension * dimension * dimension;
 55:             var col_count = dimension * dimension * 4;
 56:             // ---- helper functions ----
 57:             Action<Header> CoverColumn = c =>
 58:             {
 59:                 // header unplugging
 60:                 c.Left.Right = c.Right;
 61:                 c.Right.Left = c.Left;
 62:                 // nodes unplugging
 63:                 Node i = c.Down;
 64:                 Node j = null;
 65:                 while (i != c)
 66:                 {
 67:                     j = i.Right;
 68:                     while (j != i)
 69:                     {
 70:                         j.Up.Down = j.Down;
 71:                         j.Down.Up = j.Up;
 72:                         j.Header.Size--;
 73:                         j = j.Right;
 74:                     }
 75:                     i = i.Down;
 76:                 }
 77:             };
 78:             Action<Header> UncoverColumn = c =>
 79:             {
 80:                 // nodes plugging
 81:                 Node i = c.Up;
 82:                 Node j = null;
 83:                 while (i != c)
 84:                 {
 85:                     j = i.Left;
 86:                     while (j != i)
 87:                     {
 88:                         j.Up.Down = j;
 89:                         j.Down.Up = j;
 90:                         j.Header.Size++;
 91:                         j = j.Left;
 92:                     }
 93:                     i = i.Up;
 94:                 }
 95:                 // header plugging
 96:                 c.Left.Right = c;
 97:                 c.Right.Left = c;
 98:             };
 99:             Func<Header> FindMin = () =>
100:             {
101:                 int min = int.MaxValue;
102:                 Header ret = null;
103:                 Header j = (Header)header.Right;
104:                 while (j != header)
105:                 {
106:                     if (j.Size < min)
107:                     {
108:                         min = j.Size;
109:                         ret = j;
110:                     }
111:                     j = (Header)j.Right;
112:                 }
113:                 return ret;
114:             };
115:             // ---- sets up the skeleton matrix ----
116:             var rows = new Node[row_count];
117:             var columns = new Header[col_count];
118:             for (int i = 0; i < col_count; i++) // columns
119:             {
120:                 columns[i] = new Header(i);
121:                 columns[i].Left = header.Left;
122:                 columns[i].Right = header;
123:                 header.Left.Right = columns[i];
124:                 header.Left = columns[i];
125:             }
126:             for (int i = 0; i < row_count; i++) // rows
127:             {
128:                 rows[i] = new Node();
129:             }
130:             // ---- populate the matrix row by row with initialized node ----
131:             var b = 0;
132:             var pos = new int[4];
133:             var row = 0;
134:             for (int r = 0; r < dimension; r++)
135:             {
136:                 for (int c = 0; c < dimension; c++)
137:                 {
138:                     // set the block
139:                     b = (r / block_dimension) * block_dimension + (c / block_dimension);
140:                     for (int d = 0; d < dimension; d++)
141:                     {
142:                         pos[0] = r * dimension + c;
143:                         pos[1] = dimension * (dimension + r) + d;
144:                         pos[2] = dimension * (c + 2 * dimension) + d;
145:                         pos[3] = dimension * (b + 3 * dimension) + d;
146:                         row = r * dimension * dimension + c * dimension + d;
147:                         Node first = new Node(row);
148:                         first.Header = columns[pos[0]];
149:                         first.Header.Size++;
150:                         first.Down = columns[pos[0]];
151:                         first.Up = columns[pos[0]].Up;
152:                         columns[pos[0]].Up.Down = first;
153:                         columns[pos[0]].Up = first;
154:                         rows[row] = first;
155:                         for (int i = 1; i < pos.Length; i++)
156:                         {
157:                             Node t = new Node(row);
158:                             // left - right
159:                             t.Left = first.Left;
160:                             t.Right = first;
161:                             first.Left.Right = t;
162:                             first.Left = t;
163:                             // up - down
164:                             t.Down = columns[pos[i]];
165:                             t.Up = columns[pos[i]].Up;
166:                             columns[pos[i]].Up.Down = t;
167:                             columns[pos[i]].Up = t;
168:                             // head
169:                             t.Header = columns[pos[i]];
170:                             t.Header.Size++;
171:                         }
172:                     }
173:                 }
174:             }
175:             // ---- setup the matrix with given numbers ----
176:             int[,] g = new int[dimension, dimension];
177:             for (int i = 0; i < dimension; i++)
178:             {
179:                 for (int j = 0; j < dimension; j++)
180:                 {
181:                     g[i, j] = int.Parse(grid[i][j].ToString());
182:                 }
183:             }
184:             var index = 0;
185:             for (int r = 0; r < dimension; r++)
186:             {
187:                 for (int c = 0; c < dimension; c++)
188:                 {
189:                     if (g[r, c] != 0)
190:                     {
191:                         index = r * dimension * dimension + c * dimension + (g[r, c] - 1);
192:                         Node n = rows[index];
193:                         solution.Push(n);
194:                         do
195:                         {
196:                             CoverColumn(n.Header);
197:                             n = n.Right;
198:                         } while (n != rows[index]);
199:                     }
200:                 }
201:             }
202:             // ---- solve the exact cover with recursive method
203:             var first_three_num = 0;
204:             Action SolveRecursively = null;
205:             SolveRecursively = () =>
206:                 {
207:                     if (header.Right == header)
208:                     {
209:                         total_solutions++;
210:                         index = 0;
211:                         var s = new int[solution.Count];
212:                         foreach (var item in solution)
213:                         {
214:                             s[index++] = item.Row;
215:                         }
216:                         Array.Sort(s);
217:                         for (int i = 0; i < s.Length; i++)
218:                         {
219:                             s[i] = s[i] % dimension;
220:                         }
221:                         first_three_num = (s[0] + 1) * 100 + (s[1] + 1) * 10 + (s[2] + 1);
222:                         return;
223:                     }
224:                     Header c = FindMin();
225: 
226:                     if (c.Size == 0) return; // not a good solution
227: 
228:                     CoverColumn(c);
229:                     Node r = c.Down;
230:                     Node j = null;
231:                     while (r != c)
232:                     {
233:                         solution.Push(r);
234:                         j = r.Right;
235:                         while (j != r)
236:                         {
237:                             CoverColumn(j.Header);
238:                             j = j.Right;
239:                         }
240:                         SolveRecursively();
241:                         r = (Node)solution.Pop();
242:                         c = r.Header;
243:                         j = r.Left;
244:                         while (j != r)
245:                         {
246:                             UncoverColumn(j.Header);
247:                             j = j.Left;
248:                         }
249:                         r = r.Down;
250:                     }
251:                     UncoverColumn(c);
252:                 };
253:             SolveRecursively(); // invoke the method
254:             // ---- done ----
255:             return first_three_num;
256:         }
257:         class Header : Node
258:         {
259:             public int Size;
260:             public int Name;
261:             public Header(int name)
262:             {
263:                 this.Name = name;
264:                 this.Size = 0;
265:                 this.Header = this;
266:             }
267:         }
268:         class Node
269:         {
270:             public Node Right;
271:             public Node Up;
272:             public Node Left;
273:             public Node Down;
274:             public int Row;
275:             public Header Header;
276:             public Node() : this(-1, null) { }
277:             public Node(int row) : this(row, null) { }
278:             public Node(int row, Header header)
279:             {
280:                 this.Right = this.Up = this.Left = this.Down = this;
281:                 this.Row = row;
282:                 this.Header = header;
283:             }
284:         }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s