N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 11:15, 13 May 2022
, 2 years ago→{{header|Wren}}: Improvements in line with Go example.
m (→{{header|Go}}: Moved some code.) |
(→{{header|Wren}}: Improvements in line with Go example.) |
||
Line 1,619:
=={{header|Wren}}==
{{libheader|Wren-fmt}}
Although far quicker than it was originally (it now gets to 7 knights in less than a minute), it struggles after that and needs north of 26 minutes to get to 10.
▲It's based on the Java code [https://www.geeksforgeeks.org/minimum-queens-required-to-cover-all-the-squares-of-a-chess-board/ here] which uses a backtracking algorithm and which I extended to deal with bishops and knights as well as queens when translating to Wren. I've used the more efficient way for checking the diagonals described [https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ here].
<lang ecmascript>import "./fmt" for Fmt
Line 1,632:
var minCount
var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
Line 1,641:
diag2Lookup[diag2[row][col]]) return true
} else if (piece == "B") {
if (diag1Lookup[diag1[row][col]] ||
diag2Lookup[diag2[row][col]]) return true
Line 1,656 ⟶ 1,655:
}
return false
}
var attacks = Fn.new { |piece, row, col, trow, tcol|
if (piece == "Q") {
return row == trow || col == tcol || (row-trow).abs == (col-tcol).abs
} else if (piece == "B") {
return (row-trow).abs == (col-tcol).abs
} else { // piece == "K"
var rd = (trow - row).abs
var cd = (tcol - col).abs
return (rd == 1 && cd == 2) || (rd == 2 && cd == 1)
}
Line 1,668 ⟶ 1,679:
var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar, maxCount|
if (countSoFar >= minCount) return
var allAttacked = true
var ti = 0
var tj = 0
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
allAttacked = false
ti = i
tj = j
break
}
Line 1,685 ⟶ 1,700:
return
}
var sj
for (i in si...n)
for
board[i][j] =
diag2Lookup[diag2[i][j]] = true
placePiece.call(piece, countSoFar + 1, maxCount)
board[i][j] = false
if (piece != "K") {
diag1Lookup[diag1[i][j]] = false
diag2Lookup[diag2[i][j]] = false
}
}
}
}
}
Line 1,700 ⟶ 1,725:
}
var start = System.clock
var pieces = ["Q", "B", "K"]
var limits = {"Q": 10, "B":
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
Line 1,710 ⟶ 1,736:
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
}
diag2 = List.filled(n, null)▼
for (j in 0...n) diag2[i][j] = i - j + n - 1
}
diag2Lookup = List.filled(2*n-1, false)
}
▲ diag2 = List.filled(n, null)
▲ for (i in 0...n) {
▲ diag2[i] = List.filled(n, 0)
▲ for (j in 0...n) diag2[i][j] = i - j + n - 1
▲ }
▲ diag1Lookup = List.filled(2*n-1, false)
▲ diag2Lookup = List.filled(2*n-1, false)
minCount = Num.maxSafeInteger
layout = ""
placePiece.call(piece, 0, maxCount)
if (minCount <= n*n) break
Fmt.print("$2d x $-2d : $d", n, n, minCount)
if (n == limits[piece]) {
Line 1,733 ⟶ 1,764:
n = n + 1
}
}
System.print("Took %(System.clock - start) seconds.")</lang>
{{out}}
Line 1,773 ⟶ 1,805:
5 x 5 : 5
6 x 6 : 6
7 x 7 : 7
8 x 8 : 8
9 x 9 : 9
10 x 10 : 10
Bishops on a
. . .
. . . B . B . . . .
. . . B . B . B . .
B . .
. . . . . . . . . .
. . . . . B . . . . ▼
. . . . . B . . . . ▼
. . . . . B . . . . ▼
Knights
Line 1,791 ⟶ 1,831:
4 x 4 : 4
5 x 5 : 5
6 x 6 : 8
7 x 7 : 13
8 x 8 : 14
9 x 9 : 14
10 x 10 : 16
Knights on a
. . K K . . . . . .
. . K K . . . K K .
. . . . . . . K K .
. . . . . . . . . .
. . . . . . K K . .
. . . . . . . . . .
Took 1583.020941 seconds.
▲Q . . . . . . .
▲. . Q . . . . .
▲. . . . Q . . .
▲. Q . . . . . .
▲. . . Q . . . .
▲. . . . . . . .
▲. . . . . . . .
▲. . . . . . . .
</pre>
| |||