Oddy Chessboard
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
On a standard chessboard,
What is the number of different arrangements of pawns such that every square has an odd number of pawns on its neighbor (horizontally or vertically) squares?
Note: diagonals and the square itself is not counted
Note 2: you may count symmetrical or mirrored solutions as well.
If this question was asked for $2$x$2$ board, the answer would be $4$ as below:
and $3$ other symmetric solutions.
logical-deduction combinatorics chess
add a comment |Â
up vote
5
down vote
favorite
On a standard chessboard,
What is the number of different arrangements of pawns such that every square has an odd number of pawns on its neighbor (horizontally or vertically) squares?
Note: diagonals and the square itself is not counted
Note 2: you may count symmetrical or mirrored solutions as well.
If this question was asked for $2$x$2$ board, the answer would be $4$ as below:
and $3$ other symmetric solutions.
logical-deduction combinatorics chess
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
On a standard chessboard,
What is the number of different arrangements of pawns such that every square has an odd number of pawns on its neighbor (horizontally or vertically) squares?
Note: diagonals and the square itself is not counted
Note 2: you may count symmetrical or mirrored solutions as well.
If this question was asked for $2$x$2$ board, the answer would be $4$ as below:
and $3$ other symmetric solutions.
logical-deduction combinatorics chess
On a standard chessboard,
What is the number of different arrangements of pawns such that every square has an odd number of pawns on its neighbor (horizontally or vertically) squares?
Note: diagonals and the square itself is not counted
Note 2: you may count symmetrical or mirrored solutions as well.
If this question was asked for $2$x$2$ board, the answer would be $4$ as below:
and $3$ other symmetric solutions.
logical-deduction combinatorics chess
asked Aug 16 at 14:05


Oray
14.1k435139
14.1k435139
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
4
down vote
accepted
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $mtimes n$ grid, as shown by K. Sutner in The $sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^gcd(m + 1, n + 1) - 1$ if a solution exists, $0$ otherwise.
add a comment |Â
up vote
2
down vote
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
add a comment |Â
up vote
0
down vote
I don't know the answer but have at least found an upper bound of
$2^14 = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn.
Continuing for B2, we know either B3 and C2 are both pawns or neither pawns.
This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states.
Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations.
For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd.
The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each).
This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $mtimes n$ grid, as shown by K. Sutner in The $sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^gcd(m + 1, n + 1) - 1$ if a solution exists, $0$ otherwise.
add a comment |Â
up vote
4
down vote
accepted
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $mtimes n$ grid, as shown by K. Sutner in The $sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^gcd(m + 1, n + 1) - 1$ if a solution exists, $0$ otherwise.
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $mtimes n$ grid, as shown by K. Sutner in The $sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^gcd(m + 1, n + 1) - 1$ if a solution exists, $0$ otherwise.
We can think of this as a linear algebra problem mod $2$. That is, we need to satisfy $Ax=b$ where $A$ is the $64times 64$ adjacency matrix of the chessboard. The vector $x$ stores a $1$ if a pawn is on that square and a $0$ otherwise. Then $b$ is a vector only containing $1$'s, because we want an odd number of adjacent pawns from each square. Then we can find a solution by solving this system of equations over GF(2).
Using a computer (or a lot of spare time by hand), we find that a solution does in fact exist, for example:
x x x x x x x x
- x x x x x x -
x x - - - - x x
- x x - - x x -
x x - - - - x x
- x x x x x x -
x x x x x x x x
- - - - - - - -
We can also determine that the nullity of $A$ is $8$, so there are
$2^8=256$ solutions in total.
How can we describe the entire solution set, you may ask? Well, just put any number of pawns wherever you want on the top row. These act as our $8$ free variables. Then place whatever pawns you need in the second row so that the oddness property is satisfied on the first row. Then place whatever pawns you need in the third row so that the oddness property is satisfied in the second row. Repeat this until you place pawns on the last row and the whole board is a solution. This works for $8times 8$ specifically because there are $8$ free variables.
In general, if you only want the number of solutions, there is a very nice formula for any $mtimes n$ grid, as shown by K. Sutner in The $sigma$-Game and Cellular Automata. See theorem on pg. 28.
$2^gcd(m + 1, n + 1) - 1$ if a solution exists, $0$ otherwise.
edited Aug 16 at 16:17
answered Aug 16 at 15:51


Riley
10.4k43170
10.4k43170
add a comment |Â
add a comment |Â
up vote
2
down vote
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
add a comment |Â
up vote
2
down vote
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
Start by focusing on the black squares.
• • • A
• • C B
• • E D
• G F •
• I H •
K J • •
M L • •
N • • •
A and B must be different (one has a pawn, the other does not), because the upper right corner touches an odd number of pawns. Looking at the square surrounded by A, B, C and D, this means that C and D must be the same (both have pawns, or both do not). Continuing in this fashion, we get the following pattern:
• • • A
• • B a <-- Lower case letters must the opposite of
• • C B corresponding upper case letter.
• D c L
• E D K
F e J • Two same capital letters must be the same.
G F I •
g H • •
From now on, we use mod 2 arithmetic. Give each square a number so squares without pawns are 0 and squares with pawns are 1. Then the neighbors of any square must add to 1 (mod 2). This means that
H = g + F + 1
I = e + F + H + 1 = e + F + (g + F + 1) + 1 = e + g
J = D + e + I + 1 = D + e + (e + g) + 1 = D + g + 1
K = c + D + J + 1 = c + D + (D + g + 1) + 1 = c + g
L = B + c + K + 1 = B + c + (c + g + 1) + 1 = B + g + 1
Finally, considering the white square surrounded by a, B and L, we must have
a + B + L = 1
∴ a + B + (B + g + 1) = 1
∴ a = g
In other words, we have learned that the H, I, J, K, L diagonal is entirely determined by the numbers above it, and we have learned that a and g are constrained to be equal.
By doing similar work on the other diagonals, you can deduce that the grid must look like this:
• • • A
• • B a
• • C B
• D c •
• C D •
B c • •
A B • •
a • • •
where all of the •'s are forced by the choices of A, B, C and D. However, these four variables can be chosen freely, so there are sixteen ways to place the pawns on the black squares. The white pawns can be chosen independently of the black pawns in the same number of ways, for
16 x 16 = 256
ways total.
answered Aug 16 at 15:28


Mike Earnest
20.5k567211
20.5k567211
add a comment |Â
add a comment |Â
up vote
0
down vote
I don't know the answer but have at least found an upper bound of
$2^14 = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn.
Continuing for B2, we know either B3 and C2 are both pawns or neither pawns.
This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states.
Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations.
For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd.
The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each).
This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
add a comment |Â
up vote
0
down vote
I don't know the answer but have at least found an upper bound of
$2^14 = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn.
Continuing for B2, we know either B3 and C2 are both pawns or neither pawns.
This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states.
Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations.
For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd.
The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each).
This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I don't know the answer but have at least found an upper bound of
$2^14 = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn.
Continuing for B2, we know either B3 and C2 are both pawns or neither pawns.
This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states.
Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations.
For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd.
The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each).
This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
I don't know the answer but have at least found an upper bound of
$2^14 = 16384$
My reasoning:
If we start at one of the corners, say A1, we only one of B1 and A2 has a pawn.
Continuing for B2, we know either B3 and C2 are both pawns or neither pawns.
This reasoning can continue till H8 where we have 7 pairs of squares that can be in one of two states.
Adding in the 7 pairs for the other diagonal we get 14 pairs in total, which give us our 16384 combinations.
For each of these combinations we can find a sequence of squares that have one unknown neighbor and fill it with a pawn or not to make numbers odd.
The sequence I used was (C1, D2, D1, and their 7 rotations and mirrors for each, D3, C2, B1, and each of their 3 mirrors for each).
This will fill the rest of the board, however, there are still 12 squares that do not necessarily have an odd number of neighbors (A2, B3, C4, and their 3 mirrors for each in my case). This might rule out some of the 16384 solutions but will not add any more.
answered Aug 16 at 15:30
Bennett Bernardoni
2,073415
2,073415
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f69758%2foddy-chessboard%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password