8 מלכות

8 מלכות

מלכים :) (guest) 04 Aug 2014 10:26

שלום : רציתי לשאול לגביי שאלה 2 במבחן זה השאלה עם ה8 מלכות.

דרך א שחשבתי עליה היא לקחת שורה מסויימת כל פעם ולבדוק האם בהמשך קיימת שורה שהמלכה בה נמצאת באותו טור יחד עם המלכה בשורה שבחרתי. אם כן אז התמורה אינה מלכותית

אחר כך לבדוק האם קיימת שורה בהמשך ככה שהמיקום של המלכה עבורה הוא באלכסון (להלן הקוד ככה שבדקתי כל פעם האם מישהו באלכסון )

def foo(lst):
    for i in range(len(lst)):
        a=lst[i]
        for j in range (i+1,len(lst)):
            if lst[j]==a:# אותה עמודה הפסד ודאי בשחמט
                return False
            cheek=j-i
            if lst[j]==a+cheek or lst[j]==a-cheek:# אלכסון הפסד וודאי
                return False
        return True

חבר שלי מהכיתה הציע לי לעשות את הבדיקה הראשונה אבל הבדיקה השניה לדעתו לא נכונה ולא מספיקה הוא בכלל ממליץ לי כל פעם לבדוק האם קיימים בתמורה שני איברים שההפרש שלהם זהה. אם כן הוא טוען שהיא לא מלכותית כי במלכויתית אין דב כזה שלשני איברים לא משנה מה המיקום שלהם יהיה הפרש זהה…

אני לא יודע מי צודק?

האם הדרך שלי כשרה?
ומה עם הדרך שלו?

תודה :D

Re: 8 מלכות

Amir Rubinstein 07 Aug 2014 11:19

האם מה שחברך הציע זה לא בדיוק מה שאתה עושה?

guest (guest) 18 Jan 2015 20:45

Hi,
Regarding this question, there is no need to check that there is another queen in the same column (because of the fact that the permutation is a one-on-one function, so only i=>pi(i)) or the same line (because i goes to pi(i)).
So I only need to check diagonals, correct ?
what is the most efficient way to check it ? is there a way to outperform O(n**2) ?

thanks