Alg | DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func dfs(u int) {
	if u == n {
		for i := 0; i < n; i++ {
			fmt.Printf("%d ", path[i])
		}
		fmt.Println()
		return
	}

	for i := 1; i <= n; i++ {
		if !st[i] {
			path[u] = i
			st[i] = true
			dfs(u + 1)
			st[i] = false
		}
	}
	return
}

 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

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

const N = 20

var (
    res         [N][N]byte
    st, dj, fdj [N]bool
    n           int
)

func main() {
    defer ot.Flush()
    n = rnI()
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            res[i][j] = '.'
        }
    }
    dfs(0)
}

func dfs(u int) {
    if u == n {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                fmt.Fprintf(ot, "%c", res[i][j])
            }
            fmt.Fprintln(ot)
        }
        fmt.Fprintln(ot)
        return
    }

    for i := 0; i < n; i++ {
        if !st[i] && !dj[i-u+n] && !fdj[u+i] {
            st[i], dj[i-u+n], fdj[u+i] = true, true, true
            res[i][u] = 'Q'
            dfs(u + 1)
            st[i], dj[i-u+n], fdj[u+i] = false, false, false
            res[i][u] = '.'
        }
    }

    return
}

//{{{
var (
    ot = bufio.NewWriter(os.Stdout)
    in = bufio.NewScanner(os.Stdin)
)

func init()        { in.Split(bufio.ScanWords) }
func rnS() string  { in.Scan(); return in.Text() }
func rnI() int     { i, _ := strconv.Atoi(rnS()); return i }
func rnF() float64 { f, _ := strconv.ParseFloat(rnS(), 64); return f }

//}}}