4
$\begingroup$

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

Irregular Sudoku

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.

$\endgroup$
4
  • $\begingroup$ I have only made a regular Sudoku solver, where the cell row and column locations in a 3x3 block can be computed. But in a "Jigsaw Sudoku" I guess that you need to devise a lookup table for each of the 9 blocks, which gives the row and column of each of its 9 cells, to use instead of computing them. And for puzzle creation perhaps its converse too , so you can look up the block and index of each of 4 neighbouring cells. $\endgroup$ Sep 16, 2023 at 19:51
  • 1
    $\begingroup$ The way I interpret the description you gave, the puzzle would end up with irregular cage shapes but still secretly conforming to the standard 3x3 box cages as well. Is that an acceptable outcome for you, or would you also want number placements that would be impossible with regular 3x3 box cages? $\endgroup$
    – bobble
    Sep 16, 2023 at 21:53
  • $\begingroup$ @bobble - Number placements that would be impossible with a regular 3x3 box shape would be preferred. I've seen those and I think those would be more challenging, but shifting the cage around in order to get an irregular pattern would also be interesting to see. $\endgroup$
    – BrianLegg
    Sep 17, 2023 at 0:06
  • $\begingroup$ If you have an answer, it goes in the answer section, not as an edit to the question, please. $\endgroup$
    – bobble
    Sep 18, 2023 at 19:53

1 Answer 1

2
$\begingroup$

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...

$\endgroup$
8
  • $\begingroup$ This only gives half the puzzle because it doesn't tell you which numbers you have to provide as the starting position. The procedure guarantees that no matter which numbers or how many your initial solved grid will be a solution but I think you still need some trying and testing (possibly brute force) to find a collection of starting numbers that gives a unique solution. $\endgroup$
    – quarague
    Sep 18, 2023 at 12:04
  • $\begingroup$ @Kris Van Bael - Thanks for the reply, I will give that a try, but I am even more interested in your last sentence. How would you go about, "I would first generate a random valid 9row/9column solution (no region constraint)" - I've tried doing this and I can come up with 1-2 by hand but haven't found a good algorithm for doing this without making 3x3 regions as well. Thank you! $\endgroup$
    – BrianLegg
    Sep 18, 2023 at 14:25
  • $\begingroup$ So I've solved the 9row/9col solution. But how to "color it in" with regions? $\endgroup$
    – BrianLegg
    Sep 18, 2023 at 15:41
  • $\begingroup$ I adjusted the answer, with what I would try first. $\endgroup$ Sep 19, 2023 at 6:29
  • $\begingroup$ Thanks Kris. I've marked your answer as the most helpful/correct :) I'm still trying your idea but I didn't want to hold up the show. Your idea is really interesting but it'll take me a few to implement. thanks $\endgroup$
    – BrianLegg
    Sep 19, 2023 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.