Sudoku: Difference between revisions

=={{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>