Skip to content

Instantly share code, notes, and snippets.

@fangdingjun
Created October 14, 2015 03:01
Show Gist options
  • Save fangdingjun/bf881936bdde48982e0a to your computer and use it in GitHub Desktop.
Save fangdingjun/bf881936bdde48982e0a to your computer and use it in GitHub Desktop.
N queens problem implement code in golang
package main
import (
"fmt"
"log"
"os"
"strconv"
)
const (
intvalue = -1
)
var column []int
var N int = 8
func main() {
var err error
if len(os.Args) == 2 {
N, err = strconv.Atoi(os.Args[1])
if err != nil {
log.Fatal(err)
}
}
column = make([]int, N)
for i := 0; i < N; i++ {
column[i] = intvalue
}
place(0)
}
var count int = 0
var loop int = 0
func show() {
count++
fmt.Printf("loop: %d, Answer: %d\n", loop, count)
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
if column[i] == j {
fmt.Printf(" Q")
} else {
fmt.Printf(" .")
}
}
fmt.Printf("\n")
}
fmt.Printf("\n")
}
func valid(i, j int) bool {
//fmt.Printf("i=%d, j=%d\n", i, j)
for k := 0; k <= i; k++ {
v := column[k]
if v == j || v-j == i-k || v-j == k-i {
return false
}
}
return true
}
func place(n int) {
loop++
if n >= N {
/* all row detected, show result */
show()
fmt.Printf("\n")
loop = 0
return
}
for i := 0; i < N; i++ {
if valid(n, i) {
/* found, detect next row */
column[n] = i
place(n + 1)
/* here, all row are detected
set column[n] to initial value, ready for next detecting
*/
column[n] = intvalue
}
/* not found, detect for next column */
}
/* return for backtrace */
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment