-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
51.py
51 lines (51 loc) · 51.3 KB
/
51.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
__________________________________________________________________________________________________
sample 44 ms submission
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if n == 1:
return [['Q']]
if n == 2:
return []
if n == 3:
return []
if n == 4:
return [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
if n == 5:
return [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
if n == 6:
return [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
if n == 7:
return [["Q......","..Q....","....Q..","......Q",".Q.....","...Q...",".....Q."],["Q......","...Q...","......Q","..Q....",".....Q.",".Q.....","....Q.."],["Q......","....Q..",".Q.....",".....Q.","..Q....","......Q","...Q..."],["Q......",".....Q.","...Q...",".Q.....","......Q","....Q..","..Q...."],[".Q.....","...Q...","Q......","......Q","....Q..","..Q....",".....Q."],[".Q.....","...Q...",".....Q.","Q......","..Q....","....Q..","......Q"],[".Q.....","....Q..","Q......","...Q...","......Q","..Q....",".....Q."],[".Q.....","....Q..","..Q....","Q......","......Q","...Q...",".....Q."],[".Q.....","....Q..","......Q","...Q...","Q......","..Q....",".....Q."],[".Q.....",".....Q.","..Q....","......Q","...Q...","Q......","....Q.."],[".Q.....","......Q","....Q..","..Q....","Q......",".....Q.","...Q..."],["..Q....","Q......",".....Q.",".Q.....","....Q..","......Q","...Q..."],["..Q....","Q......",".....Q.","...Q...",".Q.....","......Q","....Q.."],["..Q....","....Q..","......Q",".Q.....","...Q...",".....Q.","Q......"],["..Q....",".....Q.",".Q.....","....Q..","Q......","...Q...","......Q"],["..Q....","......Q",".Q.....","...Q...",".....Q.","Q......","....Q.."],["..Q....","......Q","...Q...","Q......","....Q..",".Q.....",".....Q."],["...Q...","Q......","..Q....",".....Q.",".Q.....","......Q","....Q.."],["...Q...","Q......","....Q..",".Q.....",".....Q.","..Q....","......Q"],["...Q...",".Q.....","......Q","....Q..","..Q....","Q......",".....Q."],["...Q...",".....Q.","Q......","..Q....","....Q..","......Q",".Q....."],["...Q...","......Q","..Q....",".....Q.",".Q.....","....Q..","Q......"],["...Q...","......Q","....Q..",".Q.....",".....Q.","Q......","..Q...."],["....Q..","Q......","...Q...","......Q","..Q....",".....Q.",".Q....."],["....Q..","Q......",".....Q.","...Q...",".Q.....","......Q","..Q...."],["....Q..",".Q.....",".....Q.","..Q....","......Q","...Q...","Q......"],["....Q..","..Q....","Q......",".....Q.","...Q...",".Q.....","......Q"],["....Q..","......Q",".Q.....","...Q...",".....Q.","Q......","..Q...."],["....Q..","......Q",".Q.....",".....Q.","..Q....","Q......","...Q..."],[".....Q.","Q......","..Q....","....Q..","......Q",".Q.....","...Q..."],[".....Q.",".Q.....","....Q..","Q......","...Q...","......Q","..Q...."],[".....Q.","..Q....","Q......","...Q...","......Q","....Q..",".Q....."],[".....Q.","..Q....","....Q..","......Q","Q......","...Q...",".Q....."],[".....Q.","..Q....","......Q","...Q...","Q......","....Q..",".Q....."],[".....Q.","...Q...",".Q.....","......Q","....Q..","..Q....","Q......"],[".....Q.","...Q...","......Q","Q......","..Q....","....Q..",".Q....."],["......Q",".Q.....","...Q...",".....Q.","Q......","..Q....","....Q.."],["......Q","..Q....",".....Q.",".Q.....","....Q..","Q......","...Q..."],["......Q","...Q...","Q......","....Q..",".Q.....",".....Q.","..Q...."],["......Q","....Q..","..Q....","Q......",".....Q.","...Q...",".Q....."]]
if n == 8:
return [["Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["Q.......",".....Q..",".......Q","..Q.....","......Q.","...Q....",".Q......","....Q..."],["Q.......","......Q.","...Q....",".....Q..",".......Q",".Q......","....Q...","..Q....."],["Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q..","..Q....."],[".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q..."],[".Q......","....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q...."],[".Q......","....Q...","......Q.","...Q....","Q.......",".......Q",".....Q..","..Q....."],[".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q.....","....Q..."],[".Q......",".....Q..",".......Q","..Q.....","Q.......","...Q....","......Q.","....Q..."],[".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q.......","...Q...."],[".Q......","......Q.","....Q...",".......Q","Q.......","...Q....",".....Q..","..Q....."],[".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q.","...Q...."],["..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q","Q.......","......Q.","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q",".....Q..","...Q....","......Q.","Q......."],["..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q.."],["..Q.....","....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q.."],["..Q.....",".....Q..",".Q......","....Q...",".......Q","Q.......","......Q.","...Q...."],["..Q.....",".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q..."],["..Q.....",".....Q..",".Q......","......Q.","....Q...","Q.......",".......Q","...Q...."],["..Q.....",".....Q..","...Q....","Q.......",".......Q","....Q...","......Q.",".Q......"],["..Q.....",".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q......."],["..Q.....",".....Q..",".......Q","Q.......","...Q....","......Q.","....Q...",".Q......"],["..Q.....",".....Q..",".......Q","Q.......","....Q...","......Q.",".Q......","...Q...."],["..Q.....",".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q..."],["..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q....",".....Q.."],["..Q.....","......Q.",".Q......",".......Q",".....Q..","...Q....","Q.......","....Q..."],["..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......","....Q..."],["...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q.....",".....Q.."],["...Q....","Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......"],["...Q....",".Q......","....Q...",".......Q",".....Q..","Q.......","..Q.....","......Q."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","Q.......","....Q..."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q......."],["...Q....",".Q......","......Q.","....Q...","Q.......",".......Q",".....Q..","..Q....."],["...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q.....",".....Q.."],["...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q."],["...Q....",".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q."],["...Q....",".....Q..",".......Q",".Q......","......Q.","Q.......","..Q.....","....Q..."],["...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q...",".Q......"],["...Q....","......Q.","Q.......",".......Q","....Q...",".Q......",".....Q..","..Q....."],["...Q....","......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q.."],["...Q....","......Q.","....Q...",".Q......",".....Q..","Q.......","..Q.....",".......Q"],["...Q....","......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......"],["...Q....",".......Q","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."],["...Q....",".......Q","Q.......","....Q...","......Q.",".Q......",".....Q..","..Q....."],["...Q....",".......Q","....Q...","..Q.....","Q.......","......Q.",".Q......",".....Q.."],["....Q...","Q.......","...Q....",".....Q..",".......Q",".Q......","......Q.","..Q....."],["....Q...","Q.......",".......Q","...Q....",".Q......","......Q.","..Q.....",".....Q.."],["....Q...","Q.......",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["....Q...",".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q."],["....Q...",".Q......","...Q....","......Q.","..Q.....",".......Q",".....Q..","Q......."],["....Q...",".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q....."],["....Q...",".Q......",".......Q","Q.......","...Q....","......Q.","..Q.....",".....Q.."],["....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q....","......Q."],["....Q...","..Q.....","Q.......","......Q.",".Q......",".......Q",".....Q..","...Q...."],["....Q...","..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......"],["....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......"],["....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q..","..Q....."],["....Q...","......Q.",".Q......","...Q....",".......Q","Q.......","..Q.....",".....Q.."],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q"],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......",".......Q","...Q...."],["....Q...","......Q.","...Q....","Q.......","..Q.....",".......Q",".....Q..",".Q......"],["....Q...",".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q."],["....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q..","..Q....."],[".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q.","...Q...."],[".....Q..",".Q......","......Q.","Q.......","..Q.....","....Q...",".......Q","...Q...."],[".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q...","..Q....."],[".....Q..","..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q...."],[".....Q..","..Q.....","Q.......",".......Q","...Q....",".Q......","......Q.","....Q..."],[".....Q..","..Q.....","Q.......",".......Q","....Q...",".Q......","...Q....","......Q."],[".....Q..","..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q"],[".....Q..","..Q.....","....Q...",".......Q","Q.......","...Q....",".Q......","......Q."],[".....Q..","..Q.....","......Q.",".Q......","...Q....",".......Q","Q.......","....Q..."],[".....Q..","..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q...."],[".....Q..","..Q.....","......Q.","...Q....","Q.......",".......Q",".Q......","....Q..."],[".....Q..","...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q....."],[".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q....."],[".....Q..","...Q....","......Q.","Q.......","..Q.....","....Q...",".Q......",".......Q"],[".....Q..","...Q....","......Q.","Q.......",".......Q",".Q......","....Q...","..Q....."],[".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q....."],["......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......","....Q..."],["......Q.",".Q......","...Q....","Q.......",".......Q","....Q...","..Q.....",".....Q.."],["......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q","....Q..."],["......Q.","..Q.....","Q.......",".....Q..",".......Q","....Q...",".Q......","...Q...."],["......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q..","...Q...."],["......Q.","...Q....",".Q......","....Q...",".......Q","Q.......","..Q.....",".....Q.."],["......Q.","...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q..."],["......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q...."],[".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q.....",".....Q.."],[".......Q",".Q......","....Q...","..Q.....","Q.......","......Q.","...Q....",".....Q.."],[".......Q","..Q.....","Q.......",".....Q..",".Q......","....Q...","......Q.","...Q...."],[".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."]]
if n == 9:
return [["Q........","..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q...."],["Q........","..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","...Q.....",".....Q..."],["Q........","..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q....."],["Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q....","......Q.."],["Q........","...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q.."],["Q........","...Q.....",".....Q...",".......Q.",".Q.......","....Q....","..Q......","........Q","......Q.."],["Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q..."],["Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q...","..Q......"],["Q........","...Q.....",".......Q.","..Q......","........Q","......Q..","....Q....",".Q.......",".....Q..."],["Q........","....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q.."],["Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q.....",".......Q."],["Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q..."],["Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......"],["Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["Q........","....Q....","........Q",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","......Q.."],["Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......","....Q...."],["Q........",".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q."],["Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q...."],["Q........",".....Q...",".......Q.","..Q......","......Q..","...Q.....",".Q.......","........Q","....Q...."],["Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......"],["Q........",".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q....."],["Q........","......Q..","...Q.....",".....Q...","........Q",".Q.......","....Q....","..Q......",".......Q."],["Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q.......",".....Q..."],["Q........","......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q...."],["Q........","......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q....."],["Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......","....Q...."],["Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q.......","...Q.....","......Q.."],["Q........",".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q..."],[".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q....",".......Q."],[".Q.......","...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....",".......Q.","..Q......","........Q",".....Q...","Q........","....Q....","......Q.."],[".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....","........Q","......Q..","....Q....","..Q......","Q........",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q.....","........Q"],[".Q.......","....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","........Q","..Q......",".....Q...","...Q.....","Q........",".......Q."],[".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q..."],[".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q..","...Q....."],[".Q.......","....Q....",".......Q.","Q........","........Q",".....Q...","..Q......","......Q..","...Q....."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q.."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q....."],[".Q.......","....Q....","........Q","...Q.....","Q........",".......Q.",".....Q...","..Q......","......Q.."],[".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q.","....Q...."],[".Q.......",".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q"],[".Q.......",".....Q...","Q........","......Q..","....Q....","..Q......","........Q","...Q.....",".......Q."],[".Q.......",".....Q...","Q........","........Q","....Q....",".......Q.","...Q.....","......Q..","..Q......"],[".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q...."],[".Q.......",".....Q...","........Q","..Q......","....Q....",".......Q.","...Q.....","Q........","......Q.."],[".Q.......","......Q..","....Q....","Q........","........Q","...Q.....",".....Q...",".......Q.","..Q......"],[".Q.......","......Q..","....Q....",".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q"],[".Q.......","......Q..","........Q",".....Q...","..Q......","Q........","...Q.....",".......Q.","....Q...."],[".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......","....Q...."],[".Q.......",".......Q.","....Q....","..Q......","........Q",".....Q...","...Q.....","Q........","......Q.."],[".Q.......",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q...."],[".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q..."],[".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....","......Q.."],[".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q.","....Q...."],[".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........","..Q......","....Q....",".......Q."],["..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q..."],["..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q.."],["..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q","....Q...."],["..Q......","Q........","......Q..","....Q....",".......Q.",".Q.......","...Q.....",".....Q...","........Q"],["..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q.......",".....Q..."],["..Q......","Q........","........Q","......Q..","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q..."],["..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q...","........Q"],["..Q......","....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q"],["..Q......","....Q....",".......Q.",".Q.......","........Q",".....Q...","Q........","......Q..","...Q....."],["..Q......","....Q....",".......Q.",".Q.......","........Q","......Q..","Q........","...Q.....",".....Q..."],["..Q......","....Q....","........Q",".Q.......","...Q.....","......Q..","Q........",".......Q.",".....Q..."],["..Q......","....Q....","........Q","...Q.....","Q........","......Q..",".Q.......",".....Q...",".......Q."],["..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q....","........Q"],["..Q......",".....Q...",".Q.......","........Q","....Q....","Q........",".......Q.","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q"],["..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........"],["..Q......",".....Q...",".......Q.","....Q....","Q........","........Q","......Q..",".Q.......","...Q....."],["..Q......",".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........"],["..Q......",".....Q...","........Q","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],["..Q......",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q."],["..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q..","....Q...."],["..Q......",".....Q...","........Q","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q.."],["..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],["..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q...."],["..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q...."],["..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q",".....Q..."],["..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","Q........",".....Q...","...Q....."],["..Q......","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","Q........","....Q....","........Q"],["..Q......","......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q..."],["..Q......","......Q..","...Q.....",".Q.......","........Q",".....Q...","Q........","....Q....",".......Q."],["..Q......","......Q..","...Q.....",".......Q.","....Q....","........Q","Q........",".....Q...",".Q......."],["..Q......","......Q..","........Q","Q........","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........"],["..Q......",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........",".....Q..."],["..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......","....Q....","Q........",".....Q..."],["..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],["..Q......",".......Q.",".....Q...","...Q.....","........Q","Q........","....Q....","......Q..",".Q......."],["..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","Q........","...Q.....","......Q.."],["..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["..Q......","........Q","...Q.....","Q........",".......Q.",".....Q...",".Q.......","......Q..","....Q...."],["..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q..","....Q...."],["..Q......","........Q","...Q.....",".......Q.","....Q....",".Q.......",".....Q...","Q........","......Q.."],["..Q......","........Q",".....Q...",".Q.......","....Q....","......Q..","Q........","...Q.....",".......Q."],["..Q......","........Q",".....Q...","...Q.....","Q........","......Q..","....Q....",".Q.......",".......Q."],["..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q...."],["...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q....","......Q.."],["...Q.....","Q........","....Q....",".Q.......","........Q","......Q..","..Q......",".......Q.",".....Q..."],["...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q"],["...Q.....","Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q.."],["...Q.....","Q........","......Q..","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["...Q.....","Q........","........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q...."],["...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q.."],["...Q.....",".Q.......","......Q..","..Q......","Q........",".......Q.","....Q....","........Q",".....Q..."],["...Q.....",".Q.......","......Q..","........Q","Q........","....Q....",".......Q.",".....Q...","..Q......"],["...Q.....",".Q.......","......Q..","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........",".....Q..."],["...Q.....",".Q.......","........Q","..Q......",".....Q...",".......Q.","Q........","....Q....","......Q.."],["...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......","......Q.."],["...Q.....",".....Q...","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q"],["...Q.....",".....Q...","Q........","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......"],["...Q.....",".....Q...","Q........","........Q","......Q..","..Q......",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q.."],["...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q..","Q........"],["...Q.....",".....Q...","..Q......","........Q","......Q..","Q........",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","Q........","........Q","......Q..","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","......Q..","........Q","Q........","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q"],["...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q.......","........Q"],["...Q.....",".....Q...","........Q","..Q......","Q........",".......Q.",".Q.......","....Q....","......Q.."],["...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","Q........",".....Q...","........Q",".Q.......",".......Q.","....Q....","..Q......"],["...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q..."],["...Q.....","......Q..","..Q......",".....Q...","........Q","Q........",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q...","Q........"],["...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q...."],["...Q.....","......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........"],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........","..Q......",".......Q.",".....Q..."],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......"],["...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......","Q........"],["...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q..."],["...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q."],["...Q.....","......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q......."],["...Q.....",".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q"],["...Q.....",".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q.."],["...Q.....",".......Q.","....Q....","..Q......","Q........","......Q..",".Q.......",".....Q...","........Q"],["...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q."],["...Q.....","........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","......Q.."],["...Q.....","........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q..."],["...Q.....","........Q","....Q....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q.."],["....Q....","Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q.."],["....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......"],["....Q....","Q........",".......Q.",".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q"],["....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q...",".......Q."],["....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q."],["....Q....",".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q."],["....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q..","Q........"],["....Q....",".Q.......",".....Q...","........Q","......Q..","...Q.....","Q........","..Q......",".......Q."],["....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......"],["....Q....",".Q.......",".......Q.","Q........","......Q..","........Q","..Q......",".....Q...","...Q....."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........","........Q",".....Q..."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q","Q........",".....Q...","...Q....."],["....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["....Q....",".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q."],["....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q."],["....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q..","........Q"],["....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q"],["....Q....","..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q.."],["....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......",".......Q."],["....Q....","..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........"],["....Q....","..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q......."],["....Q....","..Q......",".......Q.","...Q.....",".Q.......","........Q",".....Q...","Q........","......Q.."],["....Q....","..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........"],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","Q........","...Q.....","......Q.."],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","......Q..","Q........","...Q....."],["....Q....","..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q.."],["....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q.."],["....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......"],["....Q....","......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......"],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","..Q......","........Q",".....Q..."],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","........Q",".....Q...","..Q......"],["....Q....","......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q"],["....Q....","......Q..",".Q.......",".....Q...",".......Q.","Q........","...Q.....","........Q","..Q......"],["....Q....","......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q."],["....Q....","......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q"],["....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.",".Q......."],["....Q....","......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......"],["....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........"],["....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......","Q........"],["....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q......."],["....Q....",".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q......."],["....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........","........Q","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q","Q........","...Q....."],["....Q....",".......Q.",".Q.......","........Q","..Q......","Q........","......Q..","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q.."],["....Q....",".......Q.","...Q.....","Q........","..Q......",".....Q...","........Q","......Q..",".Q......."],["....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......","........Q"],["....Q....",".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q......."],["....Q....",".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q......."],["....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q.....",".Q......."],["....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........"],["....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q.."],["....Q....","........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......"],[".....Q...","Q........","....Q....",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......"],[".....Q...","Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q....."],[".....Q...","Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.","..Q......"],[".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q......."],[".....Q...",".Q.......","....Q....","......Q..","........Q","..Q......",".......Q.","...Q.....","Q........"],[".....Q...",".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......"],[".....Q...",".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........"],[".....Q...","..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q......."],[".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q....."],[".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q..","........Q"],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q.."],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","......Q..",".Q.......","...Q....."],[".....Q...","..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q"],[".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q...."],[".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q.....","........Q"],[".....Q...","..Q......","......Q..","...Q.....","Q........","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q....."],[".....Q...","..Q......","........Q","...Q.....","Q........",".......Q.",".Q.......","....Q....","......Q.."],[".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],[".....Q...","...Q.....","Q........","......Q..","........Q",".Q.......",".......Q.","....Q....","..Q......"],[".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q.","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","..Q......","Q........","........Q","......Q.."],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","........Q","Q........","..Q......","......Q.."],[".....Q...","...Q.....","......Q..","Q........","..Q......","........Q",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......","........Q"],[".....Q...","...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......"],[".....Q...","...Q.....","........Q","Q........","..Q......","......Q..",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","........Q","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q.."],[".....Q...","...Q.....","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........"],[".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".....Q...",".......Q.","Q........","......Q..","...Q.....",".Q.......","........Q","....Q....","..Q......"],[".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q","....Q....",".Q.......","...Q.....","......Q.."],[".....Q...",".......Q.","..Q......","......Q..","........Q",".Q.......","....Q....","Q........","...Q....."],[".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......"],[".....Q...","........Q","Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q...."],[".....Q...","........Q","..Q......","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],[".....Q...","........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......"],[".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........"],[".....Q...","........Q","....Q....",".......Q.","Q........","..Q......","......Q..",".Q.......","...Q....."],[".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q....","..Q......"],["......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q...."],["......Q..","Q........","...Q.....",".....Q...","........Q","..Q......","....Q....",".......Q.",".Q......."],["......Q..","Q........","...Q.....",".......Q.","....Q....","..Q......","........Q",".....Q...",".Q......."],["......Q..","Q........",".....Q...",".Q.......","....Q....",".......Q.","...Q.....","........Q","..Q......"],["......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......","....Q...."],["......Q..","Q........",".....Q...","........Q",".Q.......","...Q.....",".......Q.","..Q......","....Q...."],["......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q...","...Q....."],["......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","........Q",".....Q...","..Q......"],["......Q..",".Q.......","...Q.....",".....Q...","Q........","........Q","....Q....","..Q......",".......Q."],["......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","....Q....","........Q","...Q....."],["......Q..",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q","...Q....."],["......Q..","..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q"],["......Q..","..Q......","Q........","........Q","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","..Q......",".....Q...",".Q.......","....Q....","Q........","........Q","...Q.....",".......Q."],["......Q..","..Q......",".....Q...",".......Q.","Q........","...Q.....","........Q","....Q....",".Q......."],["......Q..","..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q....."],["......Q..","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","........Q","....Q....","Q........"],["......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........","........Q","...Q.....",".....Q..."],["......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........","...Q....."],["......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q...."],["......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q...."],["......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["......Q..","...Q.....","Q........","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......"],["......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......","....Q...."],["......Q..","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q......."],["......Q..","...Q.....","Q........","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["......Q..","...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q"],["......Q..","...Q.....",".Q.......","....Q....","........Q","Q........","..Q......",".......Q.",".....Q..."],["......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q"],["......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......"],["......Q..","...Q.....",".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........"],["......Q..","...Q.....",".......Q.","Q........","....Q....","........Q",".Q.......",".....Q...","..Q......"],["......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q....","Q........"],["......Q..","....Q....","Q........",".....Q...","........Q","..Q......",".......Q.","...Q.....",".Q......."],["......Q..","....Q....","Q........",".......Q.",".....Q...","..Q......","........Q",".Q.......","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","..Q......","........Q",".....Q...","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","...Q.....","........Q","..Q......",".....Q..."],["......Q..","....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q....."],["......Q..","........Q","Q........","..Q......","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q.","...Q....."],["......Q..","........Q","..Q......","....Q....",".Q.......",".......Q.",".....Q...","...Q.....","Q........"],["......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........","....Q...."],["......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......"],["......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q....."],[".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q","......Q..","....Q....",".Q......."],[".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q.......","....Q...."],[".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...","..Q......"],[".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q....."],[".......Q.",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q...."],[".......Q.",".Q.......","....Q....","......Q..","Q........","...Q.....",".....Q...","........Q","..Q......"],[".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q..","....Q...."],[".......Q.","..Q......","Q........","...Q.....","......Q..","........Q",".....Q...",".Q.......","....Q...."],[".......Q.","..Q......","....Q....",".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........"],[".......Q.","..Q......","....Q....","........Q","Q........",".....Q...","...Q.....",".Q.......","......Q.."],[".......Q.","...Q.....","Q........","......Q..","....Q....",".Q.......",".....Q...","........Q","..Q......"],[".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q...."],[".......Q.","...Q.....","........Q","Q........","....Q....",".Q.......",".....Q...","..Q......","......Q.."],[".......Q.","...Q.....","........Q","..Q......","....Q....","......Q..","Q........",".....Q...",".Q......."],[".......Q.","...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........"],[".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q.......","....Q...."],[".......Q.","....Q....","Q........",".....Q...","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......"],[".......Q.","....Q....",".Q.......","........Q","Q........","...Q.....","......Q..","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......",".....Q..."],[".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q....."],[".......Q.","....Q....","..Q......","Q........","......Q..","...Q.....",".....Q...","........Q",".Q......."],[".......Q.","....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q......."],[".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q...","Q........"],[".......Q.",".....Q...","Q........","..Q......","....Q....","......Q..","........Q","...Q.....",".Q......."],[".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...",".Q.......","......Q..","Q........","...Q.....","........Q","....Q....","..Q......"],[".......Q.",".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q....",".Q......."],["........Q",".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q....."],["........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q.",".....Q...","..Q......"],["........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q..","....Q...."],["........Q","..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["........Q","..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q...."],["........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q.","...Q....."],["........Q","..Q......",".....Q...","...Q.....","Q........",".......Q.","....Q....","......Q..",".Q......."],["........Q","...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q..."],["........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......","......Q.."],["........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q...",".......Q.","Q........","....Q...."],["........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q...."],["........Q","...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q......."],["........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q..","....Q...."],["........Q","....Q....","Q........","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","..Q......"],["........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q.."],["........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q....."],["........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q...",".Q......."],["........Q","....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......"],["........Q",".....Q...",".Q.......","......Q..","Q........","..Q......","....Q....",".......Q.","...Q....."],["........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q.....","......Q.."],["........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q....."],["........Q",".....Q...","...Q.....",".Q.......",".......Q.","....Q....","......Q..","Q........","..Q......"],["........Q",".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......"],["........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q....","..Q......"],["........Q","......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q..."],["........Q","......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........",".....Q...","...Q....."],["........Q","......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q...."]]
__________________________________________________________________________________________________
sample 13020 kb submission
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def is_valid(template: List[int]) -> bool:
row_id = len(template) - 1
for i in range(row_id):
diff = abs(template[i] - template[row_id])
if diff == 0 or diff == row_id - i:
return False
return True
def gen_board_templates(n: int, row: int, template: List[int]) -> List[int]:
if row == n:
yield template
else:
for col in range(n):
template.append(col)
if is_valid(template):
for next_template in gen_board_templates(n, row + 1, template):
yield next_template
template.pop()
board_states = []
for board_template in gen_board_templates(n, 0, []):
board_state = ['.' * n] * n
for col, row in enumerate(board_template):
board_state[row] = board_state[row][:col] + 'Q' + board_state[row][col + 1:]
board_states.append(board_state)
return board_states
__________________________________________________________________________________________________