I’ve always wanted to make a Sudoku game for Mindstorms NXT, and, since it’s the holidays and it’s been raining all day, I finally got a start on it. The basic idea is that the NXT will generate a completely random (but correct) filled-in Sudoku grid, then determine what boxes can be emptied for the user to fill in, then let the user fill in those boxes, and finally check the user’s answers.
Today, I got around doing the first part: a fairly short (54 lines of code) RobotC program that generates and displays a full filled-in Sudoku grid on the NXT’s screen. Here’s the pseudo code:
- Clear the sudoku variable (a 9*9 array that will hold the grid)
- Enter the outer for loop that repeats 9 times and determines the number, i, that is going to be placed in the next cell (cells are filled in order: all the 1s are first, then all the 2s, etc.)
- Clear the block Boolean variable (a 9 variable array that will register whether number i is already in each 3*3 cell block)
- Enter the inner for loop that repeats 9 times and determines j, which represents the row the number from the outer for loop is placed in (this is because the same number can only be placed in the same row once)
- Set variable k to a random number between 0 and 8 to determine what column number i will be placed in
- Reset the tries variable
- Increment k by 1, or, if k = 8, reset it to 0
- Increment the tries variable by 1
- Check whether the tries variable is less than 9; if yes, continue, if no, go to step 1
- Check whether i is already present in the column; if yes, go to step 7, if no, continue
- Determine which block i is going to be placed in by looking at which row, j, it’s in, and which column, k, it’s in
- If i is already present in the block i is going to be placed in, go to step 7, otherwise, continue
- Place i in the sudoku array, in row j and column k
- Set the corresponding block Boolean variable to “true”
- Write i in the correct place on the screen
- Exit the inner for loop
- Exit the outer for loop
The results of that are shown in the picture above: a completely random Sudoku, made entirely by the NXT. Worth noting is that the program will get stuck, because, since the placement of the numbers is random, there are bound to be conflicts.
When this happens, steps 8 and 9 will reset the program, and it will keep on re-running until a complete Sudoku is created. Sudokus will therefore take anywhere from a split second to an infinite amount of time to generate. The average is about 4 seconds.
There are also some other things going on, like a simple UI for the user to choose a difficulty level while he/ she waits for the NXT to finish generating the Sudoku, but that’s not included in the above pseudo code. Below are some screen caps from said interface.
The next step is to make the program determine which numbers can be derived from the remaining set and hide some of them from the user. The difficulty level will determine how many of these numbers will be hidden: each progressive difficulty level will hide one more cell than the level below.