# -*- coding: utf8 -*-
'''
__author__ = 'dabay.wang@gmail.com' 51: N-Queens
https://oj.leetcode.com/problems/n-queens/ The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement,
where 'Q' and '.' both indicate a queen and an empty space respectively. For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
===Comments by Dabay===
This set of questions is relatively simple , Start with a queen , Then find the next possible location and put the second one ... The trick is “ Find the next possible location ” On ,
- Next position , In fact, in the next line
- When checking if it can be placed , Just check if the column is occupied , And whether diagonal lines are occupied on the left and right respectively .( Because there is no queen down there )
'''
class Solution:
# @return a list of lists of string
def solveNQueens(self, n):
def make_solution(board):
copy = []
for row in board:
row_str = ""
for c in row:
row_str = row_str + c
copy.append(row_str)
return copy def check_up(r, c, queen_stack, board):
i = 1
while i < len(board):
if r-i>=0 and c-i>=0 and board[r-i][c-i]=='Q':
return False
if r-i>=0 and c+i<len(board) and board[r-i][c+i]=="Q":
return False
i = i + 1
else:
return True def find_available_positions(board, queen_stack):
positions = []
row = len(queen_stack)
queen_columns = [pos[1] for pos in queen_stack]
for c in xrange(len(board)):
if c in queen_columns:
continue
if board[row][c] == "." and check_up(row, c, queen_stack, board):
positions.append((row,c))
return positions def DFS(board, queen_stack, res):
if len(queen_stack) >= len(board):
res.append(make_solution(board))
return
positions = find_available_positions(board, queen_stack)
for (r, c) in positions:
queen_stack.append((r, c))
board[r][c] = "Q"
DFS(board, queen_stack, res)
queen_stack.pop()
board[r][c] = "." board = [["."] * n for _ in xrange(n)]
queen_stack = []
res = [] DFS(board, queen_stack, res)
return res def print_board(board):
print '-' * 30
for row in board:
for item in row:
print item,
print
print '-' * 30 def main():
sol = Solution()
solutions = sol.solveNQueens(4)
for solution in solutions:
print_board(solution) if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)

[Leetcode][Python]51: N-Queens More articles about

  1. Leetcode Python Solution(continue update)

    leetcode python solution 1. two sum (easy) Given an array of integers, return indices of the two num ...

  2. LeetCode python Realize the solution of the problem ( Continuous updating )

    Catalog LeetCode Python Introduction to implementation algorithm 0001 Sum of two numbers 0002 Addition of two numbers 0003 Longest substring without repeating characters 0004 Find the median of two ordered arrays 0005 Longest text substring 0006 Z The font changes ...

  3. [Leetcode][Python]52: N-Queens II

    # -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 52: N-Queens IIhttps://oj.leetcode.com/ ...

  4. [LeetCode][Python]Container With Most Water

    # -*- coding: utf8 -*-'''https://oj.leetcode.com/problems/container-with-most-water/ Given n non-neg ...

  5. 【 One day LeetCode】#51. N-Queens

    One day LeetCode series ( One ) subject The n-queens puzzle is the problem of placing n queens on an n×n chessboard suc ...

  6. LeetCode Python Bit operation 1

    Python Bit operation : Bitwise AND &,  Press bit or | I don't know Bitwise XOR ^ num ^ num = 0 Move left << num << 1 == num * 2**1 Move right & ...

  7. 【leetcodepython】Sum Of Two Number

    #-*- coding: UTF-8 -*- # Since you can't use addition and subtraction , Then use bit operation . Let's calculate 5+4 Examples of how to use bit operations to achieve addition :#1. Two addends are represented in binary ,a=5=0101,b=4=0100 ...

  8. [Leetcode][Python]56: Merge Intervals

    # -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 56: Merge Intervalshttps://oj.leetcode. ...

  9. [Leetcode][Python]55: Jump Game

    # -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 55: Jump Gamehttps://leetcode.com/probl ...

Random recommendation

  1. 2.Nginx Optimize

    [ Tutorial topics ]:Nginx Optimize [ Course recording ]: gen E [ primary coverage ] Nginx Optimize nginx Introduce Nginx It's very lightweight, written by Russians HTTP The server ,Nginx, Its pronunciation is "engine ...

  2. js in ,var The difference between modifying variable names and not modifying them

    js in Allows you to define variables No addition var Modifier .js It will find out whether the context defines this variable in the current scope , If not, memory will be allocated for this variable . When and as if window Members of . That's the global variable . If you add va ...

  3. 【vijos1066】 Weak trenches Line segment tree

    describe Eternity and mx Playing a real-time strategy game , Name ~~~~~~ I have a bad memory , Forget -_-b. mx Built around his base n A trench , Each trench is an independent combat unit , The range can reach infinity (“mx It's not going to win ?!?” eternal ...

  4. Code execution bat

    public static void executeBat(String path) {        try {            File file = new File(path);     ...

  5. Use Microsoft Word Post blog posts

    With Microsoft Word 2010 For example : Choose in turn : file  ->  Save and send ->  Post as a blog post Configuration instructions : New account Of Blog posts URL  Fill in one column http://rpc.cn ...

  6. 【Entity Framework 7】 It's a completely different way to play

    http://www.cnblogs.com/n-pei/p/4274907.html

  7. Content based Image Retrieval CBIR(Content Based Image Retrieval) brief introduction

    Traditional image retrieval process , First, manually mark the image , And then use keywords to retrieve images , This method provides the retrieval result according to the character matching degree of image description , abbreviation “ Look for pictures with words ”, Time consuming and subjective . Content based image retrieval “ Look for pictures with words ” The way of ...

  8. 4 Japan 6 Japan --ES5 New array method

    forEach Function calls used , So it takes up a lot of memory , It's better to fix the length for Loops and iterations for loop 1. adopt forEach Represent the elements of an array one by one ( Traversal methods , Read operation ). 2. adopt map Arithmetic the elements in the original array ...

  9. Educational Codeforces Round 63 (Rated for Div. 2)

    Portal A. Reverse a Substring The question : Here's a bunch of s, Let's see if you can reverse the interval [l,r] The elements of , So that the lexicographic order of the inverted string is less than s: If you can , Output "YES", and ...

  10. 【 Reprint 】C# Use regular expressions to check the mailbox

    stay C# in , have access to Regex Regular expression class to verify whether the mailbox field information submitted by the foreground meets the requirements ,Regex Class is C# Related classes about regular expression processing in , Powerful , We just need to instantiate Regex Class, specify the corresponding rule as mailbox ...