Consider a 5 by 5 Chess Board. Is it possible to place
5 Queens on the board such that three pawns can safely
be placed on the board? (aka, by carefully choosing where
to place the 5 queens, can you arrange it so that there
are 3 squares on the board that none of the queens can
attack)
(From - http://www.princeton.edu/~sjmiller/riddles/riddles.html)
Jen's solution is correct, and not counting rotations and reflections (which would yield 7 more solutions), this answer is unique.
Here's a VB.Net program that does an exhaustive search, displaying all 8 solutions (reflections and rotations of the original one):
Module Module1
Dim board(24) As Integer
Dim diagonal(13) As String
Sub Main()
'board values: 0 = empty, not attacked, 1 - queen, 2 = attacked.
Dim i As Integer
Dim j As Integer
diagonal(0) = ",1,5,"
diagonal(1) = ",2,6,10,"
diagonal(2) = ",3,7,11,15,"
diagonal(3) = ",4,8,12,16,20,"
diagonal(4) = ",9,13,17,21,"
diagonal(5) = ",14,18,22,"
diagonal(6) = ",19,23,"
diagonal(7) = ",3,9,"
diagonal(8) = ",2,8,14,"
diagonal(9) = ",1,7,13,19,"
diagonal(10) = ",0,6,12,18,24,"
diagonal(11) = ",5,11,17,23,"
diagonal(12) = ",10,16,22,"
diagonal(13) = ",15,21,"
'place the queens
For i = 0 To 4
board(i) = 1
Next
While AdvanceAQueen()
If UnattackedSquareCount() > 2 Then
For i = 0 To 4
For j = 0 To 4
Console.Write(board(i * 5 + j))
Next
Console.WriteLine()
Next
Console.WriteLine()
End If
End While
Console.ReadLine()
End Sub
Function AdvanceAQueen() As Boolean
'searching backwards from square 24 find the first queen with an available square after it, and advance it.
' then place all subsequent queens (if any) immediately after the one we moved, and free up all squares
' from there to the end.
Dim queenNumber As Integer = 5 'this is the ordinal number of the queen we're advancing (usually the last).
Dim i As Integer
Dim foundAnOpening As Boolean = False
For i = 24 To 0 Step -1
If board(i) = 1 And Not foundAnOpening Then
queenNumber -= 1
If queenNumber < 1 Then
'all 5 queens are in the last 5 positions on the board--can't advance; we're done.
Return False
Exit Function
End If
ElseIf board(i) <> 1 And Not foundAnOpening Then
foundAnOpening = True
ElseIf board(i) = 1 Then
board(i) = 0
For k As Integer = queenNumber To 5
i += 1
board(i) = 1
Next
For j As Integer = i + 1 To 24
board(j) = 0
Next
Exit For
End If
Next
Return True
End Function
Function UnattackedSquareCount() As Integer
Dim i As Integer
Dim j As Integer
Dim k As Integer
'clear all squares with no queen
For i = 0 To 24
If board(i) <> 1 Then board(i) = 0
Next
'set the attacked squares.
For i = 0 To 24
If board(i) = 1 Then
For j = 0 To 24
If board(j) <> 1 Then
If j Mod 5 = i Mod 5 Then
board(j) = 2 'same column
ElseIf Int(i / 5) = Int(j / 5) Then
board(j) = 2 'same row
Else
'are i and j in the same diagonal?
For k = 0 To 13
If diagonal(k).IndexOf("," & i.ToString & ",") > -1 _
And diagonal(k).IndexOf("," & j.ToString & ",") > -1 Then
board(j) = 2
Exit For
End If
Next
End If
End If
Next
End If
Next
'now count unattacked squares
k = 0
For i = 0 To 24
If board(i) = 0 Then k += 1
Next
Return k
End Function
End Module
Solution and proof
