import copy def take_input(): """Accepts the size of the chess board""" while True: try: size = int(input('What is the size of the chessboard? n = \n')) if size == 1: print("Trivial solution, choose a board size of atleast 4") if size <= 3: print("Enter a value such that size>=4") continue return size except ValueError: print("Invalid value entered. Enter again") def get_board(size): """Returns an n by n board""" board = [0]*size for ix in range(size): board[ix] = [0]*size return board def print_solutions(solutions, size): """Prints all the solutions in user friendly way""" for sol in solutions: for row in sol: print(row) print() def is_safe(board, row, col, size): """Check if it's safe to place a queen at board[x][y]""" #check row on left side for iy in range(col): if board[row][iy] == 1: return False ix, iy = row, col while ix >= 0 and iy >= 0: if board[ix][iy] == 1: return False ix-=1 iy-=1 jx, jy = row,col while jx < size and jy >= 0: if board[jx][jy] == 1: return False jx+=1 jy-=1 return True def solve(board, col, size): """Use backtracking to find all solutions""" #base case if col >= size: return for i in range(size): if is_safe(board, i, col, size): board[i][col] = 1 if col == size-1: add_solution(board) board[i][col] = 0 return solve(board, col+1, size) #backtrack board[i][col] = 0 def add_solution(board): """Saves the board state to the global variable 'solutions'""" global solutions saved_board = copy.deepcopy(board) solutions.append(saved_board) size = take_input() board = get_board(size) solutions = [] solve(board, 0, size) print_solutions(solutions, size) print("Total solutions = {}".format(len(solutions)))
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question