N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 22:31, 23 April 2022
, 2 years agoAdded Wren
Thundergnat (talk | contribs) m (Thundergnat moved page N-Queens minimum and Knights and Bishops to N-queens minimum and knights and bishops: Capitalization policy) |
(Added Wren) |
||
Line 70:
Place Piece 13 in row 7 column 4
Place Piece 14 in row 7 column 7
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
Although this seems to work and give the correct answers, it's very slow indeed taking just under 5.5 minutes to run even when the board sizes are limited to 8 x 8 (queens), 6 x 6 (bishops) and 5 x 5 (knights).
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.
<lang ecmascript>import "./fmt" for Fmt
var board
var n
var minCount
var layout
var isAttacked = Fn.new { |piece, row, col|
if (piece == "Q") {
for (i in 0...n) {
if (board[i][col] || board[row][i]) return true
}
for (i in 0...n) {
if (row-i >= 0 && col-i >= 0 && board[row-i][col-i]) return true
if (row-i >= 0 && col+i < n && board[row-i][col+i]) return true
if (row+i < n && col-i >= 0 && board[row+i][col-i]) return true
if (row+i < n && col+i < n && board[row+i][col+i]) return true
}
} else if (piece == "B") {
if (board[row][col]) return true
for (i in 0...n) {
if (row-i >= 0 && col-i >= 0 && board[row-i][col-i]) return true
if (row-i >= 0 && col+i < n && board[row-i][col+i]) return true
if (row+i < n && col-i >= 0 && board[row+i][col-i]) return true
if (row+i < n && col+i < n && board[row+i][col+i]) 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
}
var storeLayout = Fn.new { |piece|
var sb = ""
for (row in board) {
for (cell in row) sb = sb + (cell ? piece + " " : ". ")
sb = sb + "\n"
}
layout = sb
}
var placePiece // recursive function
placePiece = Fn.new { |piece, countSoFar|
if (countSoFar >= minCount) return
var allAttacked = true
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
allAttacked = false
break
}
}
if (!allAttacked) break
}
if (allAttacked) {
minCount = countSoFar
storeLayout.call(piece)
return
}
for (i in 0...n) {
for (j in 0...n) {
if (!isAttacked.call(piece, i, j)) {
board[i][j] = true
placePiece.call(piece, countSoFar + 1)
board[i][j] = false
}
}
}
}
var pieces = ["Q", "B", "K"]
var limits = {"Q": 8, "B": 5, "K": 4}
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"}
for (piece in pieces) {
System.print(names[piece])
System.print("=======\n")
n = 1
while (true) {
board = List.filled(n, null)
for (i in 0...n) board[i] = List.filled(n, false)
minCount = Num.maxSafeInteger
layout = ""
placePiece.call(piece, 0)
Fmt.print("$2d x $-2d : $d", n, n, minCount)
if (n == limits[piece]) {
Fmt.print("\n$s on a $d x $d board:", names[piece], n, n)
System.print("\n" + layout)
break
}
n = n + 1
}
}</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
Queens on a 8 x 8 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
Bishops on a 6 x 6 board:
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>
| |||