Rosetta Code

N-queens minimum and knights and bishops: Difference between revisions

Page Discussion

N-queens minimum and knights and bishops (view source)

Revision as of 08:19, 13 May 2022

4,816 bytes removed ,  2 years ago
→‎{{header|Go}}: Consolidated the two existing versions and tweaked a little more.
m (→‎Quick hack [temp]: coupla typos)
(→‎{{header|Go}}: Consolidated the two existing versions and tweaked a little more.)
Line 125:
 
=={{header|Go}}==
This was originally a translation of the Wren entry but was substantially improved by [[User:Petelomax|Pete Lomax]] using suggestions from the talk page and has been tweaked a little more since then.
{{trans|Wren}}
Much quicker, of course, than Wren itself - only takes about 35 seconds to run when using the same board limits.
 
A lot of time here is spent processing the 10 x 10 board for bishops. If bishops are limited to a 9 x 9 board, then the overall time falls to 31.4 seconds or, if one simply limits the placing of the bishops to a single row (or column) at or near the middle of the board, then 5 more seconds can be knocked off that.
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.
 
Timings are for an Intel Core i7-8565U machine running Ubuntu 20.04.
<lang go>package main
 
Line 135 ⟶ 136:
"math"
"strings"
"time"
)
 
Line 154 ⟶ 156:
}
} else if piece == "B" {
if board[row][col] {
return true
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
Line 192 ⟶ 191:
}
 
func storeLayoutabs(piecei stringint) int {
varif sbi strings.Builder< 0 {
for _, row := rangei board= {-i
for _, cell := range row {
if cell {
sb.WriteString(piece + " ")
} else {
sb.WriteString(". ")
}
}
sb.WriteString("\n")
}
layoutreturn = sb.String()i
}
 
func placePieceattacks(piece string, countSoFarrow, col, trow, tcol int) bool {
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>
=== Quick hack [temp] ===
Above with my (--[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]])) suggestions applied, but not optimising bishops, so I've kept that at 9 (w/should drop to 49s or so, as-is 10B clocks in at 3m44s)
<lang go>package main
import (
"fmt"
"math"
"strings"
"time"
)
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" {
forreturn irow :== 0;trow i|| <col n;== i++tcol || abs(row-trow) == {abs(col-tcol)
if board[i][col] || board[row][i] {
return true
}
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else if piece == "B" {
ifreturn board[abs(row][col]-trow) {== abs(col-tcol)
return true
}
if diag1Lookup[diag1[row][col]] || diag2Lookup[diag2[row][col]] {
return true
}
} else { // piece == "K"
ifrd board[row][col]:= {abs(trow - row)
cd := abs(tcol - return truecol)
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
}
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 abs(i int) int {
if i<0 { i = -i }
return i
}
 
func Attacks(piece string, row, col, trow, tcol int) bool {
if piece == "Q" {
return (row==trow) || (col==tcol) || (abs(row-trow)==abs(col-tcol))
} else if piece == "B" {
return abs(row-trow)==abs(col-tcol)
} else { // piece == "K"
rd := abs(trow-row)
cd := abs(tcol-col)
return (rd==1 && cd==2) || (rd==2 && cd==1)
}
}
func storeLayout(piece string) {
var sb strings.Builder
Line 450 ⟶ 224:
layout = sb.String()
}
 
func placePiece(piece string, countSoFar, maxCount int) {
//func placePiece(piece string, countSoFar int) {
if countSoFar >= minCount {
return
Line 477 ⟶ 250:
return
}
if countSoFar <= maxCount {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if !isAttacked(piece, i, j) {
if (i == ti && j == tj) || Attacksattacks(piece, i, j, ti, tj) {
board[i][j] = true
diag1Lookup[diag1[i][j]]if piece != true"K" {
diag2Lookup diag1Lookup[diag2diag1[i][j]] = true
// placePiece(piece, countSoFar+1) diag2Lookup[diag2[i][j]] = true
}
placePiece(piece, countSoFar+1, maxCount)
board[i][j] = false
diag1Lookup[diag1[i][j]]if piece != false"K" {
diag2Lookup diag1Lookup[diag2diag1[i][j]] = false
diag2Lookup[diag2[i][j]] = false
}
}
}
Line 497 ⟶ 272:
}
}
 
func main() {
start := time.Now()
pieces := []string{"Q", "B", "K"}
limits := map[string]int{"Q": 10, "B": 910, "K": 10}
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++ {
 
for n = 1; ; n++ {
board = make([][]bool, n)
for i := 0; i < n; i++ {
board[i] = make([]bool, n)
}
diag1if piece != make([][]int,"K" n){
for i := 0; idiag1 <= make([][]int, n; i++ {)
diag1[for i] := make([]int,0; i < n); i++ {
for j := 0; jdiag1[i] <= make([]int, n; j++ {)
diag1[i][for j] := i0; +j < n; j++ {
diag1[i][j] = i + j
}
}
} diag2 = make([][]int, n)
diag2 for i := make([][]int,0; i < n); i++ {
for i := 0; i < n; diag2[i++] {= make([]int, n)
diag2[i] for j := make([]int,0; j < n); j++ {
for diag2[i][j] := 0;i - j <+ n; j++- {1
diag2[i][j] = i - j + n - 1}
}
diag1Lookup = make([]bool, 2*n-1)
diag2Lookup = make([]bool, 2*n-1)
}
diag1Lookup = make([]bool, 2*n-1)
diag2Lookup = make([]bool, 2*n-1)
minCount = math.MaxInt32
layout = ""
// placePiece(piece, 0)
for maxCount := 1; maxCount <= n*n; maxCount++ {
placePiece(piece, 0, maxCount)
if minCount <= n*n {
break
}
Line 547 ⟶ 322:
}
elapsed := time.Now().Sub(start)
fmt.Printf(" (this tookTook %s)\n\n", elapsed)
}</lang>
 
{{out}}
<pre>
Line 567 ⟶ 343:
Queens on a 10 x 10 board:
 
. . Q . . . . . . .
. . . . . . . . . .
. . . . . . . . Q .
. . . . . . . . . .
. . . . Q . . . . .
. . . . . . . . . .
Q . . . . . . . . .
. . . . . . . . . .
. . . . . . Q . . .
. . . . . . . . . .
 
Bishops
Line 590 ⟶ 366:
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10
 
Bishops on a 910 x 910 board:
 
B . B. . . . . . . B
. . . . . B. . . . .
. . . B .B B B . . .
. . . . . . . . . .
. . . . . . . . . .
. . . B. B. . . . . .
. . . . .B B . . . .
. . . B. B. . . . . .
. . . . .B B . . . .
. . . . . . . . . .
 
Knights
Line 619 ⟶ 397:
Knights on a 10 x 10 board:
 
. . . . . . . . . .
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . . . . .
. K K . . . . . . .
. K K . . . K K . .
. . . . . . K K . .
. . . . . . . . . .
 
Took 1m48.35390296s
(this took 1m1.7084192s)
</pre>
 
PureFox
9,479

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/320641"