Recap: Scala Basics

• Expressions, Values, Types

• Functions

• Collections

Today

• Compilation and Running

• More on Iteration and Recursion

Compiling and Running

To make an executable, put the functions in a file

e.g. lec-iterators.scala

object Freq { ... }

compile with

$ scalac lec-iterators.scala

and run with

$ scala Freq lec-iterators.markdown
$ scala Freq foo.txt
...

Compiling and Running

Or run in the REPL

scala> import Freq._
scala> val m = Freq("caterpillar")
scala> Freq.show(m, 1)
c : #
a : ##
e : #
i : #
r : ##
t : #
l : ##
p : #

Today: Iteration AND Recursion

Elegant way to systematically

1. Generate Combinations

2. Search Combinations

3. Generate + Search Combinations

Lets write a Polymorphic Frequency Finder

Lets write a polymorphic frequency finder.

def freq[A](xs: Iterable[A]): HashMap[A, Int] = {
  val freqMap = new HashMap[A, Int]
  for (x <- xs) {
    freqMap(x) = 1 + freqMap.getOrElse(x, 0)
  }
  freqMap
}

Iterable[A] describes objects that can be iterated over...

Lets write a Polymorphic Frequency Finder

Can run it on Strings

scala> freq("caterillar")
res: scala.collection.mutable.HashMap[Char,Int]
  = Map(c -> 1, a -> 2, e -> 1, i -> 1, r -> 2, t -> 1, l -> 2)

or List

scala> freq(List(1,2,1,13,1,2,1,3,31,12,1))
res: scala.collection.mutable.HashMap[Int,Int]
     = Map(12 -> 1, 3 -> 1, 13 -> 1, 1 -> 5, 2 -> 2, 31 -> 1)

or ...

Today: Iteration AND Recursion

Elegant way to systematically

1. Generate Combinations

2. Search Combinations

3. Generate & Search Combinations

QUIZ: Nested for-loops

Of course, you can nest for-loops too:

val res = for (xs <- Array("cat", "dog");
               x  <- xs)
          yield x

What is the type of res?

A. String

B. List[String]

C. Iterator[String]

D. List[Char]

E. Iterator[Char]

Nested for-loops

Of course, you can nest for-loops too:

val res = for (xs <- Iterator("cat", "dog", "mouse");
               x  <- xs)
          yield x

What is the type of res?

Type Of Output Collection

• Is the same as the first collection looped over,

• but actual contents are of the yielded value

• Hence, correct answer: E. Iterator[Char]

QUIZ: Nested for-loops

val res = for ( i <- List(1, 2)
              ; j <- Iterator("a", "b"))
          yield (i, j)

What is the value of res ?

A. Nothing (Type Error)

B. List(1, 2, "a", "b")

C. List(1, "a", 2, "b")

D. List((1, "a"), (2, "b"))

E. List((1,"a"), (1,"b"), (2,"a"), (2,"b"))

Nested for Loops

val res = for ( i <- List(1, 2)
              ; j <- List("a", "b"))
          yield (i, j)

Here is how it goes down:

• i <- 1
• \(\quad\) j <- a
• \(\quad \quad\) yield (1, "a")
• \(\quad\) j <- b
• \(\quad \quad\) yield (1, "b")
• i <- 2
• \(\quad\) j <- a
• \(\quad \quad\) yield (2, "a")
• \(\quad\) j <- b
• \(\quad \quad\) yield (2, "b")

• E: List((1,"a"), (1,"b"), (2,"a"), (2,"b"))

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

• Words.scala

• Crack.scala

Why?

Not to make you write

words.toList.filter(...).toIterator     // yuck

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Not to make you write

words.toList.filter(...).toIterator     // yuck

which is almost the same as

words.filter(...)                       // sweet!

• The yucky version is not just longer ...

• ... it can be massively inefficient!

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Because Iterator lazily computes one element at a time

At each .next call

• Does not build the entire sequence up at once! (as List does)

• Does not store the entire sequence in memory! (as List does)

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Because Iterator lazily computes one element at a time

At each .next call

• Does not build the entire sequence up at once! (as List does)

• Does not store the entire sequence in memory! (as List does)

So Iterator good for operating on big data streams

• Like large dictionaries of words ...

• ... and transformations thereof

PSA: Why choose Iterator vs. List

Iterator is lazy, good for operating on big data streams

def allVowels(megaDictionary: Iterator[String]): Iterator[String] =
  for { w <- megaDictionary
      ; if hasAllVowels(w)  }
  yield w

• Iterator uses O(1) memory (at any given time) ...

def allVowels(megaDictionary: List[String]): List[String] =
  for (w <- megaDictionary
       if hasAllVowels(w))
  yield w

• List uses O(N) memory, where N = megaDictionary size.

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Iterator is lazy, good for operating on big data streams

def txReverse(megaDictionary: Iterator[String]): Iterator[String] =
  for (w <- megaDictionary
       c <- Iterator(w, reverse(w))
  yield c

• Iterator uses O(1) memory (at any given time) ...

def txReverse(megaDictionary: List[String]): List[String] =
  for (w <- megaDictionary
       c <- Iterator(w, reverse(w))
  yield c

• List uses O(N) memory, where N = megaDictionary size.

Note: Only difference is in the type

PSA: Why choose Iterator vs. List

We chose Iterator and not List for password crack

Iterator is lazy, good for operating on big data streams

So why not always use Iterator ?

• Cannot reuse after reaching the end

• Cannot rewind Iterator

• Cannot randomly access (efficiently)

PSA: Bottom-line

For PA5

• Stick to using for and yield and HOFS

• Do not convert from Iterator to List

• Or you will have all sorts of (unsolvable) memory issues

QUIZ: Combining Iteration & Recursion

def bitStrings(n:Int) : List[String] =
  if (n <= 0) {
    List("")
  } else {
    for (c <- List("0", "1");
         s <- bitStrings(n-1))
    yield(c + s)
  }

What does bitStrings(2) return?

A. Nothing (Type Error)

B. Nothing (Infinite Loop)

C. List()

D. List("0", "1")

E. List("00", "01", "10", "11")

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(0) ==> List()

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(1) ==> ?

• c <- "0"
• \(\quad\) s <- ... Nothing! (because bitStrings(0) ==> List())
• c <- "1"
• \(\quad\) s <- ... Nothing! (because bitStrings(0) ==> List())

Combining Iteration & Recursion

Consider the following function:

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

Here is what happens (lets work backwards)

bitStrings(1) ==> List()

• c <- "0"
• \(\quad\) s <- ... Nothing! (because bitStrings(0) ==> List())
• c <- "1"
• \(\quad\) s <- ... Nothing! (because bitStrings(0) ==> List())

• ... same for bitStrings(2), bitStrings(3) etc.

Recap: Nested Loops

Nested loops are like cartesian products

scala> for ( i <- List(1, 2)
           ; j <- List("a", "b"))
       yield (i, j)
res0: List[(Int, String)] = List((1,a), (1,b), (2,a), (2,b))

Result is empty if either the first sequence is empty

scala> for ( i <- List(1,2)
           ; j <- List())
       yield (i, j)
res1: List[(Int, String)] = List()

or the second sequence is empty

scala> for ( i <- List()
           ; j <- List("a", "b"))
       yield (i, j)
res2: List[(Nothing, String)] = List()

Combining Iteration & Recursion

def bitStrs(n: Int) : List[String] =
  if (n <= 0) { List() } else {
   for (c <- List("0", "1");
        s <- bitStrs(n-1))
   yield(c + s)
  }

How can we fix this function so that:

bitStrs(1) ==> List("0","1")

bitStrs(2) ==> List("00","01","10","11")

bitStrs(3) ==> List("000","001","010","011","100","101","110","111")

etc. ?

• Key: Fix the base case (bitStrs(0))

Combining Iteration & Recursion

Base Case

• Empty string ""

• Only bit-string of length 0

def bitStrings(n: Int) : List[String] =
  if (n <= 0) { List("") } else {
   for (c <- List("0", "1");
        s <- bitStrings(n-1))
   yield(c + s)
  }

QUIZ: What is the value of res ?

def foo(w: String) : List[String] =
  if (w == "")  { List("") } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

val res = foo("go")

Hint "sunday".substring(0, 1) ==> "s" and "sunday".substring(1) ==> "unday"

A. Nothing (Infinite Loop)

B. List()

C. List("", "o", "g", "go")

D. List("")

E. List("o", "g", "go")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- subStrings(w.substring(1)))
    yield(c + s)

Again, lets work backwards

subStrings("") ==> List("")

• Correct base case!

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("o") ==> ?

• c <- ""
• \(\quad\) s <- "" (as subStrings("") ==> List(""))
• \(\quad \quad\) yield ("" + "")

• c <- "o"
• \(\quad\) s <- "" (as subStrings("") ==> List(""))
• \(\quad \quad\) yield ("o" + "")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("o") ==> List("", "o")

• c <- ""
• \(\quad\) s <- "" (because subStrings("") ==> List(""))

• \(\quad \quad\) yield ("" + "")

• c <- "o"
• \(\quad\) s <- "" (because subStrings("") ==> List(""))

• \(\quad \quad\) yield ("o" + "")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("go") ==> ?

• c <- ""
• \(\quad\) s <- "" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("" + "")
• \(\quad\) s <- "o" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("" + "o")
• c <- "g"
• \(\quad\) s <- "" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("g" + "")
• \(\quad\) s <- "o" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("g" + "o")

Combining Iteration & Recursion

def subStrings(w: String) : List[String] =
  if (w == "")  { List(w) } else
    for (c <- List("", w.substring(0, 1));
         s <- foo(w.substring(1)))
    yield(c + s)

Lets work backwards . subStrings("go") ==> List("", "o", "g", "go")

• c <- ""
• \(\quad\) s <- "" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("" + "")
• \(\quad\) s <- "o" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("" + "o")
• c <- "g"
• \(\quad\) s <- "" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("g" + "")
• \(\quad\) s <- "o" (because subStrings("o") ==> List("", "o"))
• \(\quad \quad\) yield ("g" + "o")

Combining Iteration & Recursion

Mega Hint for PA5

substrings is almost identical to transformCapitalize

subStrings

Replace each character "c" by either "c" or ""

transformCapitalize

Replace each character "c" by either "c" or "C"

• same holds for transformDigits

• learn to spot the patterns...

Today: Iteration AND Recursion

Elegant way to systematically

1. Generate Combinations

2. Search Combinations

3. Generate & Search Combinations

QUIZ: Systematic Search/Query

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k)
          yield (i, j, k)

What is the value of res ?

A. Vector()

B. Vector((3,4,5), (6,8,10))

C. Vector((6,8,10), (3,4,5))

D. Vector((3,4,5), (4,3,5), (6,8,10), (8,6,10))

E. Vector((8,6,10), (6,8,10), (4,3,5), (3,4,5))

Systematic Search/Query

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k)
          yield (i, j, k)

Is equivalent to:

val res = (for (i <- 1 to 10;j <- 1 to 10; k <- 1 to 10)
           yield (i, j, k)
          ).filter { case (i, j, k) => i*i + j*j == k*k}

which is equivalent to:

Vector( (1,1,1), (1,1,2), ..., (1,1,10),  (1,2,1),..., (1,10,10)
      , (2,1,1), (2,1,2), ..., (2,1,10),  (2,2,1),..., (2,10,10)
      , ...,
      ,(10,1,1), (10,1,2),...,(10,1,10), (10,2,1),...,(10,10,10)
      ).filter { case (i, j, k) => i*i + j*j == k*k}

Systematic Search/Query

Note: filter Preserves Sequence Order

Hence, the expression

Vector( (1,1,1), (1,1,2), ..., (1,1,10),  (1,2,1),..., (1,10,10)
      , (2,1,1), (2,1,2), ..., (2,1,10),  (2,2,1),..., (2,10,10)
      , ...,
      ,(10,1,1), (10,1,2),...,(10,1,10), (10,2,1),...,(10,10,10)
      ).filter { case (i, j, k) => i*i + j*j == k*k}

evaluates to ...

D. Vector((3,4,5), (4,3,5), (6,8,10), (8,6,10))

• How would you avoid duplicates?

Systematic Search/Query

• How would you avoid duplicates?

• Only count tuples where i <= j to avoid ordering issues.

Systematic Search/Query

• How would you avoid duplicates?

• Only count tuples where i <= j to avoid ordering issues.

val res = for (i <- 1 to 10;
               j <- 1 to 10;
               k <- 1 to 10
               if i*i + j*j == k*k && i <= j)
          yield (i, j, k)

Case Classes

case class Name(x1: T1, x2: T2, ..., xn: TN)

Creates a class Name with

1. Immutable fields x1 of type T1 ... xn of type Tn

2. Constructor method for object creation

3. Extractor method for pattern matching (later...)

Case Classes: Example Novel

Here is a case class (just fancy records for now...)

case class Novel(title: String, author: String)

You can create instances thus (no need for new because Scala generates an apply for us)

scala> val n1 = Novel("A Feast For Crows", "George R. R. Martin")
n1: Novel = Novel(A Feast For Crows,George R. R. Martin)

// which is equivalent from Scala's view to...

scala> val n2 = Novel.apply("A Feast For Crows", "George R. R. Martin")
n2: Novel = Novel(A Feast For Crows,George R. R. Martin)

and access fields like so

scala> n1.author
n1: String = George R. R. Martin

Case Classes: Example Album

Here is another case class (just fancy records for now...)

case class Album(title: String, artist: String)

You can create instances thus (no need for new again)

scala> val a = Album("We are glitter", "Goldfrapp")
a: Album = Album(We are glitter,Goldfrapp)

Database Style Queries

Suppose we have a "database" of novels

val novels =
  List( Novel ( "Skinny Legs and All"
              , "Tom Robbins")

      , Novel ( "Breakfast of Champions"
              , "Kurt Vonnegut")

      , Novel ( "An Object of Beauty"
              , "Steve Martin")

      , Novel ( "Sophie's Choice"
              , "William Styron")

      , Novel ( "The Other"
              , "Tom Tryon")
      )

Database Style Queries

... and a "database" of albums

val albums =
  List( Album ( "Rare Bird Alert"
              , "Steve Martin")

      , Album ( "Paper Airplane"
              , "Alison Krauss and Union Station")

      , Album ( "Earl Scruggs and Friends"
              , "Earl Scruggs")
      )

Database Style Queries

... and a "database" of movies

val movies =
  List( Movie ("Airplane",
               List ( "Leslie Nielsen", "Robert Stack"))

      , Movie ("Young Frankenstein",
               List ("Gene Wilder", "Madeline Kahn"))

      , Movie ("The Pink Panther",
               List ("Steve Martin", "Jean Reno"))
      )

Query: Is there tripleThreat ?

A person who has

1. written a book,
2. acted in a movie,
3. performed in an album ?

Query: Is there a tripleThreat ?

A person who has

1. written a book,
2. acted in a movie,
3. performed in an album ?

Cue, nested loop query...

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

Query: Is there a tripleThreat ?

A person who has

1. written a book,
2. acted in a movie,
3. performed in an album ?

Cue, nested loop query...

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

Which evaluates to

tripleThreats: List[String] = List(Steve Martin)

• Not necessarily very efficient of course ...

Even more magical: From Loops-to-SQL

You can define a special collection type such that the expression

for (n <- novels;
     a <- albums;
     m <- movies;
     if (n.author == a.artist && m.actors.contains (n.author)))
yield (n.author)

is automatically converted into an SQL (DataBase) query ...!

• Slick (formerly ScalaQL)

• .NET LINQ

• Monad Comprehensions

• Not on final...

Today: Iteration AND Recursion

Elegant way to systematically

1. Generate Combinations

2. Search Combinations

3. Generate & Search Combinations

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and n columns

Find a placement of n queens so none can kill each other!

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

One queen q1 can kill another q2 if

def canKill(q1: XY, q2: XY) =
  q1._1 == q2._1 ||                          // same row
  q1._2 == q2._2 ||                          // same column
  (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // same diagonal

QUIZ: When is a board safe?

canKill(q1, q2) is true if a queen at q1 can kill another q2

queens : List[XY] is a list of occupied positions

q : XY is a new queen position.

Which expression evaluates to true exactly when none of queens can kill q ?

A. for (qo <- queens) yield !canKill(qo, q)

B. for (qo <- queens) yield canKill(qo, q)

C. queens.exists(!canKill(_,q))

D. queens.forall(!canKill(_,q))

E. queens.map(!canKill(_,q)).foldLeft(true)(_ && _)

When is a board safe?

canKill(q1, q2) is true if a queen at q1 can kill another q2

queens : List[XY] is a list of occupied positions

q : XY is a new queen position.

Board is Safe

• When for each qo in queens, qo cannot kill q

• queens.forall (qo => !(canKill(qo, q))

• D: queens.forall (!(canKill(_, q))

• However, E: is also right. (Why?)

Generate and Search: The N-Queens Puzzle

The first question: what is a solution ?

We represent each queen by its position XY: a pair of (row, col)

type XY = (Int, Int)

One queen q1 can kill another q2 if

def canKill(q1: XY, q2: XY) =
  eqRow(q1, q2) || eqCol(q1, q2) || eqDia(q1, q2)

A queen at q is safe w.r.t. other queens if:

def isSafe(queen: XY, others: List[XY]) =
  others forall (!canKill(_, queen))

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

def placeQueens(columns: Int, row: Int) : List[XY]

Strategy: Recursive Search

To place queens on row r ... 0

• (recursively) place queens on rows r-1 ... 0

• for each column in row r

• return position which isSafe w.r.t. recursive solution

• Can anybody see a problem?

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Problem

• Can be many ways of placing rows r-1...0

• ... but only a few may be compatible with row r !

Solution

• Return all ways of placing rows r-1...0

• Try each placement for row r !

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

def placeQueens(columns: Int, row: Int) : List[List[XY]]

Strategy: Recursive Search

To place queens on row r ... 0

1. (recursively) place queens on rows r-1 ... 0

2. for each (recursive) solution

3. for each column in row r

4. yield position which isSafe w.r.t. recursive solution

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Strategy: Recursive Search

def placeQueens(columns: Int, row: Int) : List[List[XY]] =
  if (row == 0)
    List(List())
  else
    for { queens <- placeQueens(columns, row - 1)
          column <- 1 to columns
          queen   = (row, column)
          if isSafe(queen, queens) }
    yield (queen :: queens)

• Note: the base case!

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 4 Queens

Just printing the 1 solution (of several)

scala> Queens(4, 1)
OOXO
XOOO
OOOX
OXOO

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 8 Queens

Just printing the 1 solution (there are many)

scala> Queens(8, 1)
OOOXOOOO
OXOOOOOO
OOOOOOXO
OOXOOOOO
OOOOOXOO
OOOOOOOX
OOOOXOOO
XOOOOOOO

Generate and Search: The N-Queens Puzzle

Given a chess board of size n rows and columns

Find a placement of n queens so none can kill each other!

Lets run it: 2 or 3 Queens

scala> Queens(2, 1)

scala> Queens(3, 1)

scala>

• Say what?! There are no solutions for \(N = 2, 3\)

Generate and Search: A Sudoku Solver

Given A sudoku puzzle

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

Generate and Search: A Sudoku Solver

Find A solution

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

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Representing Squares

We represent each square by its position XY: a pair of (row, col)

type XY = (Int, Int)

Generate and Search: Sudoku Solver

The first question: what is a sudoku board ?

Representing Squares

We represent each square by its position XY: a pair of (row, col)

type XY = (Int, Int)

Representing Boards

We represent the board by a (partial) map from XY to Int

type Board = Map[XY, Int]

• How is a blank (unfilled) square represented?

• Simple: the position XY is just not in the map!

Representing Sudoku Boards

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

is represented by

Map ((0, 0) -> 5, (0, 1) -> 3, (0, 4) -> 7,
     (1, 0) -> 6, (1, 3) -> 1, (1, 4) -> 0, (1, 5) -> 5,
     (2, 1) -> 0, (2, 2) -> 8, (2, 7) -> 6,
     (3, 0) -> 8, (3, 4) -> 6, (3, 8) -> 3,
     (4, 0) -> 4, (4, 3) -> 8, (4, 5) -> 3, (4, 8) -> 1,
     (5, 0) -> 7, (5, 4) -> 2, (5, 8) -> 6,
     (6, 1) -> 6, (6, 6) -> 2, (6, 7) -> 8,
     (7, 3) -> 4, (7, 4) -> 1, (7, 5) -> 0, (7, 8) -> 5,
     (8, 4) -> 8, (8, 7) -> 7, (8, 8) -> 0)

Generate and Search: Sudoku Solver

Given a partially filled Sudoku Board

Find a way to fill in all squares

Strategy: Recursive Search

• If no blank squares on board then
• return board!

• Else pick blank with fewest possible choices
• for each choice
• recursively solve board with blank filled by choice

Generate and Search: Sudoku Solver

Given a partially filled Sudoku Board

Find a way to fill in all squares

Strategy: Recursive Search

def solve(b: Board) : Iterator[Board] = {
  val blanks = candidates(b)
  if (blanks.isEmpty) Iterator(b)
  else {
    val (xy, choices) = blanks minBy (_._2.length)
    for (choice <- choices.toIterator;
         bFull  <- solve(b + (xy -> choice)))
    yield bFull
  }
}

Generate and Search: Sudoku Solver

def solve(b: Board) : Iterator[Board] = {
  val blanks = candidates(b)
  if (blanks.isEmpty) Iterator(b)
  else {
    val (xy, choices) = blanks minBy (_._2.length)
    for (choice <- choices.toIterator;
         bFull  <- solve(b + (xy -> choice)))
    yield bFull
  }
}

Questions

• Why do we compute all solutions?
• Why the .toIterator call?

Generate and Search: Sudoku Solver

Details: Computing candidates for a board

def candidates (b: Board) =
  for { x <- 0 until 9 ;
        y <- 0 until 9 ;
        if (!b.isDefinedAt((x,y))) ;
        xy   = (x, y) ;
        vals = (0 until 9) diff (alreadyTaken(x,y,b)) }
  yield (xy, vals)

• Loop over all squares,
• Filter the ones that are not defined,
• Prune the already taken values for the square,
• Yield a tuple of the cell and remaining values.

Generate and Search: Sudoku Solver

Details: Computing alreadyTaken values for a square

def alreadyTaken(x: Int, y: Int, b: Board) =
  for (p <- pointsOfCol(x) ++
            pointsOfRow(y) ++
            pointsOfGrid(x, y)
       if b.isDefinedAt(p))
  yield b(p)

• Loop over squares in same row, col, grid
• Yield values at the square (if defined)

Generate and Search: Sudoku Solver

Details: Points in Same Grid

def pointsOfGrid(x: Int, y: Int) = {
  val (x0, y0) = ((x/3) * 3,  (y/3) * 3)
  for (px <- x0 until x0 + 3 ;
       py <- y0 until y0 + 3 )
  yield (px, py)
}

Details: Points in Same Row/Column

def pointsOfCol(x: Int) =
  for (y <- 0 until 9) yield (x, y)

def pointsOfRow(y: Int) =
  for (x <- 0 until 9) yield (x, y)

Today: Iteration AND Recursion

Elegant way to systematically

1. Generate Combinations

2. Search Combinations

3. Generate & Search Combinations

How ?

• Recursively generate & solve sub-problems, and

• Loop over candidates & yield valid solutions