I'm conceptualizing a solver for a variant of sudoku called multi-sudoku, where multiple boards overlap like so:

If I understand the game correctly, you must solve each grid in such a way that the overlap between any two or more grids is part of the solution for each.

I'm unsure as to how I should be thinking about this. Anybody got any hints/conceptual clues? Additionally, if any topics in artificial intelligence come to mind, I'd like to hear those too.

A different approach would be to use a genetic algorithm. Which is based on biological evolution. Genetic algorithms are part of evolutionary algorithms and therefore share the analogy "fitness-function". A valid solution is found via recombination, selection and mutation.

The basic concept is to initialize a number of solutions "individuals" which consist of "chromosomes" by random (Solutions can be wrong of course). Define a "fitness-function" which evaluates the quality of every individual within the current "generation". Take with a higher probability the individuals with better fitness to recombine them into a "child" solution and mutate, with a low probability, some individuals within the new generation. Repeat until some criteria (max_iteration_count, valid_solution_found) is true.

To fit a genetic algorithm to your problem. You could do something like the following. Create for every 3x3 or 9x9 sudoku a local correct solution. These are the chromosomes. Put them in one data structure. Thats an individual. Create a bunch of them to form a generation. Evaluate every individual by the constraints its violating. Calculate corresponding probability. Recombine the individuals, mutate some chromosomes, repeat.

You could see it as combination of local and global optimization. Since you would need some kind of greedy algorithm (or whatever you want to use to solve the local sudoku) to find a local, and the GA to find the overall global optima. I think it would not make sense to only use the GA and try to solve this Problem. I implemented a GA on a combinatorial Problem recently and without local optimization the results were, most of the time, quite terrible.

The good thing about GA though, is that they make large steps at the beginning of the search converging towards an optima but still cover big parts of the search space. But as always with EA, tuning the parameters can be quiet tricky.