Orthogonal Sudokus

Question

This a Sudoku puzzle created by Paul Vaderlind.

Fill each cell with 2-digit numbers from 11 to 99 (without the digit 0) such that

• The first digits represent one regular Sudoku grid.
• The second digits represent another regular Sudoku grid.
• Each number from 11 to 99 (without the digit 0) occurs exactly once in the grid (orthogonality constraint). So "23" cannot occur twice, but "23" and "32" both occur.

For your convenience I also made a version where the first digits have been replaced by letters from A to I.

Answer 1

I came up with the same answer as @Dr Xorile:

This one was actually pretty easy to do by hand in a spreadsheet. However it took enough steps that I couldn't undo all the way back to the beginning, so the first few steps are just going to be what I remember doing. I'll try to recreate the first part later when I have some time:

The first and most helpful thing I did after transcribing the puzzle was create a chart of all the numbers used so far. The extra information I could see in the chart made it a lot easier to decide what to try to figure out next.

My next step was just to look at each Sudoku individually and use very basic solving techniques. That allowed me to find all the 9_s and some others.

As soon as that was no longer bearing fruit:

I decided to look at the orthogonality constraint. Using my chart of used numbers, I could see that the 1_s didn't have too many left. By looking at the possibility for each 1_, I was able to solve for all of them.

More groups:

Next up were the 8_s, 9_s, and _9s, though I don't remember the order in which I did them. I think the 9_s were first.

(I have some pictures for this point on!) I was able to make a lot of progress on the second-digit Sudoku at this point

I was able to find all the _5s and some of the _3s:

Another set of numbers finished:

I figured out the rest of the _3's and got 44 and 68 along the way.
It was at about this point that I didn't really have to look very hard for the next number to fill in. Just normal sudoku rules for rows, columns, and cells, using the chart of used numbers as a guide for where to aim next and quickly narrowing down possibilities.

Finally, almost done:

I got to this point and saw that it looked underconstrained, and finally noticed that I'd missed transcribing a clue. Trivial to solve from here once I put it in

Answer 2

I believe the answer is:

59 23 96 18 42 75 84 61 37
88 62 35 57 21 94 16 43 79
17 41 74 89 63 36 55 22 98
26 99 53 45 78 12 67 34 81
65 38 82 24 97 51 49 76 13
44 77 11 66 39 83 28 95 52
93 56 29 72 15 48 31 87 64
32 85 68 91 54 27 73 19 46
71 14 47 33 86 69 92 58 25

I saw a recent comment on a different question about linear programming, so decided to give it a go. It was harder than I thought, but mostly me figuring out the syntax etc. I thought of trying by hand, but the orthogonality constraint is a pain to spot by eye. I might give it a go with a spreadsheet like I did with the mobius sudoku, where the spreadsheet can track those sorts of details.