Let’s play a little game. You have nine coins laid out as a 3×3 square in front of you. Three of them are tails while the other six are heads, in the following shape:
T T H
H T H
H H H
You are allowed to flip coins (heads becomes tails and tails becomes heads) but only in groups of three: all three coins on a line, column or diagonal can be flipped together. So, flipping the top line from the previous example would result in this:
H H T
H T H
H H H
Your objective is to determine whether this configuration can be flipped into an all-heads (or all-tails) configuration, and if it can, provide a possible flip sequence.
I’m going to find the solution using a short program written in Objective Caml. The first thing I’m going to do is translate as much information about the problem into data that the program can manipulate. The nine coins will be numbered from one to nine in reading order:
1 2 3
4 5 6
7 8 9
So, there are eight possible moves (three lines, three columns, two diagonals) and we can represent each as a list of three integers:
let moves = [
[ 1 ; 2 ; 3 ] ; [ 4 ; 5 ; 6 ] ; [ 7 ; 8 ; 9 ] ;
[ 1 ; 4 ; 7 ] ; [ 2 ; 5 ; 8 ] ; [ 3 ; 6 ; 9 ] ;
[ 1 ; 5 ; 9 ] ; [ 3 ; 5 ; 7 ]
]
Each coin will have its state represented by a boolean: true for tails, false for heads. The current state of the board will be represented by key-value pairs, where the first element of the pair is the number of the coin and the second is its state (true, or false). A missing coin is treated as false for conciseness. So, the initial state looks like this:
[ 1, true ; 2, true ; 5, true ]
Be careful: semicolons separate items of a list, while commas separate items of a tuple (such as a key-value pair).
To get the current state of a coin, I can use the built-in Objective Caml function List.assoc key list which returns the value associated to a given key in a list of key-value pairs, and raises a Not_found exception if the key was not found. The function that returns the current state is then simply:
let state board cell =
try List.assoc cell board with Not_found -> false
If you’re not familiar with Objective Caml notation function for functions, just remember that function arguments are not wrapped in parentheses like many other languages require. Instead, they simply appear after the function name. When you provide a function with all its argument, it is called and replaced by its return value. If you’re confused by the fact that the function above returns no value, remember that Objective Caml does not need a return keyword—it always returns whatever its body evaluates to (in this case, the value returned by List.assoc or, if it raises an exception, false).
I will also need the ability to flip a coin. This is done by prepending the new key-value pair to the existing list. It is not necessary to remove the previous binding of the key, because List.assoc stops as soon as it finds the key, so subsequent occurrences are simply ignored. The code is simply:
let flip board cell =
(cell , not (state board cell)) :: board
The function simply reads the current value of the cell in the board, binds it to the cell (as a key) and prepends it to the list using item :: list notation. This does not change the value of board: instead, a new list is returned with the appropriate values inside, so that board can be reused elsewhere if necessary. This is a common occurrence in functional programming languages, and is extremely useful because values are guaranteed to be remain the same at all times.
One last thing we need before writing the actual algorithm is a function that determined whether the board has been solved. Since an all-false board can be trivially turned into an all-true board (simply flip all lines), I am just going to check whether all coins are true. This is done by using the List.for_all predicate list built-in, which returns true if and only if predicate returns true when called on every item in the list. The code is:
let is_solution board =
List.for_all (state board) [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ]
You might be confused about why state is only given one argument when it expects two. This is known as currying and is another common occurrence in functional programming languages. The basic idea is that if you give a two-argument function its first argument, then it becomes a one-argument function that expects its second argument. In this situation, state board becomes a function which expects a cell as an argument and returns the state (true or false) of that cell within the board. This precisely what we want our predicate to be.
The algorithm itself needs an initial board to work on (the one we are trying to solve) and a list of moves that it can try to solve the board. It then tries every combination of moves until it runs out or finds a solution (it makes no sense to apply a move twice, and the order in which they are applied is irrelevant, so for eight possible moves, there are 28 = 256 combinations: something that can be processed by a modern computer in the blink of an eye).
Actually trying every possible combination might seem a hard thing to do until you notice that it’s an inherently recursive process: if you have eight possible moves, you can try to apply the first one and try solve the resulting board with the other seven possible moves, or not apply the first one and try to solve the initial board with the other seven possible moves. Repeat this process until you have no moves left—at which point, if the board is all-true, you win, otherwise you lose.
let rec solution_exists board moves =
match moves with
| [] -> is_solution board
| head :: tail -> solution_exists board tail ||
solution_exists (List.fold_left flip board head) tail
The rec keyword denotes that the function is recursive (which allows it to call itself). It examines the list of possible moves using match, which allows here two different possibilities: either the list is empty, in which case a solution exists if and only if the board is the solution ; or the list contains one element (the head) along with zero or more other elements (the tail, which is itself another list). In the latter case, the function recursively calls itself twice: once while ignoring the value of the current element, and once by applying it. The function returns true if either of the recursive calls return true.
Applying the current move relies on a built-in function List.fold_left func accumulator list which is perhaps one of the most useful functions in Objective Caml. It works by reading items from the list in order, calling func accumulator x for every item in the list and storing that result back into the accumulator, and finally returns the value of the accumulator. Let’s see an example with the first possible move, [1;2;3].
let result = List.fold_left flip board [1;2;3]
(* Is equivalent to: *)
let result =
let board = flip board 1 in
let board = flip board 2 in
let board = flip board 3 in
board
In short, this applies all flips determined by the current move and returns the resulting board. But, of course, it is much shorter than the version written by hand—this was made possible by the tendency of many functional languages to manipulate lists of values instead of code. List.fold_left is one of the many ways of applying a single piece of code over a list of values and obtaining some results.
Now that all of this is done, let’s look for our solution:
let find = solution_exists [ 1, true ; 2, true ; 5, true ] moves
The result is false, meaning that no solution was found. Let’s try with another board:
T T H
H H H
T H H
Or, in terms of code:
let find = solution_exists [ 1, true ; 2, true ; 7, true ] moves
This returns true, meaning that a solution exists. How do we adapt our code to return a solution instead of just true? First, we need a way to give a name to every move, which we are going to do by associating a bit of text to each in the list of possible moves. This looks like this:
let moves = [
"L1", [ 1 ; 2 ; 3 ] ; "L2", [ 4 ; 5 ; 6 ] ; "L3", [ 7 ; 8 ; 9 ] ;
"C1", [ 1 ; 4 ; 7 ] ; "C2", [ 2 ; 5 ; 8 ] ; "C3", [ 3 ; 6 ; 9 ] ;
"D1", [ 1 ; 5 ; 9 ] ; "D2", [ 3 ; 5 ; 7 ]
]
This means that the solving function also needs to be rewritten to take this into account. Instead of returning true or false, we are going to use another Objective Caml built-in type which allows one to either return a value, or return nothing—we return the solution if it exists (Some ["C1";"D2"]) and nothing if there was no solution (None). The code becomes this:
let rec solve board moves =
match moves with
| [] -> if is_solution board then Some [] else None
| (name, move) :: tail ->
match solve (List.fold_left flip board move) tail with
| Some solution -> Some (name :: solution)
| None -> solve board tail
This is a bit more complex, but the recursive algorithm is the same: if there are no moves left, then either the board is solved (return a zero-move solution Some []) or it isn’t (return an absence of solution None. If there’s a possible move, remember its name, apply it and check whether a solution was returned: if there was one (Some solution), then just prepend the name of the move to the solution and return it (Some (name::solution)) ; if trying the move did not allow for a solution, then try solving the board without that move and return whatever solution or absence of solution this results in.
Applying this to the original problem returns None as expected, while applying it to the second problem returns Some ["L1";"L2";"C2";"D1"] — a valid solution indeed.
The complete (and quite short!) code is:
let moves = [
"L1", [ 1 ; 2 ; 3 ] ; "L2", [ 4 ; 5 ; 6 ] ; "L3", [ 7 ; 8 ; 9 ] ;
"C1", [ 1 ; 4 ; 7 ] ; "C2", [ 2 ; 5 ; 8 ] ; "C3", [ 3 ; 6 ; 9 ] ;
"D1", [ 1 ; 5 ; 9 ] ; "D2", [ 3 ; 5 ; 7 ]
] ;;
let state board cell =
try List.assoc cell board with Not_found -> false
let flip board cell =
(cell , not (state board cell)) :: board
let is_solution board =
List.for_all (state board) [ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ]
let rec solve board moves =
match moves with
| [] -> if is_solution board then Some [] else None
| (name, move) :: tail ->
match solve (List.fold_left flip board move) tail with
| Some solution -> Some (name :: solution)
| None -> solve board tail
let find = solve [ 1, true ; 2, true ; 7, true ] moves
Any questions? Let me know in the comments!
Hi. I'm Victor Nicollet,
Recent Comments