Given an ordinary sudoku puzzle how would you convert it into an irregular sudoku?

Question

I'm trying to create a puzzle like the one below (image snagged from puzzlephil.com).

I know how to generate and solve sudoku 3x3 variation via C#, and I'm now trying to add a new variant, irregular sudoku, and I'm completely stuck.

The only explanation I've been able to find on the internet came from (http://www.clarity-media.co.uk/puzzleblog/creating-irregular-sudoku-puzzles) and states, "Writing a program to create them is not trivial, but also not too hard as long as you get your algorithm correct. One way is to start off with the orthodox 3x3 box regions. Then look for regions that are capable of exchanging a cell with a neighboring region - growing by one cell from the neighboring region whilst instantly losing a different cell to the neighbor."

This isn't descriptive enough. Can anyone explain how these irregular sudoku are created? I don't need/expect code, just a simple explanation of the process. This is my first post, I hope it's not too subjective. If so, please advise me how I can be more specific. Thanks!

EDIT: I'm making progress! I now start with a board containing rows such as: 1,2,3,4,5,6,7,8,9 - next row: 2,3,4,5,6,7,8,9,1 - etc. This gives me a starting board with 1-9 in each row and col but 3x3 regions have duplicates. I then randomly switch 2 rows and then 2 columns over and over creating a randomized grouping of numbers still conforming to the 1-9 in each row/col. That's where I am for now - I am going to attempt to "draw" the irregular shapes now using recursion and maybe a tree to prune paths that aren't valid. Still open to any tips but thank you to those replying as you've started me on a path.

Answer 1

eThe quoted method could be interpreted like this:

1. Take a valid (solved) sudoku with regular 3x3 regions
2. Take a random edge between 2 regions (A and B).
3. Look for a number X that appears adjacent to this edge in both A and B. (Return to 2 if none)
4. Region A & B trade the squares with number X
5. Check that region A and B are still contiguous. (Undo 4 if not)
6. Repeat from 2.

However, as @bobble pointed out, that would yield an irregular puzzle that is secretly also solvable on a regular grid.

If I were to make such a puzzle generator, I would first generate a random valid 9row/9column solution (no region constraint) and then try to “color it in” with regions.

It will take some experimentation.

One attempt: Is to randomly assign the 9 colours to each set of 9 squares of the same number (completely ignoring the requirement that the coloured regions should be contiguous).

Next, you need to make the regions contiguous. So you define some penalty function. Eg. This penalty could be the number of squares that are not contiguously connected to the 1-square of their color. If this penalty reaches 0, you effectively have a valid puzzle.

So, you look for a pair of squares with the same number so that the penalty goes down if you swap their colours. And you repeat that until the penalty drops to 0.

This is just a naive first attempt which will surely you will get 'stuck' all the time in a local optimum. That forces you to backtrack, restart, or (probably better) implement some simulated annealing method. To avoid the algorithm taking a zillion years, inspect the stuck cases and insert heuristics to avoid those cases. Eg. if isolated squares get locked in at corners or edges, then favour fixing the edge-squares first. etc...