Sudoku solver

[Jan Skibinski]

#|
file: "sudoku.scm"
author: "Jan Skibinski"

version: 0.1
init-date: 2006-06-10
license: at the bottom of this file
description:

A sudoku solver with with aggressive pruning of the solution space.
Uses Sitarai/Brown amb framework (attached at the beginning of the
code). Provides three puzzles with solutions and progress reports -
ranging in complexity from low to high: 'pacific, 'classic and
'vintage.
Fast and memory neutral in Petite Chez Scheme interpreter
slow and memory hungry in Mzscheme interpreter. [This observation
relates only to this and other Constraint Satisfaction Problems
handled by this amb framework, otherwise Mzscheme is just fine.
See a separate post on this issue.]

Note: Before using this script examine the last section of the
code and supply your own implementation of several semi-standard
list functions: take, drop, product, fact, nub, zip, iota,
minimum, filter, some. I just imported them here from my own module
'hof.

The basic units of operation are the nondeterministic procedures
'sudoku-box and 'sudoku-row, which apply to 3x3 boxes and
rows/columns,
respectively. During processing the boxes are converted to rows,
then to columns and then back to boxes.

Boxes are enumerated as follows:

|0 1 2|
|3 4 5|
|6 7 8|

The constraints:
+ Elements are drawn from the (1 2 3 4 5 6 7 8 9) domain.
+ Elements at each 9-component row are distinct
+ Elements at each 9-component column are distinct
+ Elements at each 3x3 box are distinct

The sudoku algorithm is made of three parts:
1. Prune the solution space via deterministic recursive
function 'prune, which simplifies domains whenever possible
when examining consistency of boxes, rows and columns.
2. Reduce the solution space via nondeterministic recursive
function 'reduce, which dissassembles and then assembles again
the boxes, rows and columns - simplifying in process the ovarall
representation of the puzzle.
3. Split the puzzle into several 9x9 sub-puzzles via
nondeterministic
function 'split and apply steps 2 and 3 to each branch in
succession -- until one of the branches succeeds.

Some puzzles are completely solvable during the first two stages
alone. More difficult ones need the splitting stage or several
such stages.

Pruning is very important as demonstrated by the following
calculations for the 'vintage example:

The puzzle input (zeros stand for unknowns):

(define vintage '(
(0 0 8 0 0 0 1 5 0)
(0 0 0 0 0 1 8 0 0)
(3 0 5 4 0 0 0 0 9)

(5 0 0 0 0 9 0 0 0)
(0 9 0 2 3 4 0 7 0)
(0 0 0 1 0 0 0 0 8)

(4 0 0 0 0 5 9 0 1)
(0 0 6 7 0 0 0 0 0)
(0 5 3 0 0 0 2 0 0)))

1. Initialization, replaces zeros by lists of admissible domains:

(define initial-boxes (map box-init (rows->boxes vintage)))

2. Count of admissible solutions per each box, satisfying a box
constraint (all elements should be distinct and taken from 1 to
9):

(map permutation-count initial-boxes)
==> (720 5040 120 5040 24 5040 120 5040 720)

3. Count of admissible solutions per box, as delivered by
nondeterministic function sudoku-box. Confirmation of
the result 2 above. Not used in the sudoku algorithm, takes
long time to compute. Take it for granted, skip this step
unless you like to see the experimental confirmation of 2!

(map (lambda(box)(length (bag-of (sudoku-box box))))
initial-boxes)
==> (720 5040 120 5040 24 5040 120 5040 720)

4. Total count of admissible solutions:

(* 720 5040 120 5040 24 5040 120 5040 720)
==> 11,560,080,875,181,834,240,000,0000

No way to be handled by a brute force search!

5. First stage of solving the puzzle:

(define pruned-boxes (prune initial-boxes))

6. Count of admissible solutions per box after pruning,
as delivered by nondeterministic function sudoku-box:

(map (lambda(box)(length (bag-of (sudoku-box box))))
pruned-boxes)
==> (40 84 16 24 3 4 12 10 12)

7. Total count of admissible solutions after pruning:

(* 40 84 16 24 3 4 12 10 12) ==> 22,295,347,200

No way to be handled via blind backtracking in any reasonable
time!

8. Second stage of the algorithm, reduction:

(define reduced-boxes (reduce pruned-boxes))

9. Count of admissible solutions per box, after reduction,
as delivered by nondeterministic function sudoku-box:

(map (lambda(box)(length (bag-of (sudoku-box box))))
reduced-boxes)
==> (12 10 8 12 3 2 3 5 5)

10. Total count of admissible solutions after reduction:

(* 12 10 8 12 3 2 3 5 5) ==> 5,184,000

Still a huge number, but it can be handled by exhaustive search.
A naive version of the sudoku solver could find the solution after
about
1,400,000 trials. But it would take 30 seconds or so to find it.

11. This is where the third part of the algorithm, the 'split
function,
kicks in. It splits the puzzle into several nondeterministic 9x9
sub-puzzles, and examines each one in turn, until some branch is
reduced to this count of admissible solutions per box:
(1 1 1 1 1 1 1 1 1).

Due to this approach no brute force search is ever employed and the
result is delivered in two seconds when using Petite interpreter.
See progress report inside the examples section.

|#
;; ======================
;; The Amb framework
;; ======================

;;Copied from the presentation:
;;
;; "Advanced Scheme Techniques
;; Some Naughty Bits"
;; by Jeremy Brown
;;
;; which in turn is adapted from the book:
;;
;; "Teach yourself Scheme in Fixnum Days"
;; by Dorai Sitaram

;; One of many nondeterministic solutions
(define-syntax amb
(syntax-rules ()
[
(amb argument ...)
(let ((old-amb-fail amb-fail))
(call/cc
(lambda (return)
(call/cc
(lambda(next)
(set! amb-fail next)
(return argument))) ...
(set! amb-fail old-amb-fail)
(amb-fail #f))))
]))

;; All solutions
(define-syntax bag-of
(syntax-rules ()
[
(bag-of expr)
(let* ((old-amb-fail amb-fail)
(result '()))
(if (call/cc
(lambda (ifcondcont)
(set! amb-fail ifcondcont)
(let ((e expr))
(set! result (cons e result))
(ifcondcont #t))))
(amb-fail #f))
(set! amb-fail old-amb-fail)
(reverse result))
]))

(define amb-fail '())

(define (initialize-amb-fail)
(set! amb-fail
(lambda(x)
(error 'amb "amb tree exhausted"))))

(define (assert pred)
(if (not pred) (amb)))

(define (fail) (amb))

(define (next) (amb))

;; Use this instead of amb when choices
;; are given as a list xs
(define (choose xs)
(assert (not (null? xs)))
(amb (car xs) (choose (cdr xs))))

;; Repeat this at some strategic points
;; to prevent picking up some solutions
;; from previous irrelevant exercises
(initialize-amb-fail)

;; =======================================
;; Nondeterministic generators
;; sudoku
;; sudoku-box
;; sudoku-row
;; sudoku-split
;; ======================================

;; Solve a sudoku puzzle for a list of nine 9-element 'rows.
;; Valid elements are integers 0 ... 9, where 0 indicates
;; an unknown variable. During initialization these zeros are
;; replaced by lists of valid domains. See three examples
;; at the bottom of this file.
;;
;; The constraints:
;; + Elements at each row are distinct
;; + Elements at each column are distinct
;; + Elements at each 3x3 box are distinct
;;
;; The basic unit of operation is nondeterministic procedure
'sudoku-box,
;; which operates on 3x3 boxes. During processing boxes are converted
;; to rows, then to columns and then back to boxes.
;;
;; The algorithm is made of three parts:
;; 1. Prune the solution space via deterministic recursive
;; function 'prune, which reduces domains whenever possible
;; by examining consistency of boxes, rows and columns.
;; 2. Prune the solution space via nondeterministic recursive
;; function 'reduce, which dissassembles and then assembles again
;; the boxes, rows and columns - simplifying in process the ovarall
;; representation of the puzzle.
;; 3. Split the puzzle into several puzzles via nondeterministic
;; function 'split and apply steps 2, 3 to each branch in succession

;; until one of the branches succeeds.
;;
;; Some puzzles are completely solved during the first two stages
;; alone. Most difficult ones need the splitting stage or several
;; such stages.
;;
(define (sudoku rows)

(define (recursive-split boxes)
(let ((splitted-boxes (sudoku-split boxes)))
(if (done? splitted-boxes)
(boxes->rows splitted-boxes)
(recursive-split splitted-boxes))))
(let (
(pruned-boxes (prune (map box-init (rows->boxes rows)))))
(if (done? pruned-boxes)
(boxes->rows pruned-boxes)
(let (
(reduced-boxes (reduce pruned-boxes)))
(if (done? reduced-boxes)
(boxes->rows reduced-boxes)
(recursive-split reduced-boxes))))))

;; Generate the first available nondeterministic
;; solution for the 'box, subject to the constraint
;; that all elements of this 3x3 box are distinct.
(define (sudoku-box box)
(define (choice x) (if (integer? x) x (choose x)))
(let ((sbox (map (lambda(n)(map choice (list-ref box n))) '(0 1
2))))
(assert (distinct? (apply append sbox)))
sbox))

;; Generate the first available nondeterministic
;; solution for the 'row, subject to the constraint
;; that all elements of the row are distinct.
(define (sudoku-row row)
(define (choice x) (if (integer? x) x (choose x)))
(let ((srow (map choice row)))
(assert (distinct? srow))
srow))

;; Split a sudoku problem into n ambivalent choices
;; of simpler sudoku problems.
;;
;; The split occurs at a box number k, which is
;; decomposed into n simpler boxes via application
;; (bag-of (sudoku-box abox))). The components
;; are then set one by one at the index k of original
;; list of boxes -- effectively forming n versions of
;; the former.
;;
;; The box to be decomposed is chosen as the one
;; which has minimal number of admissible solutions,
;; but greater than 1.
;;
;; Return one of several possible lists of reduced
;; boxes, subject to the constraint that such a list
;; has not been reduced to an empty list.
(define (sudoku-split boxes)
(define sizes (map (lambda(box)(length (bag-of (sudoku-box box))))
boxes))
(define min-size (minimum (filter (lambda(x)(> x 1)) sizes)))
(define k
(caar
(filter
(lambda(x)(= (cadr x) min-size))
(zip (iota 0 8) sizes))))
(define bag (bag-of (sudoku-box (list-ref boxes k))))
(display "Splitting ...\n");
(let* (
(split-boxes (choose (map (lambda(u)(list-set boxes k u)) bag)))
(reduced-boxes (reduce split-boxes))
)
(assert (not (null? reduced-boxes)))
reduced-boxes ))

;; =======================================
;; Initialization procedure
;; ======================================

;; Initialize 'box by replacing each unknown
;; variable (initially represented by 0) by a list
;; representing its admissible domain.
(define (box-init box)
(define (choice x)
(cond
((zero? x) ys)
(else x)))
(define cs '(1 2 3 4 5 6 7 8 9))
(define xs (apply append box))
(define ys (set-difference cs xs))
(list
(map choice (list-ref box 0))
(map choice (list-ref box 1))
(map choice (list-ref box 2))))

;; =======================================
;; Counts and other auxiliary procedures
;; ======================================

;; Set object 'x at 'n position of the 'list
(define (list-set list n x)
(append (take n list) (cons x (drop (+ n 1) list))))

;;A set difference between two sets
(define (set-difference xs ys)
(filter (lambda(x)(not (member x ys))) xs))

;; True if all list elements are distinct
(define (distinct? xs)
(cond
((null? xs) #t)
((member (car xs) (cdr xs)) #f)
(else (distinct? (cdr xs)))))

;; A count of unconstrained solutions
;; for a given 'box
(define (permutation-count box)
(fact
(length
(filter list?
(apply append box)))))

;; Count of known values in sudoku puzzle
(define (known-elements-count boxes)
(apply +
(map (lambda(box)(length (filter integer? (apply append box))))
boxes)))

;; True if a puzzle is solved
(define (done? boxes)
(= (known-elements-count boxes) 81))

;; =======================================
;; Conversions
;; boxes->rows
;; rows->boxes
;; transpose
;; ======================================

;; Convert a list of nine 3X3 boxes into a list of 9 rows
(define (boxes->rows boxes)
(define (box k) (list-ref boxes k))
(define (box-row k n) (list-ref (box k) n))
(list
(append (box-row 0 0) (box-row 1 0) (box-row 2 0))
(append (box-row 0 1) (box-row 1 1) (box-row 2 1))
(append (box-row 0 2) (box-row 1 2) (box-row 2 2))

(append (box-row 3 0) (box-row 4 0) (box-row 5 0))
(append (box-row 3 1) (box-row 4 1) (box-row 5 1))
(append (box-row 3 2) (box-row 4 2) (box-row 5 2))

(append (box-row 6 0) (box-row 7 0) (box-row 8 0))
(append (box-row 6 1) (box-row 7 1) (box-row 8 1))
(append (box-row 6 2) (box-row 7 2) (box-row 8 2))))

;; Convert a list of 9 rows into a list of 9 boxes
(define (rows->boxes m)
(define c1 (map (lambda(x)(take 3 x)) m))
(define c2 (map (lambda(x)(take 3 (drop 3 x))) m))
(define c3 (map (lambda(x)(drop 6 x)) m))
(list
(take 3 c1) ;; b11
(take 3 c2) ;; b12
(take 3 c3) ;; b13
(take 3 (drop 3 c1)) ;; b21
(take 3 (drop 3 c2)) ;; b22
(take 3 (drop 3 c3)) ;; b23
(drop 6 c1) ;; b31
(drop 6 c2) ;; b32
(drop 6 c3))) ;; b33

;; Transpose a matrix
;; (transpose '((1 2 3) (4 5 6))) ==> ((1 4) (2 5) (3 6))
(define (transpose matrix)
(map (lambda(n)(
map (lambda(row)(list-ref row n)) matrix))
(iota 0 (- (length (car matrix)) 1))))

;; =======================================
;; Deterministic pruning
;; prune-row
;; prune-box
;; prune
;; ======================================

;; Recursively prune lists of domains inside the row xs
;; by removing those values that have their counterparts
;; in the integer subset of xs, which represent known values.
;; During the process replace domains of size 1, such as (9),
;; by their contents, such as 9 -- effectively eliminating
;; some unknowns and enlarging the subset of solved variables.
(define (prune-row xs)
(define iset (filter integer? xs))
(define (prune/aux xs iset n)
(define (f x)
(if (integer? x) x (g (set-difference x iset))))
(define (g x)
(if (null? (cdr x)) (car x) x))
(define ys (map f xs))
(define new-iset (filter integer? ys))
(define k (length new-iset))
(cond
((= k n) ys)
(else (prune/aux ys new-iset k))))
(prune/aux xs iset (length iset)))

;; Prune the 'box using the function 'prune-row.
(define (prune-box box)
(define xs (prune-row (apply append box)))
(list (take 3 xs) (take 3 (drop 3 xs)) (drop 6 xs)))

;; Prune the list of 'boxes by recursively
;; pruning first the boxes, then the rows
;; and finally the columns -- until the total
;; number of known elements reaches some limit,
;; which no longer can be improved upon via
;; this procedure.
(define (prune boxes)
(define (loop knowns boxes)
(define count (known-elements-count boxes))
(cond
((> count knowns)
(begin
(report count)
(loop count (prune/aux boxes))))
(else boxes)))
(define (report count)
(display "Pruning: Count of known elements = ")
(display count)
(newline)
count)

(define (prune/aux boxes)
(rows->boxes
(transpose
(map prune-row
(transpose
(map prune-row
(boxes->rows
(map prune-box boxes))))))))
(loop 0 boxes))

;; =======================================
;; Nondeterministic reductions
;; reduce-box
;; reduce-row
;; reduce
;; ======================================

;; Reduce the 'box to a simpler form
;; by disassembling it first via function sudoku-box,
;; then unionizing the result, removing duplicates
;; and finally pruning the resulting box.
;; Consequently, some unknowns may become known
;; and some remaining unknowns may have their domains
;; reduced.
;; Example:
;; (reduce-box '((1 (5 7 9) (5 7)) (8 (6 7 9) (3 7)) ((3 5) 4 2)))
;; ==> ((1 9 (5 7)) (8 6 (7 3)) ((3 5) 4 2))
(define (reduce-box box)
(define bag (bag-of (sudoku-box box)))
(define nub-box (lambda(u)(map nub u)))
(define zip-box (lambda(u)(apply zip u)))
(cond
((null? bag) '())
(else (prune-box
(map nub-box
(map zip-box
(apply zip bag)))))))

;; Reduce the 'row to a simpler form
;; by disassembling it first via function sudoku-row,
;; then unionizing the result, removing duplicates
;; and finally pruning the resulting row.
;; Consequently, some unknowns may become known
;; and some remaining unknowns may have their domains
;; reduced.
;; Example of successful reduction:
;; (reduce-row '((8 6) 9 1 2 3 4 (6 5) 7 (5 6)))
;; ==> ( 8 9 1 2 3 4 (6 5) 7 (5 6))
;;
(define (reduce-row row)
(define bag (bag-of (sudoku-row row)))
(cond
((null? bag) '())
(else (prune-row (map nub (apply zip bag))))))

;; Reduce the list of 'boxes by recursively
;; reducing first the boxes, then the rows
;; and finally the columns -- until the total
;; number of known elements reaches some limit,
;; which no longer can be improved upon via
;; this procedure.
;; Return reduced list of 9 boxes or an empty
;; list in case of violated constraints.
(define (reduce boxes)
(define (loop knowns boxes)
(define count (known-elements-count boxes))
(cond
((null? boxes) boxes)
((> count knowns)
(begin
(report count)
(loop count (reduce/aux boxes))))
(else boxes)))
(define (report count)
(display "Reducing: Count of known elements = ")
(display count)
(newline)
count)

(define (reduce/aux boxes)
(let ((reduced-rows
(map reduce-row (boxes->rows (map reduce-box boxes)))))
(cond
((some null? reduced-rows) '())
(else
(let ((reduced-columns
(map reduce-row (transpose reduced-rows))))
(cond
((some null? reduced-columns) '())
(else (rows->boxes (transpose
reduced-columns)))))))))
(loop 0 boxes))

;; =======================================
;; Some semi-standard functions which I do
;; not reproduce here, but just import them
;; to show their usage. Most likely you
;; have your own versions of such functions.
;; ======================================

;;(take n xs), take n elements from a list
(define take (from module-hof take))

;;(drop n xs), drop n elements from a list
(define drop (from module-hof drop))

;;(product xs), a numerical list product
(define product (from module-hof product))

;;(fact n), a definition of factorial
(define fact (from module-hof fact))

;;(nub xs), eliminate duplicates from a list
(define nub (from module-hof nub))

;;(zip xs ys ...), zip n lists into a list of n-tuples
;;(zip '(1 2 3) '(a b)) ==> ((1 a) (2 b))
(define zip (from module-hof zip));

;; Generate list of indices in a given range
;; (iota -1 4) ==> (-1 0 1 2 3 4)
;; (iota 4 -1) ==> (4 3 2 1 0 -1)
(define iota (from module-hof iota))

;; A minimal value from a numerical list
;; (minimum '(6 3 9)) ==> 3
(define minimum (from module-hof minimum))

;; filter :: (a -> boolean) -> (List a) -> (List a)
;; (filter even? '(-2 -9 0 4 -1 5)) ==> (-2 0 4)
(define filter (from module-hof filter))

;; some :: (a -> boolean) -> (List a) -> boolean
;; (some odd? '(2 4 5 7 8 10)) ==> #t
(define some (from module-hof some))

#|
================== Examples ===================

;; The easiest example
(define pacific '(
(8 6 0 3 0 0 0 0 9)
(9 5 0 0 0 8 0 0 1)
(1 0 0 0 4 2 0 0 8)

(7 0 0 0 0 0 0 0 0)
(4 0 0 5 6 9 0 0 7)
(0 0 0 0 0 0 0 0 2)

(3 0 0 7 8 0 0 0 4)
(2 0 0 4 0 0 0 7 5)
(6 0 0 0 0 1 0 9 3)))

(sudoku pacific)
==>
Pruning: Count of known elements = 31
Pruning: Count of known elements = 37
Pruning: Count of known elements = 48
Reducing: Count of known elements = 48
Reducing: Count of known elements = 63
Reducing: Count of known elements = 75
Reducing: Count of known elements = 81
(
(8 6 4 3 1 5 7 2 9)
(9 5 2 6 7 8 4 3 1)
(1 7 3 9 4 2 5 6 8)

(7 3 9 8 2 4 1 5 6)
(4 2 1 5 6 9 3 8 7)
(5 8 6 1 3 7 9 4 2)

(3 9 5 7 8 6 2 1 4)
(2 1 8 4 9 3 6 7 5)
(6 4 7 2 5 1 8 9 3))

==============================

;; Medium complexity
(define classic '(
(0 2 0 0 5 8 7 0 0)
(0 0 9 0 0 0 0 0 0)
(7 3 0 0 1 0 0 0 0)

(1 0 0 0 0 2 3 6 0)
(8 0 0 0 0 0 0 0 5)
(0 4 2 1 0 0 0 0 7)

(0 0 0 0 3 0 0 7 2)
(0 0 0 0 0 0 8 0 0)
(0 0 6 5 8 0 0 1 0)))

(sudoku classic)
==>
Pruning: Count of known elements = 26
Pruning: Count of known elements = 28
Pruning: Count of known elements = 33
Reducing: Count of known elements = 33
Reducing: Count of known elements = 43
Reducing: Count of known elements = 48
Reducing: Count of known elements = 51
Reducing: Count of known elements = 53
Reducing: Count of known elements = 69
Reducing: Count of known elements = 79
Reducing: Count of known elements = 81
(
(6 2 1 3 5 8 7 4 9)
(5 8 9 2 4 7 6 3 1)
(7 3 4 9 1 6 2 5 8)

(1 9 5 8 7 2 3 6 4)
(8 6 7 4 9 3 1 2 5)
(3 4 2 1 6 5 9 8 7)

(9 1 8 6 3 4 5 7 2)
(4 5 3 7 2 1 8 9 6)
(2 7 6 5 8 9 4 1 3))

==========================
;; Quite complex example
(define vintage '(
(0 0 8 0 0 0 1 5 0)
(0 0 0 0 0 1 8 0 0)
(3 0 5 4 0 0 0 0 9)

(5 0 0 0 0 9 0 0 0)
(0 9 0 2 3 4 0 7 0)
(0 0 0 1 0 0 0 0 8)

(4 0 0 0 0 5 9 0 1)
(0 0 6 7 0 0 0 0 0)
(0 5 3 0 0 0 2 0 0)))

(sudoku vintage)
==>
Pruning: Count of known elements = 27
Pruning: Count of known elements = 28
Reducing: Count of known elements = 28
Reducing: Count of known elements = 43
Reducing: Count of known elements = 47
Splitting ...
Reducing: Count of known elements = 49
Reducing: Count of known elements = 54
Reducing: Count of known elements = 61 <== leads to a failure
Reducing: Count of known elements = 49 <== backtrack
Reducing: Count of known elements = 51
Splitting ...
Reducing: Count of known elements = 54
Reducing: Count of known elements = 57
Reducing: Count of known elements = 62
Reducing: Count of known elements = 75
Reducing: Count of known elements = 81
(
(7 4 8 3 9 2 1 5 6)
(2 6 9 5 7 1 8 4 3)
(3 1 5 4 8 6 7 2 9)

(5 7 4 8 6 9 3 1 2)
(8 9 1 2 3 4 6 7 5)
(6 3 2 1 5 7 4 9 8)

(4 8 7 6 2 5 9 3 1)
(9 2 6 7 1 3 5 8 4)
(1 5 3 9 4 8 2 6 7))

|#

#|

===============================================

Copyright (C) Jan Skibinski (2006). All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
check-contract,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


|#