1  package piscine
 2  
 3  import "fmt"
 4  
 5  const size int = 8
 6  
 7  var board [size][size]bool
 8  
 9  func EightQueens() {
10  	placeX(0)
11  }
12  
13  func printQueens() {
14  	x := 0
15  	for x < size {
16  		y := 0
17  		for y < size {
18  			if board[x][y] {
19  				// We have found a queen, let's print her y
20  				fmt.Print(y + 1)
21  			}
22  			y++
23  		}
24  		x++
25  	}
26  	fmt.Println('\n')
27  }
28  
29  func placeX(x int) {
30  	for y := 0; y < size; y++ {
31  		if canBePlaced(x, y) {
32  			board[y][x] = true
33  			if x == size-1 {
34  				printQueens()
35  			} else {
36  				placeX(x + 1)
37  			}
38  			board[y][x] = false
39  		}
40  	}
41  }
42  
43  func canBePlaced(x, y int) bool {
44  	for i := 0; i < size; i++ {
45  		// check row
46  		if board[y][i] {
47  			return false
48  		}
49  		// check column
50  		if board[i][x] {
51  			return false
52  		}
53  		// check diagonal
54  		py := y + i
55  		px := x + i
56  		my := y - i
57  		mx := x - i
58  		if px < size && py < size && board[py][px] {
59  			return false
60  		}
61  		if mx >= 0 && my >= 0 && board[my][mx] {
62  			return false
63  		}
64  		if mx >= 0 && py < size && board[py][mx] {
65  			return false
66  		}
67  		if px < size && my >= 0 && board[my][px] {
68  			return false
69  		}
70  	}
71  	return true
72  }