All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Safety from the queen (Posted on 2002-12-12) Difficulty: 2 of 5
ABCDE
1
2
3
4
5
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)

See The Solution Submitted by Raveen    
Rating: 3.4615 (13 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution and proof | Comment 16 of 17 |

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


  Posted by Ken Haley on 2004-09-27 01:17:54
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information