N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 18:13, 25 April 2022
, 2 years agoAdded Go
(→{{header|Wren}}: Improved method for checking diagonals.) |
(Added Go) |
||
Line 70:
Place Piece 13 in row 7 column 4
Place Piece 14 in row 7 column 7
</pre>
=={{header|Go}}==
{{trans|Wren}}
Much quicker, of course, than Wren itself - only takes about 35 seconds to run when using the same board limits.
However, it struggles as soon as you try to increase the board sizes for bishops or knights. When you try 7 x 7 for bishops (as the code below does) the run time shoots up to almost 5.5 minutes.
<lang go>package main
import (
"fmt"
"math"
"strings"
)
var board [][]bool
var diag1, diag2 [][]int
var diag1Lookup, diag2Lookup []bool
var n, minCount int
var layout string
func isAttacked(piece string, row, col int) bool {
if piece == "Q" {
for i := 0; i < n; i++ {
if board[i][col] || board[row][i] {
return true
}
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else if piece == "B" {
if board[row][col] {
return true
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else { // piece == "K"
if board[row][col] {
return true
}
if row+2 < n && col-1 >= 0 && board[row+2][col-1] {
return true
}
if row-2 >= 0 && col-1 >= 0 && board[row-2][col-1] {
return true
}
if row+2 < n && col+1 < n && board[row+2][col+1] {
return true
}
if row-2 >= 0 && col+1 < n && board[row-2][col+1] {
return true
}
if row+1 < n && col+2 < n && board[row+1][col+2] {
return true
}
if row-1 >= 0 && col+2 < n && board[row-1][col+2] {
return true
}
if row+1 < n && col-2 >= 0 && board[row+1][col-2] {
return true
}
if row-1 >= 0 && col-2 >= 0 && board[row-1][col-2] {
return true
}
}
return false
}
func storeLayout(piece string) {
var sb strings.Builder
for _, row := range board {
for _, cell := range row {
if cell {
sb.WriteString(piece + " ")
} else {
sb.WriteString(". ")
}
}
sb.WriteString("\n")
}
layout = sb.String()
}
func placePiece(piece string, countSoFar int) {
if countSoFar >= minCount {
return
}
allAttacked := true
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if !isAttacked(piece, i, j) {
allAttacked = false
break
}
}
if !allAttacked {
break
}
}
if allAttacked {
minCount = countSoFar
storeLayout(piece)
return
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if !isAttacked(piece, i, j) {
board[i][j] = true
diag1Lookup[diag1[i][j]] = true
diag2Lookup[diag2[i][j]] = true
placePiece(piece, countSoFar+1)
board[i][j] = false
diag1Lookup[diag1[i][j]] = false
diag2Lookup[diag2[i][j]] = false
}
}
}
}
func main() {
pieces := []string{"Q", "B", "K"}
limits := map[string]int{"Q": 10, "B": 7, "K": 5}
names := map[string]string{"Q": "Queens", "B": "Bishops", "K": "Knights"}
for _, piece := range pieces {
fmt.Println(names[piece])
fmt.Println("=======\n")
for n = 1; ; n++ {
board = make([][]bool, n)
for i := 0; i < n; i++ {
board[i] = make([]bool, n)
}
diag1 = make([][]int, n)
for i := 0; i < n; i++ {
diag1[i] = make([]int, n)
for j := 0; j < n; j++ {
diag1[i][j] = i + j
}
}
diag2 = make([][]int, n)
for i := 0; i < n; i++ {
diag2[i] = make([]int, n)
for j := 0; j < n; j++ {
diag2[i][j] = i - j + n - 1
}
}
diag1Lookup = make([]bool, 2*n-1)
diag2Lookup = make([]bool, 2*n-1)
minCount = math.MaxInt32
layout = ""
placePiece(piece, 0)
fmt.Printf("%2d x %-2d : %d\n", n, n, minCount)
if n == limits[piece] {
fmt.Printf("\n%s on a %d x %d board:\n", names[piece], n, n)
fmt.Println("\n" + layout)
break
}
}
}
}</lang>
{{out}}
<pre>
Queens
=======
1 x 1 : 1
2 x 2 : 1
3 x 3 : 1
4 x 4 : 3
5 x 5 : 3
6 x 6 : 4
7 x 7 : 4
8 x 8 : 5
9 x 9 : 5
10 x 10 : 5
Queens on a 10 x 10 board:
. . Q . . . . . . .
. . . . . . . . . .
. . . . . . . . Q .
. . . . . . . . . .
. . . . Q . . . . .
. . . . . . . . . .
Q . . . . . . . . .
. . . . . . . . . .
. . . . . . Q . . .
. . . . . . . . . .
Bishops
=======
1 x 1 : 1
2 x 2 : 2
3 x 3 : 3
4 x 4 : 4
5 x 5 : 5
6 x 6 : 6
7 x 7 : 7
Bishops on a 7 x 7 board:
. B . B . . .
. . . B . . .
. . . . . . .
. . B B . . .
. . . . . . .
. . B B . . .
. . . . . . .
Knights
=======
1 x 1 : 1
2 x 2 : 4
3 x 3 : 4
4 x 4 : 4
5 x 5 : 5
Knights on a 5 x 5 board:
K . . . .
. . . . .
. . K K .
. . K K .
. . . . .
</pre>
| |||