Eight Queens
You are given a chessboard of size
8x8. Your task is to place eight queens on the chessboard in such a way that no two queens are attacking each other. Two queens are considered to be attacking each other if they share the same row, column, or diagonal on the chessboard. The chessboard contains both free squares (.) and reserved squares (*), and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.Determine the total number of possible ways to place the queens on the chessboard without violating the constraint of non-attacking queens.
Input
The input consists of eight lines, each containing eight characters. Each character represents a square on the chessboard. A period (
.) represents a free square and an asterisk (*) represents a reserved square.Output
Print a single integer, representing the number of possible ways you can place the eight queens on the chessboard without any two queens attacking each other.
Examples
Input | Output |
........
........
..*.....
........
......*.
........
...*....
........ | 72 |
........
........
.......
........
........
.....**.
.......
........ | 65 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB