Exercise 02: Solving Sudoku

For this exercise, make sure you run all commands from the directory:

  /path/to/cbat_tools/docs/exercises/02

The task of this exercise is to let wp solve a 3x3 Sudoku cube.

3x3 Sudoku cubes

A 3x3 sudoku cube has 9 squares, some of which have a 1, 2, or 3 in them. For example:

+---+---+---+
|   |   | 2 |
+---+---+---+
| 2 |   |   |
+---+---+---+
|   | 2 |   |
+---+---+---+

To solve a cube such as this, you must fill in each square with a 1, 2, or 3, so that each row and each column in the cube contains one each of 1, 2, and 3. For example, a correct solution to the above would be this:

+---+---+---+
| 3 | 1 | 2 |
+---+---+---+
| 2 | 3 | 1 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+

Such a solution can be encoded as a 32-bit number. To do that, convert each digit into a 2-bit binary number (so 1 becomes 01, 2 becomes 10, and 3 becomes 11), then concatenate them, and pad with 12 zeros on the right to make the whole number 32 bits wide. For example, to encode the above solution as a 32-bit number, do it like this:

+---+---+---+      +----+----+----+
| 3 | 1 | 2 |      | 11 | 01 | 10 |    11 01 10
+---+---+---+      +----+----+----+
| 2 | 3 | 1 |  =>  | 10 | 11 | 01 | => 10 11 01
+---+---+---+      +----+----+----+
| 1 | 2 | 3 |      | 01 | 10 | 11 |    01 10 11
+---+---+---+      +----+----+----+


=>  11 01 10   10 11 01   01 10 11    00000000000000

        ^          ^         ^              ^
        |          |         |              |
     1st row    2nd row   3rd row     Pad with zeros


=>  110110 101101 011011 00000000000000
=>  11011010110101101100000000000000

Finally, use a binary-to-hex converter (easily found online) to convert that binary number to a hex value. In this case:

11011010110101101100000000000000  =>  0xDAD6C000

So 0xDAD6C000 represents the above solution to the 3x3 cube. Here is another solution to a 3x3 cube, which is not correct (can you see why it is not correct?):

+---+---+---+      +----+----+----+
| 1 | 3 | 2 |      | 01 | 11 | 10 |    01 11 10
+---+---+---+      +----+----+----+
| 2 | 3 | 1 |  =>  | 10 | 11 | 01 | => 10 11 01
+---+---+---+      +----+----+----+
| 3 | 2 | 1 |      | 11 | 10 | 01 |    11 10 01
+---+---+---+      +----+----+----+


=>  01 11 10   10 11 01   11 10 01    00000000000000
=>  01111010110111100100000000000000
=>  0x7ADE4000 (in hex)

So, 0x7ADE4000 is a solution to a 3x3 sudoku cube, but it is a solution which is incorrect.

The sample binary program

There is a program at binary/main. The source code lives at binary/main.c, but you should be able to complete this exercise without looking at the source code. This program checks solutions to a 3x3 sudoku cube. The program contains a function check, which takes for its argument a solution encoded as a 32-bit number in the manner described above. This function checks if the provided number represents a correct solution. If so, it trips an assert. Try it out, using the number we constructed above, namely 0x7ADE4000, which represents an incorrect solution:

    $ ./binary/main 0x7ADE4000

When you run this, the program prints the solution you provided:

+---+---+---+
| 1 | 3 | 2 |
+---+---+---+
| 2 | 3 | 1 |
+---+---+---+
| 3 | 2 | 1 |
+---+---+---+

Check the exit code:

    $ echo $?

You will see that the program returned 1, to indicate that the solution is not correct. Now try it with the number we constructed above that represents a correct solution, namely 0xDAD6C000:

    $ ./binary/main 0xDAD6C000

Again, it prints the solution you provided:

+---+---+---+
| 3 | 1 | 2 |
+---+---+---+
| 2 | 3 | 1 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+

But this time, since the solution is correct, it trips the assert:

main: main.c:68: check: Assertion `0' failed.
Aborted

Your task

Use wp to complete the following task:

Use wp to find a hex number that represents a correct solution to a 3x3 sudoku cube.
Convert that hex number to a 3x3 sudoku cube board (draw the board, with the correct 1s, 2s, and 3s in it).

Solution

To see the solution, click here.