Eight Queens Problem, error in printing list

[snl_9527]

import time , random
#eight_queen problem
board_sz = 15
direction = [(1,1),(-1,-1),(1,-1),(-1,1)]
data = [ [0 for _ in range(board_sz) ] for _ in range(board_sz) ]

def print_lines(sz):
    for line in sz:
        print(line)

def judge(data):
    #Determine if it is a diagonal and column or row
    find = False
    for row in range(board_sz):
        for col in range(board_sz):
            if data[row][col] != 1:
                continue
            else:
                for dirc in direction:
                    (dx,dy) = dirc
                    new_row,new_col = row + dx , col + dy
                    while 0<= new_row <board_sz and 0 <= new_col < board_sz:
                        if data[new_row][new_col] == 1:
                            find = True
                            return find
                        new_row += dx
                        new_col += dy


def trim(queen):
    board = [[0 for _ in range(board_sz)] for _ in range(board_sz)]
    for (row,col) in enumerate(queen):
        board[row][col] = 1
    return board

def current_solution():
    num = 0
    tries = 0
    start_time = time.time()
    while num  < 10:
        tries += 1
        queen = [i for i in range(board_sz)]
        random.shuffle(queen)
        new_data = trim(queen[:])
        find = judge(new_data)
        if not find:
            end_time = time.time()
            print(f'time used：{(end_time - start_time)*1000:.2f} ms')
            print(f'try {tries} times，found the correct solution：{queen}')
            tries = 0
            num += 1
            start_time = end_time
            print_lines(new_data)
            print()




current_solution()

[Gribouillis]

The problem is that you always shuffle the same list. You need to append a copy of the list. This copy won't be affected by further calls to shuffle

correct_solution.append(lst[:])

[snl_9527]

The problem is that you always shuffle the same list. You need to append a copy of the list. This copy won't be affected by further calls to shuffle

correct_solution.append(lst[:])

Your meaning is that shuffle does not create a new list, right?

[Gribouillis]

Your meaning is that shuffle does not create a new list, right?

Exactly. The documentation says that shuffle() shuffles the sequence in place. It also says that you could use

new_lst = sample(lst, len(lst))

but I think copying the list when you append it to the result is just as good.

Also note that this way of generating the solutions of the eight queens problem is inefficient. Your program will examine many non-solutions. You could try to write a deterministic algorithm. I remember the 8 queens problem was one of the first computer programs I ever wrote back in the early 80s. I coded it in UCSD Pascal then.

[snl_9527]

Your meaning is that shuffle does not create a new list, right?

Exactly. The documentation says that shuffle() shuffles the sequence in place. It also says that you could use

new_lst = sample(lst, len(lst))

but I think copying the list when you append it to the result is just as good.

Thank you, your solution is correct. I still need to look at the technical documentation to deepen my understanding. Thank you again.

[Gribouillis]

Also note that this way of generating the solutions of the eight queens problem is inefficient. Your program will examine many non-solutions. You could try to write a deterministic algorithm. I remember the 8 queens problem was one of the first computer programs I ever wrote back in the early 80s. I coded it in UCSD Pascal then.

[snl_9527]

Also note that this way of generating the solutions of the eight queens problem is inefficient. Your program will examine many non-solutions. You could try to write a deterministic algorithm. I remember the 8 queens problem was one of the first computer programs I ever wrote back in the early 80s. I coded it in UCSD Pascal then.

Yes, I understand that this approach is inefficient. I tried a 20x20 chessboard, and my computer froze. Since I am currently learning and have not yet been exposed to more efficient and concise algorithms, this is the only clumsy method I could come up with.

[snl_9527]

Also note that this way of generating the solutions of the eight queens problem is inefficient. Your program will examine many non-solutions. You could try to write a deterministic algorithm. I remember the 8 queens problem was one of the first computer programs I ever wrote back in the early 80s. I coded it in UCSD Pascal then.

I am not a student in the mathematics or computer science department, so I am somewhat lacking in the ability to abstract such problems.。I am currently reading the open-source book from the Python community, 《How to Think Like a Computer Scientist》 ，I'm not sure if this book is suitable for a beginner with no programming experience...

[Gribouillis]

I am not a student in the mathematics or computer science department, so I am somewhat lacking in the ability to abstract such problems.。I am currently reading the open-source book from the Python community, 《How to Think Like a Computer Scientist》 ，I'm not sure if this book is suitable for a beginner with no programming experience...

This book was written specifically for beginners. It has a very long history, I think the first version used the Lisp language. It is perfectly suitable if you have no experience.

[snl_9527]

I am not a student in the mathematics or computer science department, so I am somewhat lacking in the ability to abstract such problems.。I am currently reading the open-source book from the Python community, 《How to Think Like a Computer Scientist》 ，I'm not sure if this book is suitable for a beginner with no programming experience...

This book was written specifically for beginners. It has a very long history, I think the first version used the Lisp language. It is perfectly suitable if you have no experience.

Are you still here? I have another problem that I haven't solved. The exercises in the book ask me to find the family solutions of the eight queens problem. Wiki says that there are eight family solutions in total, but I have only found seven (x, y mirroring, origin, 90, 180, 270 rotation). How is the other solution generated? With my current ability, I cannot take another step. If you have time, you can take a look at my updated code, find the error and give criticism. I would be very grateful if you could help me in your busy schedule.