Chessboard Problems and Domino Puzzles
Invariant Method
A Chessboard Problem
A Bishop can only move along a diagonal
Can a bishop move from its current position to the question mark?
A bishop can only move along a diagonal
Can a bishop move from its current position to the question mark?
Impossible!
Why?
A Chessboard Problem
1.
The
bishop
is in a
red
position.
2.
A
red
position can only move to
a
red
position by diagonal
moves.
3.
The question mark is in a
white
position.
4.
So it is impossible for the
bishop
to go there.
Invariant!
This is a simple example of the invariant method.
A Chessboard Problem
Domino Puzzle
An 8x8 chessboard, 32 pieces of dominos
Can we fill the chessboard?
Domino Puzzle
An 8x8 chessboard, 32 pieces of dominos
Easy!
Domino Puzzle
An 8x8 chessboard with
two holes
,
31
pieces of dominos
Can we fill the chessboard?
Easy!
Domino Puzzle
An 8x8 chessboard with
two holes
,
31
pieces of dominos
Can we fill the chessboard?
Easy??
Domino Puzzle
An 4x4 chessboard with
two holes
,
7
pieces of dominos
Can we fill the chessboard?
Impossible!
Domino Puzzle
An 8x8 chessboard with
two holes
,
31
pieces of dominos
Can we fill the chessboard?
Then what??
Domino Puzzle
An 8x8 chessboard with
two holes
,
31
pieces of dominos
Can we fill the chessboard?
Domino Puzzle
1.
Each domino will occupy one
white square and one
red
square.
2.
There are 32 blue squares but
only 30 white squares.
3.
So it is impossible to fill the
chessboard using only 31
dominos.
Invariant!
This is another example of the invariant method.
Invariant Method
1.
Find properties (the
invariants
) that are satisfied
throughout the whole process.
2.
Show that the target do not satisfy the properties.
3.
Conclude that the target is not achievable.
In the rook example, the invariant is
the colour of the position of the rook.
In the domino example, the invariant is that
any placement of dominos will occupy the same
number of blue positions and white positions.
The Possible
We just proved that if we take out two squares of
the same colour
, then it is impossible to finish.
What if we take out two squares of
different colours
?
Would it be always possible to finish then?
Yes??
Prove the Possible
Yes??
Prove the Possible
The secret.
Prove the Possible
The secret.
Fifteen Puzzle
Move:
can move a square adjacent to the empty square
to the empty square.
Fifteen Puzzle
Initial
configuration
Target
configuration
Is there a sequence of moves that allows you to start
from the
initial
configuration to the
target
configuration?
Invariant Method
1.
Find properties (the
invariants
) that are satisfied
throughout the whole process.
2.
Show that the target do not satisfy the properties.
3.
Conclude that the target is not achievable.
What is an invariant in this game??
This is usually the hardest part of the proof.
Hint
Initial
configuration
Target
configuration
((1,2,3,…,14,15),(4,4))
((1,2,3,…,15,14),(4,4))
Hint:
the
two states have different parity.
Parity
Given a sequence, a pair is
“out-of-order”
if the first element is larger.
For example, the sequence (1,2,4,5,3) has two out-of-order pairs, (4,3) and (5,3).
Given a state S = ((a1,a2,…,a15),(i,j))
Parity of S = (number of out-of-order pairs + row) mod 2
row number of the
empty square
More formally, given a sequence (a
1
,a
2
,…,a
n
),
a pair (i,j) is out-of-order if i<j but a
i
> a
j
.
Hint
Initial
configuration
Target
configuration
((1,2,3,…,14,15),(4,4))
((1,2,3,…,15,14),(4,4))
Clearly, the two states have different parity.
Parity of S = (number of out-of-order pairs + row) mod 2
Invariant Method
1.
Find properties (the
invariants
) that are satisfied
throughout the whole process.
2.
Show that the target do not satisfy the properties.
3.
Conclude that the target is not achievable.
Invariant
= parity of state
Claim:
Any move will preserve the parity of the state.
Proving the claim will finish the impossibility proof.
Parity is even
Parity is odd
Proving the Invariant
Claim:
Any move will preserve the parity of the state.
Parity of S = (number of out-of-order pairs + row) mod 2
Horizontal movement does not change anything…
Proving the Invariant
Claim:
Any move will preserve the parity of the state.
Parity of S = (number of out-of-order pairs + row) mod 2
Row number has
changed by 1
To count the
change
on the number of out-of-order pairs, we can distinguish
4 cases, depending on the relative order of a among (a,b1,b2,b3).
Proving the Invariant
Claim:
Any move will preserve the parity of the state.
Parity of S = (number of out-of-order pairs + row) mod 2
Row number has
changed by 1
Case 1: when a is largest, then the number of out-of-order pairs will
decrease by three, and since the row number is changed by one,
the parity is still the same.
Proving the Invariant
Claim:
Any move will preserve the parity of the state.
Parity of S = (number of out-of-order pairs + row) mod 2
Row number has
changed by 1
Case 2: when a is the second largest, then the number of out-of-order pairs
will decrease by one, and since the row number is changed by one,
the parity is still the same. (The remaining case analysis is the same.)
Proving the Invariant
Claim:
Any move will preserve the parity of the state.
Parity of S = (number of out-of-order pairs + row) mod 2
If there are (0,1,2,3) out-of-order pairs in the current state,
there will be (3,2,1,0) out-of-order pairs in the next state.
Row number has
changed by 1
So the parity stays the same! We’ve proved the
claim
.
Difference
is 1 or 3.
Fifteen Puzzle
Initial
configuration
Target
configuration
Is there a sequence of moves that allows you to start
from the
initial
configuration to the
target
configuration?
Fifteen Puzzle
Initial
configuration
Target
configuration
Number of out-of-order pairs = 0
Row of empty square = 4
Parity is even.
Number of out-of-order pairs
= 14 + 13 + 12 + … + 1
= 14(13)/2 = 91
Row of empty square = 4
Parity is odd.
Impossible!
Fifteen Puzzle
If two configurations have the same parity,
is it true that we can always move from one to another?
YES,
good project idea.
http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf
K=4
x=0
Remember the checker game that we have seen before?
K=5
Sorry there are no slides for this proof.
The proof can be found in “Mathematical Gems II” by Honsberger.
There are three books on Mathematical Gems and all are excellent.
This can also be solved by the invariant method.
Can you cover a 8X8 board with straight trominoes?
No, since the board has 64 squares and each tromino covers 3.
So, lets remove one corner so that the board now has 63 squares.
Can we now, cover with straight trominoes?
Covering with Trominoes
Lets try
Lets try our coloring trick.
Color board so that
each tromino colors 3
different colors
Of the 4 corners, say 2
are red and one each
are blue, yellow
Rotate board so that
missing corner is blue/
yellow
Now we have 22 reds, 21 yellows and 20 blues!!
Remarks and References
Another interesting application of the invariant method is the Nim game.
See http://en.wikipedia.org/wiki/Nim.
Solve chessboard problems and domino puzzles using the invariant method. Discover the logic behind bishop movements, chessboard filling, and domino placements. Learn how invariants provide solutions to complex challenges in chess-related scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Invariant Method 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 1 5 9 10 11 12 13 15 14 2 6 3 7 4 8
A Chessboard Problem A Bishop can only move along a diagonal Can a bishop move from its current position to the question mark? ?
A Chessboard Problem A bishop can only move along a diagonal Can a bishop move from its current position to the question mark? Impossible! ? Why?
A Chessboard Problem Invariant! 1. The bishop is in a red position. 2. A red position can only move to a red position by diagonal moves. ? 3. The question mark is in a white position. 4. So it is impossible for the bishop to go there. This is a simple example of the invariant method.
Domino Puzzle An 8x8 chessboard, 32 pieces of dominos Can we fill the chessboard?
Domino Puzzle An 8x8 chessboard, 32 pieces of dominos Easy!
Domino Puzzle An 8x8 chessboard with two holes, 31 pieces of dominos Can we fill the chessboard? Easy!
Domino Puzzle An 8x8 chessboard with two holes, 31 pieces of dominos Can we fill the chessboard? Easy??
Domino Puzzle An 4x4 chessboard with two holes, 7 pieces of dominos Can we fill the chessboard? Impossible!
Domino Puzzle An 8x8 chessboard with two holes, 31 pieces of dominos Can we fill the chessboard? Then what??
Domino Puzzle An 8x8 chessboard with two holes, 31 pieces of dominos Can we fill the chessboard?
Domino Puzzle Invariant! 1. Each domino will occupy one white square and one red square. 2. There are 32 blue squares but only 30 white squares. 3. So it is impossible to fill the chessboard using only 31 dominos. This is another example of the invariant method.
Invariant Method 1. Find properties (the invariants) that are satisfied throughout the whole process. 2. Show that the target do not satisfy the properties. 3. Conclude that the target is not achievable. In the rook example, the invariant is the colour of the position of the rook. In the domino example, the invariant is that any placement of dominos will occupy the same number of blue positions and white positions.
The Possible We just proved that if we take out two squares of the same colour, then it is impossible to finish. What if we take out two squares of different colours? Would it be always possible to finish then? Yes??
Prove the Possible Yes??
Prove the Possible The secret.
Prove the Possible The secret.
Fifteen Puzzle 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 Move: can move a square adjacent to the empty square to the empty square.
Fifteen Puzzle 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 1 5 9 10 11 12 13 15 14 2 6 3 7 4 8 Target configuration Initial configuration Is there a sequence of moves that allows you to start from the initial configuration to the target configuration?
Invariant Method 1. Find properties (the invariants) that are satisfied throughout the whole process. 2. Show that the target do not satisfy the properties. 3. Conclude that the target is not achievable. What is an invariant in this game?? This is usually the hardest part of the proof.
Hint 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 1 5 9 10 11 12 13 15 14 2 6 3 7 4 8 Target configuration Initial configuration ((1,2,3, ,15,14),(4,4)) ((1,2,3, ,14,15),(4,4)) Hint: the two states have different parity.
Parity Given a sequence, a pair is out-of-order if the first element is larger. More formally, given a sequence (a1,a2, ,an), a pair (i,j) is out-of-order if i<j but ai> aj. For example, the sequence (1,2,4,5,3) has two out-of-order pairs, (4,3) and (5,3). Given a state S = ((a1,a2, ,a15),(i,j)) Parity of S = (number of out-of-order pairs + row) mod 2 row number of the empty square
Hint 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 1 5 9 10 11 12 13 15 14 2 6 3 7 4 8 Target configuration Initial configuration ((1,2,3, ,15,14),(4,4)) ((1,2,3, ,14,15),(4,4)) Parity of S = (number of out-of-order pairs + row) mod 2 Clearly, the two states have different parity.
Invariant Method Parity is even 1. Find properties (the invariants) that are satisfied throughout the whole process. 2. Show that the target do not satisfy the properties. 3. Conclude that the target is not achievable. Parity is odd Invariant = parity of state Claim: Any move will preserve the parity of the state. Proving the claim will finish the impossibility proof.
Proving the Invariant Parity of S = (number of out-of-order pairs + row) mod 2 Claim: Any move will preserve the parity of the state. ? ? ? ? ? a ? ? ? ? ? ? ? ? ? ? ? ? ? a ? ? ? ? ? ? ? ? ? ? Horizontal movement does not change anything
Proving the Invariant Parity of S = (number of out-of-order pairs + row) mod 2 Claim: Any move will preserve the parity of the state. ? ? ? a b1 b2 ? ? ? ? ? ? ? ? ? ? b1 b2 ? ? b3 ? ? ? b3 a ? ? ? Row number has changed by 1 ? To count the change on the number of out-of-order pairs, we can distinguish 4 cases, depending on the relative order of a among (a,b1,b2,b3).
Proving the Invariant Parity of S = (number of out-of-order pairs + row) mod 2 Claim: Any move will preserve the parity of the state. ? ? ? a b1 b2 ? ? ? ? ? ? ? ? ? ? b1 b2 ? ? b3 ? ? ? b3 a ? ? ? Row number has changed by 1 ? Case 1: when a is largest, then the number of out-of-order pairs will decrease by three, and since the row number is changed by one, the parity is still the same.
Proving the Invariant Parity of S = (number of out-of-order pairs + row) mod 2 Claim: Any move will preserve the parity of the state. ? ? ? a b1 b2 ? ? ? ? ? ? ? ? ? ? b1 b2 ? ? b3 ? ? ? b3 a ? ? ? Row number has changed by 1 ? Case 2: when a is the second largest, then the number of out-of-order pairs will decrease by one, and since the row number is changed by one, the parity is still the same. (The remaining case analysis is the same.)
Proving the Invariant Parity of S = (number of out-of-order pairs + row) mod 2 Claim: Any move will preserve the parity of the state. ? ? ? a b1 b2 ? ? ? ? ? ? ? ? ? ? b1 b2 ? ? b3 ? ? ? b3 a ? ? ? Row number has changed by 1 ? Difference is 1 or 3. If there are (0,1,2,3) out-of-order pairs in the current state, there will be (3,2,1,0) out-of-order pairs in the next state. So the parity stays the same! We ve proved the claim.
Fifteen Puzzle 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 15 14 13 12 11 10 9 7 6 3 2 8 4 5 1 Target configuration Initial configuration Is there a sequence of moves that allows you to start from the initial configuration to the target configuration?
Fifteen Puzzle 1 5 9 10 11 12 13 14 15 2 6 3 7 4 8 15 14 13 12 11 10 9 7 6 3 2 8 4 5 1 Target configuration Initial configuration Number of out-of-order pairs = 0 Number of out-of-order pairs = 14 + 13 + 12 + + 1 = 14(13)/2 = 91 Row of empty square = 4 Parity is even. Row of empty square = 4 Parity is odd. Impossible!
Fifteen Puzzle If two configurations have the same parity, is it true that we can always move from one to another? YES, good project idea. http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf
K=4 x=0 Remember the checker game that we have seen before?
K=5 This can also be solved by the invariant method. Sorry there are no slides for this proof. The proof can be found in Mathematical Gems II by Honsberger. There are three books on Mathematical Gems and all are excellent.
Covering with Trominoes Can you cover a 8X8 board with straight trominoes? No, since the board has 64 squares and each tromino covers 3. So, lets remove one corner so that the board now has 63 squares. Can we now, cover with straight trominoes?
Lets try our coloring trick. Color board so that each tromino colors 3 different colors Of the 4 corners, say 2 are red and one each are blue, yellow Rotate board so that missing corner is blue/ yellow Now we have 22 reds, 21 yellows and 20 blues!!
Remarks and References Another interesting application of the invariant method is the Nim game. See http://en.wikipedia.org/wiki/Nim.
