N-queens minimum and knights and bishops: Difference between revisions
Content added Content deleted
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: | Line 70: | ||
Place Piece 13 in row 7 column 4 |
Place Piece 13 in row 7 column 4 |
||
Place Piece 14 in row 7 column 7 |
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> |
</pre> |