Sudoku is a logic based number-placement puzzle game originally from Japan. The word sudoku literally means digit-single. The objecttive is to fill a 9x9 grid with numbers between 1 and 9, without having a number repeat in a row, column or a 3x3 subgrid. Normally, there are a few numbers preset. In a regular sudoku, the pre-filled numbers make sure, that exactly one solution for the puzzle exists.

The number of possible valid solutions to a sudoku is finite. In a classical Sudoku, there are 6,670,903,752,021,072,936,960 possible valid grids. A number that reduces to 5,472,730,538 essentially different solutions. The Sudokus you will find in a modern day puzzle book, are always one of those roughly 5 billion, in order to guarantee a solution.

Rules

A Sudoku is presented in a 9x9-grid:

||===|===|===||===|===|===||===|===|===||
||   |   | 2 || 9 |   | 3 || 8 |   |   ||
||---|---|---||---|---|---||---|---|---||
||   |   |   || 4 | 6 | 8 ||   |   |   ||
||---|---|---||---|---|---||---|---|---||
|| 4 |   |   ||   |   |   ||   |   | 1 ||
||===|===|===||===|===|===||===|===|===||
|| 5 | 6 |   ||   |   |   ||   | 4 | 9 ||
||---|---|---||---|---|---||---|---|---||
||   | 2 |   ||   | 5 |   ||   | 7 |   ||
||---|---|---||---|---|---||---|---|---||
|| 7 | 8 |   ||   |   |   ||   | 1 | 3 ||
||===|===|===||===|===|===||===|===|===||
|| 2 |   |   ||   |   |   ||   |   | 7 ||
||---|---|---||---|---|---||---|---|---||
||   |   |   || 3 | 8 | 4 ||   |   |   ||
||---|---|---||---|---|---||---|---|---||
||   |   | 6 || 2 |   | 1 || 3 |   |   ||
||===|===|===||===|===|===||===|===|===||

The rules are the following:

Every row must contain every number between 1 and 9 exactly once.
Every vertical column must contain all the numbers between 1 and 9 exactly once.
Every 3x3 sub-grid must contain every number between 1 and 9 exactly once.

Solving Sudokus programatically

Backtracking (naïve approach)

Solving a Sudoku can be achieved in serveral ways. The most simple algorithm, is a backtracking algorithm. With this a sudoku can be resolved basically by brute-forcing it. In this case, we walk through each cell of the grid recurseivly, and add a number. Then we check, if the grid is still valid. If it is, we recursivly move on to the next column. If we find a number that doesn't match, we return to the previous incarnation, and try another number. In order to check, if our grid is still valid, we can use simple function:

// Function to check, if it is save to place num at mat[row][col]
int isSafe(int[][] *mat, int row, int col, int num) {
  // Check if num exists in the row
  for (int x = 0; x <= 8; x++) {
    if (*mat[row][x] == num) {
      return 0;
    }
  }

  // Check, if num exists in column
  for (int x = 0; x < 8; x++) {
    if (*mat[x][col]) {
      return 0;
    }
  }

  // Check if num exists in the 3x3 sub matrix
  int startRow = row - (row % 3);
  int startCol = col - (col % 3);

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++ {
      if (*mat[i + startRow][j + startCol] == num) {
        return 0;
      }
    }
  }

  return 1;
}

The only bit in this code, not straight forward, is the last part. By taking the modulus of the current row and column, we can find the top left element in each sub-grid, and adding the according number to it, we can then walk through.

The solving algorithm itself, is surprisingly simple:

// Function to solve the sudoku problem by backtracking.
int solveSudokuRec(int[][] *mat, int row, int col) {
  int n = sizeof(*mat);

  // base case: Reached the nth column of the last row. We're done.
  if (row == n - 1 && col == n) {
    return 1;
  }

  // if last column of a row, go to next row
  if (col == n) {
    row++;
    col=0;
  }

  // if cell is already occupied, move on
  if (*mat[row][col] != 0) {
    return solveSudokuRec(mat, row, col + 1);
  }

  for (int num = 1; num <= n; num++) {

    // if it is safe to place num at current position, do so.
    if (isSafe(mat, row, col, num)) {
      *mat[row][col] = num;
      if (solveSudokuRec(mat, row, col + 1)) {
        return 1;
      }

      *mat[row][col] = 0;
    }
  }

  return 0;
}

And that's it.

Using the PDP-10 to solve the Sudoku

In order to run this program, you need a working PDP-10 simulator (or, if you are a very lucky person,the real thing). You can either use the PiDP-10 kit, or a Raspberry Pi 5 to run it on. The PiDP-10 can be run on any Raspberry 5 computer, even without the front panel, but having the front panel is fancier. You can also run simh on a PC, but that would only be half the fun.

The PiDP-10 shold be booted into ITS, as this is the OS, this project is running against. Now the only thing you need to do, is copy the source code files into the file system of your PiDP-10. You can do this by using the mlftp tool, installed on the machine your simulator runs on. You clone the repository and run the following commands from the command line:

/opt/pidp10/bin/mlftp -w ITS "SUDOKU 1 JALI;" ./src/sudoku.s
/opt/pidp10/bin/mlftp -w ITS "PUZZL1 SUDOKU JALI;" ./src/puzzle_1.sudoku

This will copy the source code file, and the example puzzle file onto the PiDP-10. Remmber to change the directory name in the ITS path form JALI to the directory you want to copy to.

You can now edit both files in EMACS on the PiDP-10. However, if you prefer to edit your code in a somewhat more modern environment (your favourite IDE, for example), consider installing the git-monitor on your PiDP-10's host system. The monitor is a service written in bash, that will clone your project repositories and then monitor a given branch for new commits. On new commits it pulls them, and runs the script .git-monitor_after.sh, which in turn, contains the upload commands for ITS. This way, you can automatically update your source code in ITS, even when you are working on a modern machine.

Building and running

Log into ITS with your developers user name by typing USERNAME$U (where $ is the ESC-Key), If you are a luser: Type :LOGIN USERNAME and swap USERNAME for your actual username. Confirm with Enter.

Now you can build the sudoku solver by invoking MIDAS in DDT:

:MIDAS TS SUDOKU_SUDOKU

This will instruct MIDAS to create a relocatable binary (TS) from the latest version of the SUDOKU file, and store it in a file named TS SUDOKU in the current directory. If this succeded, listing the files with :LISTF (or CTRL+F, if you're not a turist), should look something like this:

KA    JALI
FREE BLOCKS #2=154 #3=169 #0=156 #1=171
  1  PUZZL1  SUDOKU 1 ! 9/21/2025 22:02:04
  3  SUDOKU  1      1 ! 9/21/2025 22:02:02
  1  TS      SUDOKU 1 ! 9/21/2025 23:25:09

To invoke the solver run it with:

:SUDOKU PUZZL1 SUDOKU

This will pass the file PUZZL1 SUDOKU to the program, and start to solve it.

The result will be printed on the screen (once the project is finished).