N-Piece Problem Flashcards
nxn board with n pieces (21 cards)
When the pieces are the same, how many solutions are there?
No constraints
Pieces can stack, be in the same row/column/diagonal
Fewer than n^2n
When the pieces are the different, how many solutions are there?
No constraint
Pieces can stack, be in the same row/column/diagonal
n^2 * n^2 * … * n^2 = n^2n
When the pieces are the same, how many solutions are there?
Pieces cannot stack
C(n^2, n)
When the pieces are different, how many solutions are there?
Pieces cannot stack
C(n^2, n) n!
When the pieces are the same, how many solutions are there?
Pieces must be in different rows
n * n * … * n = n^n
When the pieces are different, how many solutions are there?
Pieces in different rows
n^n n!
When the pieces are the same, how many solutions are there?
Pieces in different rows and columns
n * (n-1) * (n-2) * … *1 = n!
When the pieces are different, how many solutions are there?
Pieces in different rows and columns
n! n! = (n!)^2
What is a Brute Force approach to solving this problem?
Create all possible assignments, iteratively check if the assignments follow the constraints
When could the Bruce Force approach be useful?
If you only need one solution to the problem
What is the Algorithmic approach to this problem called?
Searching a State Space
What is the approach for one solution?
Fast forward to the first solution, i.e. make choices that favor reaching the solution
What is the approach for ALL solutions?
Prune as many branches as possible, i.e. make choices that favor breaking constraints
What is the goal of Search State Space?
An efficient, methodical search through the complete and partial state spaces
What is the most efficient approach for Search State Space?
Checking constraints with previously assigned pieces
What is the first thing that happens IN THE CODE when solving the n-piece problem?
Check if done, and attempt the next assignment j = a[i] + 1
What happens if j > n-1?
The placement for i is reset, we backtrack to the previous row
What happens if the current placement conflicts with a previous one?
Move to the next column placement
What happens when i >= n-1?
We’ve reached the last row, increase the complete counter EVEN IF THERE ARE CONFLICTS
Log the solution ONLY IF there are no conflicts
What happens if we want ALL the solutions?
Log the current solution, and continue looping
What is this kind of search algorithm called?
Exhaustive Search
