SKILL for the Skilled: Introduction to Classes -- Part 2

In the previous posting Introduction to Classes -- Part 1 we introduced the problem of solving the Sudoku puzzle. I want to show a solution to this puzzle in SKILL++. Doing so, I'll break the problem up roughly into four parts.

• Represent the structure of the data
• Initializing
• Displaying the state
• Searching for a solution

High Level View

Here is a top-down view of the solution algorithm.

(defun SkuSolve (partial_solution)
  (let ((sudoku (SkuInitialize (SkuNew) partial_solution)))
    (printf "starting with: \n%s\n"
            (SkuPrint sudoku))
    (printf "\nfound solution:\n%s\n"
            (SkuPrint (SkuFindSolution sudoku)))))

In the upcoming postings I'll define the following functions used in SkuSolve. SkuNew Allocate a new sudoku board, creating rows, columns and 3x3 grids which appropriate links to enable fast searching. SkuInitiailize Fill in the empty board with an initial partial solution. SkuPrint Print the current state of the board with either a number or white space in each cell. SkuFindSolution Assign the appropriate numbers to the empty cells so as to solve the sudoku puzzle.

In this posting, let's look at how to represent the structure of the sudoku puzzle using SKILL++ classes.

Defining a class

A sudoku board has 9 rows, 9 columns, and 9 3x3 blocks of cells. Each row, column and 3x3 block has 9 individual cells. Each individual cell contains a single value which is a digit between 1 and 9 inclusive. We can represent a cell in SKILL++ with the following class definition. As shown on line 1.1, we define a class with defclass. Each instance of an SkuCell has several slots which can be accessed by name.

• an index, (line 1.2) which is a number between 0 and 80 inclusive. There are 81 (9x9) cells in the sudoku board. The index uniquely identifies the cell.
• a value, (line 1.3) which is an integer in the set {1, 2, 3, 4, 5, 6, 7, 8, 9}.
• row, (line 1.4) an instance of SKILL++ class SkuRow indicating that this cell is an element of that row in the sudoku board.
• column, (line 1.5) an instance of SKILL++ class SkuColumn indicating that this cell is an element of that column in the sudoku board.
• b3x3, (line 1.6) an instance of SKILL++ class SkuB3x3 indicating that this cell is an element of that 3x3 block in the sudoku board.

(defclass SkuCell ()      ; 1.1
  ((index @initarg index) ; 1.2
   (value @initform nil)  ; 1.3
   (row)                  ; 1.4
   (column)               ; 1.5
   (b3x3)))               ; 1.6

Creating instances of a class

You can use makeInstance to create an instance of the class: (makeInstance 'SkuCell). Because the slot index is defined containing @initarg index (line 1.2), you can optionally specify the ?index keyword in the makeInstance call. E.g., (makeInstance 'SkuCell ?index 42), this will provide an initial value of 42 as for slot index. The slot value is defined with @initform nil (line 1.3) which provides an initial value of nil this slot.

Accessing slots of an instance of a class

The slots defined on lines 1.4, 1.5, and 1.6 have no @initarg nor @initform, but you can access these slot values using the handy-dandy -> operator as shown on lines 2.3, 2.4, 2.6 and 2.7.

cell1 = (makeInstance 'SkuCell ?index 42) ; 2.1
cell2 = (makeInstance 'SkuCell ?index 43) ; 2.2
(assert cell1->index == 42)               ; 2.3
(assert cell2->index == 43)               ; 2.4
                                          ; 2.5
cell1->row    = nil                       ; 2.6
(assert cell1->row == nil)                ; 2.7

Using classes to share structure

The rows, columns, and 3x3 blocks (b3x3's) are represented respectively by the classes SkuRow, SkuColumn, and SkuB3x3. But each of these shares some structure. Each has an index, rows are numbered 0 through 8, columns are also numbered 0 through 8 (likewise for 3x3 blocks). Furthermore, rows, columns, and 3x3 blocks have a list of cells (9 instances of class SkuCell). This shared structure is represented by the class SkuGroup from which SkuRow, SkuColumn, and SkuB3x3 each inherit. Note in the example 3 that the second argument of defclass may be nil indicating that the direct super-class is the default one provided by SKILL++, or the second argument may be a list of class names. Actually in 6.1.5 the list of class names is fully supported. Prior to 6.1.5, classes were only allowed one direct super-class. In example 3, the three sub-classes (SkuRow, SkuColumn, and SkuB3x3) of SkuGroup all have slots named index and cells.

(defclass SkuGroup ()
  ((index @initarg index)
   (cells @initform nil)))

(defclass SkuRow (SkuGroup)
  ())

(defclass SkuColumn (SkuGroup)
  ())

(defclass SkuB3x3 (SkuGroup)
  ())

Review

In this posting we looked at the plan for solving the sudoku puzzle, and the first step we used class inheritance define some simple classes which represent the state of the board. This includes simple uses of @initarg, @initform, and makeInstance

Preview

In the upcoming postings we'll continue by looking at some slightly more advanced ways to use defclass and encapsulation. We'll also continue the development of sudoku by printing the board and solving the puzzle.

Jim Newton