Coins on a Chessboard
Tags: javascript, algorithms, tutorial, computerscience
Published: 2020-07-09 03:44:19

# Introduction
Recently I've discovered the concept of error detecting/correcting codes and have been fascinated. Specifically I read an article here about the [Luhn algorithm](https://en.wikipedia.org/wiki/Luhn_algorithm) the other day. 

{% post divyajyotiuk/credit-card-number-check-4cf8 %}

And even more fascinating to me was this video from [3blue1brown](https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw).

{% youtube wTJI_WuZSwE %}

This problem is fascinating to me for so many reasons, especially how it can be rewritten as a graph theory problem. I won't be diving into the many different ways to write or solve this problem, but I encourage you to watch his video if you're interested.
# The Chessboard Problem
In case you don't wanna watch the whole video, I'll summarize the problem posed.

- There are 3 people involved in this scenario two prisoners and a warden.
- The warden takes prisoner 1 to a room with a chessboard, the chessboard has a coin on every square.
- The warden is able to flip any coins he wants over, and hide a key under one coin.
- Prisoner 1, knowing where the key is, is allowed to flip over one coin in an attempt to relay the keys position to prisoner 2.
- No other information or hints may be left by prisoner 1, he is escorted out of the room and prisoner 2 enters.
- Prisoner 2 is allowed to pick up one coin to find the key, if he finds the key their freedom is assured, if not they are stuck in prison.
- If the prisoners are allowed to strategize before attempting the puzzle, is it possible to relay the position of the key to the other prisoner?

# The Solution
While it would be tricky to do by hand (entirely feasible, but tedious), writing a program to find a solution is fairly simple. I thought I would share my implementation and how I worked through it.

To solve this problem I'm going to start with an example of a 2x2 chessboard, every position on the checkerboard is going to be assigned a unique index.

|||
|--|--|
|0|1|
|2|3|

The problem doesn't actually need a 2D grid to be solved, we can just as easily work it out if we flatten the above array:

|||||
|--|--|--|--|
|0|1|2|3|

For the sake of matching the original problem, I will mostly display the table in 2d format.

It's also important to note that all of these numbers can be written in binary.

|||
|--|--|
|00|01|
|10|11|

Next we can represent the board state in terms of heads and tails, or true and false.

|||
|--|--|
|Heads|Heads|
|Heads|Tails|

For our notation the above layout will match the following representation.

|||
|--|--|
|True|True|
|True|False|

Before we can find a way to send information by flipping a coin, we need a way to turn our board state into a message for the other prisoner. If we look at all the spots on the board that are heads up, we get the positions `{00, 01, 10}` while `{11}` is tails. If we XOR all of the positions in the heads up positions we get `00 XOR 01 XOR 10 -> 11` meaning the message prisoner 2 would receive is position 11.

We now need a way to send a specific message, let's say the warden hides the key position `10`.  We need to flip one and only one coin to change the message from `11` to `10`, to do this we find the differing bits `11 XOR 10 -> 01` and flip the resulting coin.

So our board state goes from:

|||
|--|--|
|True|**True**|
|*True*|False|

To:

|||
|--|--|
|True|**False**|
|True|False|

After flipping the coin prisoner 1 can leave and allow prisoner to decode the message using the previously described method. 
1. The heads up coins are in positions `{00, 10}` 
2. XOR all heads up coins: `00 XOR 10 -> 10`
3. Look under the resulting coin (`10 -> 3`) to find the key

This method extends to larger boards, with some caveats I will explain later.

We will expand to a 4x4 for another example. The positions are going to be assigned as follows:

|||||
|--|--|--|--|
|0000|0001|0010|0011|
|0100|0101|0110|0111|
|1000|1001|1010|1011|
|1100|1101|1110|1111|

The warden flips coins to give this board:

|||||
|--|--|--|--|
|False|False|*False*|True|
|False|True|False|False|
|True|False|True|False|
|True|False|False|False|

Then the warden hides the key in position `0010`.

Prisoner 1 takes the following steps to flip a coin over:

1. Find all positions that are heads up: `{0011, 0101, 1000, 1010, 1100}`
2. XOR all positions: `0011 XOR 0101 XOR 1000 XOR 1010 XOR 1100 -> 1000`
3. Find different bits between the keys position and the current message: `0010 XOR 1000 -> 1010`
4. Flip the coin at position `1010`

The new board state is:

|||||
|--|--|--|--|
|False|False|*False*|True|
|False|True|False|False|
|True|False|**False**|False|
|True|False|False|False|

Prisoner 2 takes the following steps to decode the message:

1. Find all positions that are heads up: `{0011, 0101, 1000, 1100}`
2. XOR all positions: `0011 XOR 0101 XOR 1000 XOR 1100 -> 0010`
3. Look under the coin in position `0010`

# The Implementation
To implement, there are 5 individual functions we will implement:
- `randomBoard(n)`
	- returns randomized `n` x `n` board of coins
- `randomPosition(board)`
	- returns random position on `board` in the format `{i: int, j: int}`
- `decodeBoard(board, target=0)`
	- returns result of XOR operations on all true values on `board` as well as the `target` parameter
- `whatCoinToFlip(board, target)`
	- returns position of coin to flip to encode `target` on the `board` in the form `{i: int, j: int}`
- `flipCoin(board, target)`
	- return a deep copy of `board` where the coin at `target` is flipped
- `findKey(board)`
	- return position in the form `{i: int, j: int}` of key given a `board` that has the proper message encoded.

## randomBoard(n)
```javascript
function randomBoard(n) {
	let board = [];
	for (let i = 0; i < n; i++) {
		board.push([]);
		for(let j = 0; j < n; j++) {
			board[i].push(Math.random() > .5);
		}
	}
	return board;
}
```
All this function does is initialize an array, push `n` arrays into it then push `n` random boolean values into all of those.

We can also test it using `console.table(board)` which will allow us to view our board in a very attractive way.

```javascript
let board = randomBoard(4);
console.table(board);
```
```
┌─────────┬──────┬───────┬───────┬───────┐
│ (index) │  0   │   1   │   2   │   3   │
├─────────┼──────┼───────┼───────┼───────┤
│    0    │ true │ false │ true  │ true  │
│    1    │ true │ true  │ false │ true  │
│    2    │ true │ true  │ true  │ false │
│    3    │ true │ true  │ false │ false │
└─────────┴──────┴───────┴───────┴───────┘
```

## randomPosition(board)
```javascript
function randomPosition({length}) {
	return {
		i: random(length),
		j: random(length)
	};
	function random(max) {
		return  Math.floor(Math.random() * max);
	}
}
```
Javascript doesn't have a built in random function that takes a range, so I just wrote a small random function to make it more readable to me. Our indexes i and j line up with the boards row and column respectively. Simply returning two random numbers constrained to the boards length is enough.

Also, rather than calling board.length, it's easier to destructure the object and just get length in the function parameters.
```javascript
let board = randomBoard(4);
let keyLocation = randomPosition(board);
console.log(keyLocation);
```
```
key:  { i: 3, j: 2 }
```
## decodeBoard(board, target=0);
```javascript
function decodeBoard(board, target=0) {
	return board.flat().reduce((cum, val, idx) => cum ^ (val * idx), target);
}
```
First I'm going to flatten the array because 1D arrays are easier to iterate over, from here we can proceed with reduce. Using javascript reduce to XOR all elements of an array is pretty trivial, the trick here is `val * idx` will be 0 whenever `val` is false. Because when it tries to do multiplication the `True` value will act is if it is `1` and `False` will act as if it is a `0`. I can see how this might be viewed as bad practice, however I think it makes the code look pretty nice in this case.

I'm also using target as the starting point of our accumulator, since `target` is 0 by default it will decode the board normally if not given anything. However, if we give it a value it will also XOR that value, this allows us to pass an extra parameter to get the coin we need to flip to get a specific value encoded.
```javascript
let board = randomBoard(4);
console.table(board);
let val = decodeBoard(board);
console.log(val);
```
```
┌─────────┬──────┬───────┬───────┬───────┐
│ (index) │  0   │   1   │   2   │   3   │
├─────────┼──────┼───────┼───────┼───────┤
│    0    │ true │ false │ true  │ true  │
│    1    │ true │ false │ false │ true  │
│    2    │ true │ true  │ true  │ false │
│    3    │ true │ true  │ false │ false │
└─────────┴──────┴───────┴───────┴───────┘
8
```
## whatCoinToFlip(board, target) 
```javascript
function whatCoinToFlip(board, {i, j}) {
	let target = i * board.length + j
	let pos = decodeBoard(board, target);

	return {
		i: Math.floor(pos / board.length),
		j: pos % board.length
	};
}
```
I'm using the same destructuring trick as earlier (in `randomPosition`) to just get i and j from the target passed in. Then we need to convert the row column indexes to our mapping we laid out in the solution part of the post. It will be the same as an index in the flattened array, so we can use `i * board.length + j`

We can then decode the board, passing in the extra parameter to get the specific coin we need to flip.

We can then convert the index on a 1D array to a position on a 2D array and return it.
```javascript
let board = randomBoard(4);
console.table(board);
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
```
```
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ false │ false │ false │ true  │
│    2    │ true  │ false │ true  │ false │
│    3    │ true  │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 3, j: 1 }
flip over the coin at { i: 1, j: 1 }
```
## flipCoin(board, target)
```javascript
function flipCoin(board, {i, j}) {
	let newBoard = board.map((arr) => arr.slice());
	newBoard[i][j] = !newBoard[i][j];
	return newBoard;
}
```
While this may be a somewhat unnecessary addition as I can always just change board itself, I wanted to avoid mutations as much as possible, so I'm returning a new array. The array is also always going to be 2D, so the copy can be made by using map, where every array in the board is mapped to a copy.

Then, we make the change at position `[i][j]` and return the newBoard.
```javascript
let board = randomBoard(4);
console.table(board);
let locationToFlip = randomPosition(board);
console.log("Flipping coin at", locationToFlip);
board = flipCoin(board, locationToFlip);
console.table(board);
```
```
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ false │ false │
│    1    │ true  │ false │ false │ true  │
│    2    │ true  │ true  │ false │ true  │
│    3    │ false │ false │ false │ false │
└─────────┴───────┴───────┴───────┴───────┘
Flipping coin at { i: 2, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ false │ false │
│    1    │ true  │ false │ false │ true  │
│    2    │ true  │ true  │ false │ false │
│    3    │ false │ false │ false │ false │
└─────────┴───────┴───────┴───────┴───────┘
```
## findKey(board)
```javascript
function findKey(board) {
	let pos = decodeBoard(board);

	return {
		i: Math.floor(pos / board.length),
		j: pos % board.length
	};
}
```
This function is very simple as we only need to decode the board, and then convert the 1D index to a 2D index and return it.
```javascript
let board = randomBoard(4);
console.table(board);
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
board = flipCoin(board, flipLocation);
console.table(board);
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
```
```
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ false │
│    1    │ true  │ false │ true  │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ false │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 1, j: 0 }
flip over the coin at { i: 0, j: 0 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ true  │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ false │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is at { i: 1, j: 0 }
```

# Conclusion
Now after putting everything together we are left with a fairly concise program that can simulate and solve the puzzle.
```javascript
function randomBoard(n) {
	let board = [];
	for (let i = 0; i < n; i++) {
		board.push([]);
		for(let j = 0; j < n; j++) {
			board[i].push(Math.random() > .5);
		}
	}
	return board;
}
  
function randomPosition({length}) {
	return {
		i: random(length),
		j: random(length)
	};
	  
	function random(max) {
		return  Math.floor(Math.random() * max);
	}
}
  
function whatCoinToFlip(board, {i, j}) {
	let target = i * board.length + j
	let pos = decodeBoard(board, target);
	  
	return {
		i: Math.floor(pos / board.length),
		j: pos % board.length
	};
}
  
function flipCoin(board, {i, j}) {
	let newBoard = board.map((arr) => arr.slice());
	newBoard[i][j] = !newBoard[i][j];
	return newBoard;
}
  
function findKey(board) {
	let pos = decodeBoard(board);
	  
	return {
		i: Math.floor(pos / board.length),
		j: pos % board.length
	};
}
	  
function decodeBoard(board, target=0) {
	return board.flat().reduce((cum, val, index) => cum ^ (val * index), target);
}
  
// generate new board
let board = randomBoard(4);
console.table(board);
  
// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
  
// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
  
// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);
  
// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
```
```
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ false │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ true  │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 0, j: 0 }
flip over the coin at { i: 3, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ false │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┘
The key is at { i: 0, j: 0 }
```
Pretty cool right? the program also changes pretty easily to larger boards, lets try it with n=8 since the original problem wanted a chessboard.
```javascript
// generate new board
let board = randomBoard(8);
console.table(board);
  
// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
  
// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
  
// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);
  
// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
```
```
┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
│    1    │ false │ true  │ false │ false │ true  │ false │ false │ false │
│    2    │ false │ true  │ true  │ false │ true  │ true  │ true  │ true  │
│    3    │ true  │ false │ true  │ false │ false │ true  │ false │ true  │
│    4    │ true  │ false │ true  │ true  │ true  │ false │ true  │ true  │
│    5    │ false │ true  │ false │ false │ true  │ false │ true  │ false │
│    6    │ false │ true  │ false │ false │ false │ true  │ false │ false │
│    7    │ false │ false │ true  │ false │ false │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 5, j: 5 }
flip over the coin at { i: 7, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
│    1    │ false │ true  │ false │ false │ true  │ false │ false │ false │
│    2    │ false │ true  │ true  │ false │ true  │ true  │ true  │ true  │
│    3    │ true  │ false │ true  │ false │ false │ true  │ false │ true  │
│    4    │ true  │ false │ true  │ true  │ true  │ false │ true  │ true  │
│    5    │ false │ true  │ false │ false │ true  │ false │ true  │ false │
│    6    │ false │ true  │ false │ false │ false │ true  │ false │ false │
│    7    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is at { i: 5, j: 5 }
```
Lastly I wanted to jump back to something I mentioned briefly, there are some caveats to this scaling up, I was very intentional in using `n=2`, `n=4` and `n=8`. these can all be written in the form of n=2<sup>k</sup>, since our algorithm is relies on flipping over a specific coin derived from repeated XOR operations there needs to actually be a coin for every possible value using `2k` bits. So its impossible to solve a 9 x 9 board as we need 7 bits to represent numbers `n > 63`, however there is no coin for any `n > 81` such as `93 -> 1011101`

We can even try this odd board size and see an error occur as the index it tries to find is out of bounds
```
┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │   8   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ true  │ false │ false │ false │ false │ true  │ false │ false │
│    1    │ false │ true  │ true  │ true  │ false │ false │ false │ false │ false │
│    2    │ true  │ true  │ true  │ true  │ false │ false │ false │ true  │ true  │
│    3    │ false │ true  │ false │ false │ false │ true  │ false │ true  │ false │
│    4    │ true  │ false │ false │ false │ false │ false │ true  │ true  │ false │
│    5    │ true  │ true  │ false │ false │ true  │ false │ false │ false │ true  │
│    6    │ true  │ false │ false │ false │ false │ true  │ false │ false │ false │
│    7    │ false │ true  │ false │ true  │ false │ true  │ false │ true  │ true  │
│    8    │ true  │ false │ false │ true  │ true  │ true  │ true  │ false │ true  │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 1, j: 3 }
flip over the coin at { i: 12, j: 3 }
TypeError: Cannot read property '3' of undefined
    at flipCoin (/home/runner/ChessBoardProblem/index.js:35:32)
    at /home/runner/ChessBoardProblem/index.js:65:9
    at Script.runInContext (vm.js:131:20)
    at Object.<anonymous> (/run_dir/interp.js:156:20)
    at Module._compile (internal/modules/cjs/loader.js:1133:30)    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1153:10)
    at Module.load (internal/modules/cjs/loader.js:977:32)
    at Function.Module._load (internal/modules/cjs/loader.js:877:14)
    at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main
.js:74:12)
```

It is entirely possible however, for some non-square boards, such as a 2 x 32 which will use all 5 bit numbers or an 8 x 16 board using all 7 bit numbers. As long as the total number of coins can be written in the form `n=2^k`

Rewriting some code we can generalize it for n x m boards.
```javascript
function randomBoard(n, m) {
	let board = [];
	for (let i = 0; i < n; i++) {
		board.push([]);
		for(let j = 0; j < m; j++) {
			board[i].push(Math.random() > .5);
		}
	}
	return board;
}
  
function randomPosition({length, [0]: {length: width}}) {
	return {
		i: random(length),
		j: random(width)
	};
	  
	function random(max) {
		return  Math.floor(Math.random() * max);
	}
}
  
function whatCoinToFlip(board, {i, j}) {
	let target = i * board[0].length + j
	let pos = decodeBoard(board, target);
	  
	return {
		i: Math.floor(pos / board[0].length),
		j: pos % board[0].length
	};
}
  
function flipCoin(board, {i, j}) {
	let newBoard = board.map((arr) => arr.slice());
	newBoard[i][j] = !newBoard[i][j];
	return newBoard;
}
  
function findKey(board) {
	let pos = decodeBoard(board);
	  
	return {
		i: Math.floor(pos / board[0].length),
		j: pos % board[0].length
	};
}
  
function decodeBoard(board, target=0) {
	return board.flat().reduce((cum, val, index) => cum ^ (val * index), target);
}
  
// generate new board
let board = randomBoard(2,8);
console.table(board);

// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);

// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);

// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);

// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
```
```
┌─────────┬───────┬───────┬──────┬──────┬───────┬───────┬───────┬──────┐
│ (index) │   0   │   1   │  2   │  3   │   4   │   5   │   6   │  7   │
├─────────┼───────┼───────┼──────┼──────┼───────┼───────┼───────┼──────┤
│    0    │ false │ true  │ true │ true │ false │ true  │ false │ true │
│    1    │ false │ false │ true │ true │ true  │ false │ true  │ true │
└─────────┴───────┴───────┴──────┴──────┴───────┴───────┴───────┴──────┘
The key is hidden at { i: 1, j: 4 }
flip over the coin at { i: 0, j: 2 }
┌─────────┬───────┬───────┬───────┬──────┬───────┬───────┬───────┬──────┐
│ (index) │   0   │   1   │   2   │  3   │   4   │   5   │   6   │  7   │
├─────────┼───────┼───────┼───────┼──────┼───────┼───────┼───────┼──────┤
│    0    │ false │ true  │ false │ true │ false │ true  │ false │ true │
│    1    │ false │ false │ true  │ true │ true  │ false │ true  │ true │
└─────────┴───────┴───────┴───────┴──────┴───────┴───────┴───────┴──────┘
The key is at { i: 1, j: 4 }
```

I'll leave it you to read through and find the changes on that one :)

This was my first post here, I hope you learned something, I thought this was a really cool and wanted to share. If anyone else knows any similar puzzles/algorithms I'd love to dive more into this subject. I know my university offers a course on error correcting codes but it's only offered in the spring semesters so I have a bit until I can take it, so I'd love some resources to dive into the subject on my own.

Thanks!