Sudoku: Difference between revisions
Content deleted Content added
Go solution |
|||
Line 1,717: | Line 1,717: | ||
|6 9 5|4 1 7|3 8 2| |
|6 9 5|4 1 7|3 8 2| |
||
+-----+-----+-----+ |
+-----+-----+-----+ |
||
=={{header|Go}}== |
|||
Solution using [http://en.wikipedia.org/wiki/Dancing_Links Knuth's DLX.] This code follows his paper fairly closely. Input to function solve is an 81 character string. This seems to be a conventional computer representation for Sudoku puzzles. |
|||
<lang go>package main |
|||
import "fmt" |
|||
var puzzle = |
|||
"394 267 " + |
|||
" 3 4 " + |
|||
"5 69 2 " + |
|||
" 45 9 " + |
|||
"6 7" + |
|||
" 7 58 " + |
|||
" 1 67 8" + |
|||
" 9 8 " + |
|||
" 264 735" |
|||
func main() { |
|||
printGrid("puzzle:", puzzle) |
|||
if s := solve(puzzle); s == "" { |
|||
fmt.Println("no solution") |
|||
} else { |
|||
printGrid("solved:", s) |
|||
} |
|||
} |
|||
func printGrid(title, s string) { |
|||
fmt.Println(title) |
|||
for r, i := 0, 0; r < 9; r, i = r+1, i+9 { |
|||
fmt.Printf("%c %c %c | %c %c %c | %c %c %c\n", |
|||
s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5], s[i+6], s[i+7], s[i+8]) |
|||
if r == 2 || r == 5 { |
|||
fmt.Println("------+-------+------") |
|||
} |
|||
} |
|||
} |
|||
func solve(u string) string { |
|||
d := newDlxObject(324) |
|||
for r, i := 0, 0; r < 9; r++ { |
|||
for c := 0; c < 9; c, i = c+1, i+1 { |
|||
b := r/3*3 + c/3 |
|||
n := int(u[i] - '0') |
|||
if n >= 1 && n <= 9 { |
|||
d.newRow([]int{i + 1, 81 + r*9 + n, 162 + c*9 + n, 243 + b*9 + n}) |
|||
} else { |
|||
for n = 1; n <= 9; n++ { |
|||
d.newRow([]int{i + 1, 81 + r*9 + n, 162 + c*9 + n, 243 + b*9 + n}) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
h := &d[0] |
|||
var o []*x |
|||
if solution := h.search(o); solution != nil { |
|||
return text(solution) |
|||
} |
|||
return "" |
|||
} |
|||
// Knuth's data object |
|||
type x struct { |
|||
c *y |
|||
u, d, l, r *x |
|||
} |
|||
// Knuth's column object |
|||
type y struct { |
|||
x |
|||
s int // size |
|||
n int // name |
|||
} |
|||
// convenient during construction to work with all column headers in a slice. |
|||
type sparse []y |
|||
func newDlxObject(nCols int) sparse { |
|||
d := make(sparse, nCols+1) |
|||
// d[0] is Knuth's h, the root node. He mentioned h.c was unused, |
|||
// but we need it initialized to satisfy Go's strict type checking. |
|||
d[0].c = &d[0] |
|||
d[0].l = &d[nCols].x |
|||
for i := 1; i <= nCols; i++ { |
|||
d[i].n = i - 1 |
|||
d[i].c = &d[i] |
|||
d[i].u = &d[i].x |
|||
d[i].d = &d[i].x |
|||
d[i-1].r = &d[i].x |
|||
d[i].l = &d[i-1].x |
|||
} |
|||
d[nCols].r = &d[0].x |
|||
return d |
|||
} |
|||
func (a sparse) newRow(nr []int) { |
|||
var rh x |
|||
rh.l, rh.r = &rh, &rh |
|||
for _, j := range nr { |
|||
a[j].s++ |
|||
np := &x{&a[j], a[j].u, &a[j].x, rh.l, &rh} |
|||
a[j].u.d, a[j].u, rh.l.r, rh.l = np, np, np, np |
|||
} |
|||
rh.l.r, rh.r.l = rh.r, rh.l |
|||
} |
|||
func (h *y) search(o []*x) []*x { |
|||
j := h.r.c |
|||
if j == h { |
|||
return o |
|||
} |
|||
// choose column with min s |
|||
c := j |
|||
for minS := j.s; ; { |
|||
j = j.r.c |
|||
if j == h { |
|||
break |
|||
} |
|||
if j.s < minS { |
|||
c, minS = j, j.s |
|||
} |
|||
} |
|||
cover(c) |
|||
for r := c.d; r != &c.x; r = r.d { |
|||
o = append(o, r) |
|||
for j := r.r; j != r; j = j.r { |
|||
cover(j.c) |
|||
} |
|||
if solution := h.search(o); solution != nil { |
|||
return solution |
|||
} |
|||
// Knuth resets r and c at this point. |
|||
// they are actually still set with the correct values, but |
|||
// we need to pop the failed row from the partial solution o. |
|||
o = o[:len(o)-1] |
|||
for j := r.l; j != r; j = j.l { |
|||
uncover(j.c) |
|||
} |
|||
} |
|||
uncover(c) |
|||
return nil |
|||
} |
|||
func cover(c *y) { |
|||
c.r.l, c.l.r = c.l, c.r |
|||
for i := c.d; i != &c.x; i = i.d { |
|||
for j := i.r; j != i; j = j.r { |
|||
j.d.u, j.u.d = j.u, j.d |
|||
j.c.s-- |
|||
} |
|||
} |
|||
} |
|||
func uncover(c *y) { |
|||
for i := c.u; i != &c.x; i = i.u { |
|||
for j := i.l; j != i; j = j.l { |
|||
j.c.s++ |
|||
j.d.u, j.u.d = j, j |
|||
} |
|||
} |
|||
c.r.l, c.l.r = &c.x, &c.x |
|||
} |
|||
func text(o []*x) string { |
|||
b := make([]byte, 81) |
|||
for _, r := range o { |
|||
b[r.c.n] = byte(r.r.c.n%9) + '1' |
|||
} |
|||
return string(b) |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
puzzle: |
|||
3 9 4 | 2 | 6 7 |
|||
| 3 | 4 |
|||
5 | 6 9 | 2 |
|||
------+-------+------ |
|||
4 5 | | 9 |
|||
6 | | 7 |
|||
7 | | 5 8 |
|||
------+-------+------ |
|||
1 | 6 7 | 8 |
|||
9 | 8 | |
|||
2 6 | 4 | 7 3 5 |
|||
solved: |
|||
3 9 4 | 8 5 2 | 6 7 1 |
|||
2 6 8 | 3 7 1 | 4 5 9 |
|||
5 7 1 | 6 9 4 | 8 2 3 |
|||
------+-------+------ |
|||
1 4 5 | 7 8 3 | 9 6 2 |
|||
6 8 2 | 9 4 5 | 3 1 7 |
|||
9 3 7 | 1 2 6 | 5 8 4 |
|||
------+-------+------ |
|||
4 1 3 | 5 6 7 | 2 9 8 |
|||
7 5 9 | 2 3 8 | 1 4 6 |
|||
8 2 6 | 4 1 9 | 7 3 5 |
|||
</pre> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |