[אתגר קשה] חידת N המלכות

חידת שמונה המלכות היא חידת שחמט שבה יש למקם שמונה מלכות שחמט על לוח שחמט כך שאף אחת מהן לא מאיימת על אף אחת מחברותיה. החידה היא מקרה פרטי של בעיית n המלכות, בעיה דומה בה יש להציב n מלכות על לוח בגודל n x n‏.
לחידה 92 פתרונות: 12 יסודיים, ומהם מקבלים בעזרת שיקוף וסיבוב הלוח את שאר הפתרונות.
– ויקיפדיה

פתרו את בעית N המלכות בעזרת פייתון.

טיפ: זהו תרגיל קשה, אבל מגה מוכר ופופולרי ויש אינסוף פתרונות אליו באינטרנט. אל תחפשו את הפתרונות, לפתור אותו (גם אם ייקח לכם כמה ימים) זו גאווה קטנה :slight_smile: להסתכל על פתרון יגרום תחושת החמצה כל פעם שתשמעו את החידה הזו בעתיד :stuck_out_tongue:

6 לייקים

״לחידה 92 פתרונות״ - הכוונה לדרכי פתרון ?
או הכוונה היא92 העמדות עבור 8 המלכות על לוח של 8*8

מפחד להיכנס לויקיפדיה שלא אראה את התשובה

לייק 1

הכוונה למספר הסידורים האפשריים של 8 מלכות על לוח של 8X8.
בשנה שעברה זכרתי בעל פה גם את כל מספרי הסידורים של לוחות מגודל iXi מ-1 עד 10 או 11 אבל ההדחקה עשתה את שלה בסוף :see_no_evil: :sweat_smile:

5 לייקים

אחרי כמה שעות של חשיבה אשמח לביקורת:
עשיתי שבסופו של דבר אקבל רשימה של רשימות - כל רשימה קטנה מורכבת מטאפלים שכל טאפל מרכיב איפה מלכה נמצאת - האיבר הראשון הוא השורה, האיבר השני הוא הטור, כך שבסופו של דבר רשימה קטנה מורכבת מ-n טאפלים (למעשה כל טאפל עוקב הוא השורה הבאה - הם מסודרים לפי שורות)

BOARD_SIZE = 8 # Can get any "Native" number

# Checks if a move is legal
def is_legal(board, move):
    row_move = move[0]
    col_move = move[1]
    for row, col in board:
        if col == col_move or abs(row - row_move) == abs(col - col_move):
            return False
    return True

# Returns each time a turn that is valid
def make_turn(board, row, col, results):
    move = (row, col)
    if len(board) == BOARD_SIZE and board not in results:
        return board
    if len(board) == 0 and col == BOARD_SIZE:
        return False
    if col == BOARD_SIZE or board in results:
        last_move = board.pop()
        return make_turn(board, len(board), last_move[1]+1, results)
    if is_legal(board, move):
        board.append(move)
        return make_turn(board, row+1, 0, results)
    return make_turn(board, row, col+1, results)

# Returns the final results - each time starts from the last move
def queens(board, results):
    new_result = make_turn(board, 0, 0, results)
    if new_result != False:
        new_result_c = new_result.copy()
        results.append(new_result_c)
        return queens(new_result, results)
    return results

print(len(queens([], [])))
לייק 1

זה נראה מצוין :slight_smile:
עכשיו נסה להחזיר את התוצאות בלי סיבובים/השתקפויות :stuck_out_tongue:

זה לא פשוט לעבור עד אורך הלוח חלקי 2?

לייק 1

מישהו יכול להגיד לי אם זה יעבוד?