N-queens minimum and knights and bishops: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Improved method for checking diagonals.) |
|||
Line 420: | Line 420: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Although this seems to work and give the correct answers, it's very slow |
Although this seems to work and give the correct answers, it's very slow taking about 23.5 minutes to run even when the board sizes are limited to 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. |
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 |
<lang ecmascript>import "./fmt" for Fmt |
||
var board |
var board |
||
var diag1 |
|||
var diag2 |
|||
var diag1Lookup |
|||
var diag2Lookup |
|||
var n |
var n |
||
var minCount |
var minCount |
||
Line 435: | Line 439: | ||
if (board[i][col] || board[row][i]) return true |
if (board[i][col] || board[row][i]) return true |
||
} |
} |
||
if (diag1Lookup[diag1[row][col]] || |
|||
diag2Lookup[diag2[row][col]]) 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") { |
} else if (piece == "B") { |
||
if (board[row][col]) return true |
if (board[row][col]) return true |
||
if (diag1Lookup[diag1[row][col]] || |
|||
diag2Lookup[diag2[row][col]]) 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" |
} else { // piece == "K" |
||
if (board[row][col]) return true |
if (board[row][col]) return true |
||
Line 490: | Line 486: | ||
return |
return |
||
} |
} |
||
for (i in 0...n) { |
for (i in 0...n) { |
||
for (j in 0...n) { |
for (j in 0...n) { |
||
if (!isAttacked.call(piece, i, j)) { |
if (!isAttacked.call(piece, i, j)) { |
||
board[i][j] = true |
board[i][j] = true |
||
diag1Lookup[diag1[i][j]] = true |
|||
diag2Lookup[diag2[i][j]] = true |
|||
placePiece.call(piece, countSoFar + 1) |
placePiece.call(piece, countSoFar + 1) |
||
board[i][j] = false |
board[i][j] = false |
||
diag1Lookup[diag1[i][j]] = false |
|||
diag2Lookup[diag2[i][j]] = false |
|||
} |
} |
||
} |
} |
||
Line 503: | Line 502: | ||
var pieces = ["Q", "B", "K"] |
var pieces = ["Q", "B", "K"] |
||
var limits = {"Q": |
var limits = {"Q": 10, "B": 6, "K": 5} |
||
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"} |
var names = {"Q": "Queens", "B": "Bishops", "K": "Knights"} |
||
for (piece in pieces) { |
for (piece in pieces) { |
||
Line 512: | Line 511: | ||
board = List.filled(n, null) |
board = List.filled(n, null) |
||
for (i in 0...n) board[i] = List.filled(n, false) |
for (i in 0...n) board[i] = List.filled(n, false) |
||
diag1 = List.filled(n, null) |
|||
for (i in 0...n) { |
|||
diag1[i] = List.filled(n, 0) |
|||
for (j in 0...n) diag1[i][j] = i + j |
|||
⚫ | |||
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 |
minCount = Num.maxSafeInteger |
||
layout = "" |
layout = "" |
||
Line 538: | Line 549: | ||
7 x 7 : 4 |
7 x 7 : 4 |
||
8 x 8 : 5 |
8 x 8 : 5 |
||
9 x 9 : 5 |
|||
10 x 10 : 5 |
|||
Queens on a |
Queens on a 10 x 10 board: |
||
Q . . . . . . . |
. . Q . . . . . . . |
||
. . |
. . . . . . . . . . |
||
. . . . |
. . . . . . . . Q . |
||
. |
. . . . . . . . . . |
||
. . . Q . . . . |
. . . . Q . . . . . |
||
. . . . . . . . |
. . . . . . . . . . |
||
. . . . . . . . |
Q . . . . . . . . . |
||
. . . . . . . . |
. . . . . . . . . . |
||
. . . . . . Q . . . |
|||
. . . . . . . . . . |
|||
Bishops |
Bishops |
||
Line 585: | Line 600: | ||
. . K K . |
. . K K . |
||
. . . . . |
. . . . . |
||
</pre> |
|||
If I limit the board size for the queens to 8 x 8, the run time comes down to around 2 minutes 12 seconds and the following example layout is produced: |
|||
<pre> |
|||
Queens on a 8 x 8 board: |
|||
Q . . . . . . . |
|||
. . Q . . . . . |
|||
. . . . Q . . . |
|||
. Q . . . . . . |
|||
. . . Q . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
</pre> |
</pre> |