PDP-10 Sudoku-Solver

Introduction

This project is designed mostly in order to study the way PDP-10 assembly and machine language works, and not so much about solving sudoky's. After all, there's already a lot of software out there, doing just that. So this document will analyse how the algorithm works, and explain how to map it into the PDP-10's machine language.

Despite this technical approach, we first need to explain what a sudoku is, and how it works. Sudoku is a a logic based number-replacement puzzle gane originally from Japan. The word sudoku literally means digit-single. The objective is to fill a 9x9 grid with numbers between 1 and 9, without having a number repeat in a row, column or inside a 3x3 sub-grid the sudoku is separated into. Normally, there are a few numbers preset. Im 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 valid grids. A number that reduces to 5,472,730,538 essentially different solutions. The sudokus you will find in a puzzle book, are always one of those roughly five billon, in order to guarantee a solution.

Sudoku 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.

This is it. Learning the rules to solve a sudoku is trivial, solving it, is another story. Solving sudokus can be quite tricky at times.

Solving Sudokus Algorithmically

Solving a sudoku can be achieved in several 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 recursively, and add a number. Then we check if the grid is still valid. If it is, we recursively 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 a simple function. In C it looks like this:

// 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 is not straight forward, is the last part. By taking the modulus of the current row and cilumn, we can find the top left element in each sub-grid thus getting the index in the matrix, the sub-grid starts. When doing so, the grid has to be treated as a matrix, which is comparatively easy in C, but needs some preparation in machine code.

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;
}

That is basically it.

Using the PDP-10 To Solve Sudokus

Of course we could just write the whole program in C and forget about the PiDP-10. But we want to create the code in machine language, in order to understand the PDP-10 better. The following chapters will describe in detail, how this project was created and setup.