-
Notifications
You must be signed in to change notification settings - Fork 6
/
Solver.cs
403 lines (373 loc) · 18.9 KB
/
Solver.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
/// <summary>
/// Ported from http://norvig.com/sudo.py by Richard Birkby, June 2007.
/// See http://norvig.com/sudoku.html
/// Also, https://bugzilla.mozilla.org/attachment.cgi?id=266577 - Javascript1.8 version
/// </summary>
static class LinqSudokuSolver {
// Throughout this program we have:
// r is a row, e.g. 'A'
// c is a column, e.g. '3'
// s is a square, e.g. 'A3'
// d is a digit, e.g. '9'
// u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
// g is a grid, e.g. 81 non-blank chars, e.g. starting with '.18...7...
// values is a dict of possible values, e.g. {'A1':'123489', 'A2':'8', ...}
static string rows = "ABCDEFGHI";
static string cols = "123456789";
static string digits = "123456789";
static string[] squares = cross(rows, cols);
static Dictionary<string, IEnumerable<string>> peers;
static Dictionary<string, IGrouping<string, string[]>> units;
/*
* def cross(A, B):
* return [a+b for a in A for b in B]
*/
static string[] cross(string A, string B) {
return (from a in A from b in B select ""+a+b).ToArray();
}
static LinqSudokuSolver() {
/*
* unitlist = ([cross(rows, c) for c in cols] +
* [cross(r, cols) for r in rows] +
* [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
*/
var unitlist=((from c in cols select cross(rows, c.ToString()))
.Concat(from r in rows select cross(r.ToString(), cols))
.Concat(from rs in (new [] { "ABC", "DEF", "GHI" }) from cs in (new [] { "123", "456", "789" }) select cross(rs, cs)));
/*
* units = dict((s, [u for u in unitlist if s in u])
* for s in squares)
*/
units = (from s in squares from u in unitlist where u.Contains(s) group u by s into g select g).ToDictionary(g=>g.Key);
/*
* peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s))
* for s in squares)
*/
peers = (from s in squares from u in units[s] from s2 in u where s2 != s group s2 by s into g select g).ToDictionary(g=>g.Key, g=>g.Distinct());
}
/* [Javascript1.8]
* function zip(A, B) {
* let z = []
* let n = Math.min(A.length, B.length)
* for (let i = 0; i < n; i++)
* z.push([A[i], B[i]])
* return z
* }
*/
static string[][] zip(string[] A, string[] B) {
var n=Math.Min(A.Length, B.Length);
string[][] sd = new string[n][];
for(var i = 0; i < n; i++) {
sd[i]=new string[] {A[i].ToString(), B[i].ToString()};
}
return sd;
}
/*
def parse_grid(grid):
"Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}"
grid = [c for c in grid if c in '0.-123456789']
values = dict((s, digits) for s in squares) ## To start, every square can be any digit
for s,d in zip(squares, grid):
if d in digits and not assign(values, s, d):
return False
return values
*/
/// <summary>Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}</summary>
public static Dictionary<string, string> parse_grid(string grid) {
var grid2 = from c in grid where "0.-123456789".Contains(c) select c;
var values = squares.ToDictionary(s => s, s => digits); //To start, every square can be any digit
foreach (var sd in zip(squares, (from s in grid select s.ToString()).ToArray())) {
var s = sd[0];
var d = sd[1];
if (digits.Contains(d) && assign(values, s, d)==null) {
return null;
}
}
return values;
}
/*
* def search(values):
* "Using depth-first search and propagation, try all possible values."
* if values is False:
* return False ## Failed earlier
* if all(len(values[s]) == 1 for s in squares):
* return values ## Solved!
* ## Chose the unfilled square s with the fewest possibilities
* _,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
* return some(search(assign(values.copy(), s, d))
* for d in values[s])
*/
/// <summary>Using depth-first search and propagation, try all possible values.</summary>
public static Dictionary<string, string> search(Dictionary<string, string> values) {
if (values == null) {
return null; // Failed earlier
}
if (all(from s in squares select values[s].Length == 1?"":null)) {
return values; // Solved!
}
// Chose the unfilled square s with the fewest possibilities
var s2 = (from s in squares where values[s].Length > 1 orderby values[s].Length ascending select s).First();
return some(from d in values[s2]
select search(assign(new Dictionary<string,string>(values), s2, d.ToString())));
}
/*
* def assign(values, s, d):
* "Eliminate all the other values (except d) from values[s] and propagate."
* if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
* return values
* else:
* return False
*/
/// <summary>Eliminate all the other values (except d) from values[s] and propagate.</summary>
static Dictionary<string, string> assign(Dictionary<string, string> values, string s, string d) {
if (all(
from d2 in values[s]
where d2.ToString() != d
select eliminate(values, s, d2.ToString()))) {
return values;
}
return null;
}
// Eliminate d from values[s]; propagate when values or places <= 2.
/* def eliminate(values, s, d):
* "Eliminate d from values[s]; propagate when values or places <= 2."
* if d not in values[s]:
* return values ## Already eliminated
* values[s] = values[s].replace(d,'')
* if len(values[s]) == 0:
* return False ## Contradiction: removed last value
* elif len(values[s]) == 1:
* ## If there is only one value (d2) left in square, remove it from peers
* d2, = values[s]
* if not all(eliminate(values, s2, d2) for s2 in peers[s]):
* return False
* ## Now check the places where d appears in the units of s
* for u in units[s]:
* dplaces = [s for s in u if d in values[s]]
* if len(dplaces) == 0:
* return False
* elif len(dplaces) == 1:
* # d can only be in one place in unit; assign it there
* if not assign(values, dplaces[0], d):
* return False
* return values
*/
/// <summary>Eliminate d from values[s]; propagate when values or places <= 2.</summary>
static Dictionary<string, string> eliminate(Dictionary<string, string> values, string s, string d) {
if (!values[s].Contains(d)) {
return values;
}
values[s]=values[s].Replace(d, "");
if (values[s].Length == 0) {
return null; //Contradiction: removed last value
} else if (values[s].Length == 1) {
//If there is only one value (d2) left in square, remove it from peers
var d2 = values[s];
if (!all(from s2 in peers[s] select eliminate(values, s2, d2))) {
return null;
}
}
//Now check the places where d appears in the units of s
foreach (var u in units[s]) {
var dplaces = from s2 in u where values[s2].Contains(d) select s2;
if (dplaces.Count() == 0) {
return null;
} else if (dplaces.Count() == 1) {
// d can only be in one place in unit; assign it there
if (assign(values, dplaces.First(), d)==null) {
return null;
}
}
}
return values;
}
/*
* def all(seq):
* for e in seq:
* if not e: return False
* return True
*/
static bool all<T>(IEnumerable<T> seq) {
foreach (var e in seq) {
if (e==null) return false;
}
return true;
}
/*
* def some(seq):
* for e in seq:
* if e: return e
* return False
*/
static T some<T>(IEnumerable<T> seq) {
foreach (var e in seq) {
if (e!=null) return e;
}
return default(T);
}
/*
* def center(s, width):
* n = width - len(s)
* if n <= 0: return s
* half = n/2
* if n%2 and width%2:
* half = half+1
* return ' '*half + s + ' '*(n-half)
*/
static string Center(this string s, int width) {
var n=width-s.Length;
if(n<=0) return s;
var half = n/2;
if(n%2>0 && width%2>0) half++;
return new string(' ', half) + s + new String(' ', n-half);
}
/*
* def printboard(values):
* "Used for debugging."
* width = 1+max(len(values[s]) for s in squares)
* line = '\n' + '+'.join(['-'*(width*3)]*3)
* for r in rows:
* print ''.join(values[r+c].center(width)+(c in '36' and '|' or '')
* for c in cols) + (r in 'CF' and line or '')
* print
* return values
*/
/// <summary>Used for debugging.</summary>
static Dictionary<string, string> print_board(Dictionary<string, string> values) {
if (values == null) return null;
var width = 1 + (from s in squares select values[s].Length).Max();
var line = "\n" + String.Join("+", Enumerable.Repeat(new String('-', width * 3), 3).ToArray());
foreach (var r in rows) {
Console.WriteLine(String.Join("",
(from c in cols
select values[""+r+c].Center(width)+("36".Contains(c)?"|":"")).ToArray())
+ ("CF".Contains(r)?line:""));
}
Console.WriteLine();
return values;
}
public static void Test()
{
var easy = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..";
print_board(parse_grid(easy));
Console.WriteLine("Simple elimination not possible:");
var grid = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......";
print_board(parse_grid(grid));
Console.WriteLine("Try again with search:");
print_board(search(parse_grid(grid)));
var hardest = "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.";
DateTime start = DateTime.Now;
for (var i = 0; i < 300; i++)
{
search(parse_grid(hardest));
}
Console.WriteLine("Solving 'hardest' sodoku took on average " + (DateTime.Now - start).TotalMilliseconds / 300 + " milliseconds, timed over 300 runs");
var top95 = @"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
52...6.........7.13...........4..8..6......5...........418.........3..2...87.....
6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....
48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....
....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....
.524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........
6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....
.923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....
6..3.2....5.....1..........7.26............543.........8.15........4.2........7..
.6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...
..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..
3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....
1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......
6..3.2....4.....1..........7.26............543.........8.15........4.2........7..
....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.
45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..
.237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......
..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56
.98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..
..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...
4.....8.5.3..........7......2.....6.....5.4......1.......6.3.7.5..2.....1.9......
.2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4
1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46
4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......
.......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....
6..3.2....4.....8..........7.26............543.........8.15........8.2........7..
.47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.
......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....
38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..
.2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....
.8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....
..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4
4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......
1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......
1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........
249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...
...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1
...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36....
......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....
.476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7
.....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................
.4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..
.834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..
..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8
.26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4
2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......
6..3.2....1.....5..........7.26............843.........8.15........8.2........7..
1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.
.........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9
.2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5
9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.
...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.
53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.
1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4
....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..
.47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..
......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....
.2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..
1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......
2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5
..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.
...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...
34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82
......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....
.4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........
.......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3
8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2
.8...4.5....7..3............1..85...6.....2......4....3.26............417........
....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....
......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....
.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.
.52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9
....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....
1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....
4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....
......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....
963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..
15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423
..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6
....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........
6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....
....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..
.32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.
...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..
.5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..
..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.
..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.
...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..
.2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9
.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........
3...8.......7....51..............36...2..4....7...........6.13..452...........8..".Split('\n');
foreach (var game in top95)
{
Console.WriteLine(game);
print_board(search(parse_grid(game)));
search(parse_grid(game));
}
Console.WriteLine("Press enter to finish");
Console.ReadLine();
}
}