A "superqueen" is a chess queen that also moves like a knight.
Place four superqueens on a five-by-five board so that no piece attacks another.
If you solve this, try arranging 10 superqueens on a 10-by-10 board so that no piece attacks another.
Both solutions are unique if rotations and reflections are ignored.
by Hilario Fernandez Long.
The ordinary Queens problem is typically used in introducing computer students to the power of recursive programming. The Superqueens problem adds an extra wrinkle.
Part 1:
1's mark the locations of the superqueens, and 0's empty squares:
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 1 0 0 0
This same tableau was actually shown multiple times--once for each position of the superqueen left out ot the middle column. The mirror image was avoided by not allowing the first-column superqueen to be lower than the middle row.
DefDbl A-Z
Dim crlf$, board As Variant, n, emptycol
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
n = 5
ReDim board(-n To n * 2, -n To n * 2)
For emptycol = 1 To n
addOn 1
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub addOn(col)
DoEvents
If col = 1 Then mx = -Int(-n / 2) Else mx = n
For row = 1 To mx
good = 1
If col <> emptycol Then
board(row, col) = 1
For c = 1 To col - 1
If board(row, c) Then good = 0: Exit For
If board(row - (col - c), c) Then good = 0: Exit For
If board(row + (col - c), c) Then good = 0: Exit For
Next
If board(row - 1, col - 2) Then good = 0
If board(row + 1, col - 2) Then good = 0
If board(row - 2, col - 1) Then good = 0
If board(row + 2, col - 1) Then good = 0
End If
If good Then
If col = n Then
For r = 1 To n
For c = 1 To n
Text1.Text = Text1.Text & Str(board(r, c))
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf
Else
addOn (col + 1)
End If
End If
board(row, col) = 0
Next
End Sub
Part 2:
With appropriate modification (n=10 and no empty column):
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
which are reflections of each other. Reflections were avoided in the first instance, by not having the queen in column 1 be below midlevel. Here, the reflected tableau has the queen in column 1 also above midlevel, so the restriction didn't rule out the reflection.
|
|
Posted by Charlie
on 2015-12-31 15:16:31 |
computer solutions
