In an effort to improve things, I have split this challenge into two parts, both currently listed in this question for the sake of keeping them together.
NOTE: "Run a game of Flood" has now been posted.
Solve a game of Flood
This is a Code Challenge with Code Golf aspects.
Flood is a game in which the player is presented with a game board such as this:
On each turn, you choose a colour (on the link above, by clicking a square containing that colour), and the cell in the top-left corner is filled with that colour - this colour will absorb all adjacent cells with the same colour. So, for example, the first turn might be Blue, which will cause the yellow cell in the top corner to turn blue, and merge with the existing blue cell. The next turn might be Purple, which will fill both of the first two cells purple, merging them with the two-cell purple area attached to them. Then you might go Red, then Orange. With this sequence, the board will end up as:
Your task is to write code that acts as a "solver" program/code, which reads in the initial/current state of the board, and determines the next move or the remaining moves. This code should make an effort to produce an efficient path to the solution, but you must balance this search for efficiency with the golfing effort.
Your code may make use of a simulator code (such as may be used in the "Run a game of Flood" challenge) that takes input of the current state of the board and a sequence of moves, and outputs the resulting state of the board after these moves - these must be the only inputs/outputs used by your code.
Your code must produce a solution for any initial board (not just the test boards, see below), and must be deterministic - that is, it must produce the same solution every time the same initial board is input (fixed-seed pseudorandom numbers are acceptable).
As noted above, this is a combination Code Golf challenge. Your goal is to minimise your score, much of which is determined by the length of your code in bytes.
Your final score is
b is the total bytes of your code (simulator code does not count towards this value, but the call to simulator code does),
n_i is the number of steps used by your solver program to solve each of the test boards (see below), and
d_i is the maximal depth to which your code searches for each of the test boards before selecting a step.
d_i value, here, is intended to punish those who use brute force to find the optimal solution. You need to find efficient solutions, cheaply.
Rules and Assumptions
Standard Loopholes are forbidden.
Code must be able to handle non-square boards, with each dimension being anywhere between 6 and 30 cells (more is fine, it must handle this range). It must be able to handle between 3 and 9 distinct colours or "colour" labels (numbers are fine).
You may assume that input is in simplest form - that is, if there are four colours, they will be labelled 1-4, or a-d, or any other similar system as appropriate. You will not need to handle situations such as incorrect inputs, unsimplified inputs (you won't have the numbers 1, 3, 6, and 9, without the others in between, unless it suits your code).
Your code may take input indicating details of the board such as dimensions and the set of valid "colours".
Your answer should include a description of formats, etc.
Code cannot treat the test boards as special cases - that is, you cannot have the code detect which test board it is, and if it doesn't match a test board, use a generic, low-quality code for solving.
Request: If you believe you have identified a non-standard loophole, and it's definitely a loophole and not in the spirit of the question, please comment to have the loophole closed, rather than posting an answer using it. This is not a rule, per se, but an effort to keep the challenge interesting.
7x6, 6 colours
12x12, 6 colours
12x12, 3 colours
16x16, 9 colours
Tags: Code-Challenge, Code-Golf, Optimization, Game
Not sure whether this should be labelled as Code-Challenge, Code-Golf, or both