Void’s Vault

Knowledge source for efficiency.

The Cubic Sudoku Problem

On my previous post on this subject, I explained how I created a Sudoku solver for Android using the CoR pattern. Now, some students I am supervising in an engineering course at Laval University were given the task to solve a Cubic Sudoku. This problem looked interesting so I wanted to search a bit to find how difficult it is to solve this problem. You will see in this article that it’s really no big deal.

It’s quite simple in fact :

In a real sudoku problem, you have to respect three rules.

  • A number must not repeat itself within a row;
  • A number must not repeat itself within a column;
  • A number must not repeat itself within a 9x9 section;

In the cubic sudoku, well… it’s the same thing, except that the rows and the columns are messed up a bit. Let me explain:

In this puzzle, a section is a 4x2 area delimited by the bold lines. The only other rule is that a column|row is a 8x1 line in any direction. There are four lines crossing the upper part through the left part of the cube. [0 7 4 0 8 0 0 0] is an example. There are also four lines crossing the upper part through the right part of the cube. [0 5 7 0 0 0 6 0] is also an example. Finally, there are four lines crossing the left part through the right part of the cube. [0 3 0 0 2 0 0 0] is one of them.

The solution is then to consider rows and columns as the same thing for the cube. You will then be facing a problem that is way easier than the sudoku problem. Since I could reuse my code from the Sudoku Solver I’ve made earlier, it took only a couple of hours to solve the problem.

I reused my chain of responsibility pattern, but with only one strategy: a Simple Constraints Satisfaction Problem. Then, when the constraints are propagated, I try to bruteforce the cell with the least values possible. It leads to a solution in almost no time, since this puzzle is a bit smaller than a real sudoku puzzle.

I invite you to revisit the website I used to build strategies to solve this problem faster.

Of course, the problem that the students are facing is much more interesting and the “Sudocube” is only a part of the problem.

They first need to detect an antenna with their robot that will emit an encoded signal telling the id of the sudocube to read. This should be easy to do this part if everybody do his job well.

Second, they need to do some pathfinding to move their robot in front of the sudocube. (They will locate the position of their robot with a Kinect, how cool is that?!?)

Third, they must do some OpenCv work to scan the sheet with the sudoku. The teachers have eased the task by giving them puzzles that are always a the very same position on each sheet. Still, that is not an easy task.

Finally, when the puzzle is solved, they need to draw a particular cell of the puzzle on the table with great precision. For this last part, if the pathfinding is working well and since they can easily solve the sudocube, let’s just hope that the servo-control of their robot have been done perfectly!

Enjoy the tips, and I wish good luck to the future engineers!