Project 73 — Sudoku Puzzle

A1 9
C1 4
QUIT

ek9 sudoku.ek9 < input.txt

Sudoku Puzzle, by Al Sweigart al@inventwithpython.com
  A B C   D E F   G H I
1 5 3 . | . 7 . | . . . 
2 6 . . | 1 9 5 | . . . 
3 . 9 8 | . . . | . 6 . 
  ------+-------+------
4 8 . . | . 6 . | . . 3 
5 4 . . | 8 . 3 | . . 1 
6 7 . . | . 2 . | . . 6 
  ------+-------+------
7 . 6 . | . . . | 2 8 . 
8 . . . | 4 1 9 | . . 5 
9 . . . | . 8 . | . 7 9 

Enter a move, or RESET, UNDO, ORIGINAL, or QUIT:
(For example, a move looks like "B4 9".)

You cannot overwrite the original grid's numbers.
Enter ORIGINAL to view the original grid.
  A B C   D E F   G H I
1 5 3 . | . 7 . | . . . 
2 6 . . | 1 9 5 | . . . 
3 . 9 8 | . . . | . 6 . 
  ------+-------+------
4 8 . . | . 6 . | . . 3 
5 4 . . | 8 . 3 | . . 1 
6 7 . . | . 2 . | . . 6 
  ------+-------+------
7 . 6 . | . . . | 2 8 . 
8 . . . | 4 1 9 | . . 5 
9 . . . | . 8 . | . 7 9 

Enter a move, or RESET, UNDO, ORIGINAL, or QUIT:
(For example, a move looks like "B4 9".)

  A B C   D E F   G H I
1 5 3 4 | . 7 . | . . . 
2 6 . . | 1 9 5 | . . . 
3 . 9 8 | . . . | . 6 . 
  ------+-------+------
4 8 . . | . 6 . | . . 3 
5 4 . . | 8 . 3 | . . 1 
6 7 . . | . 2 . | . . 6 
  ------+-------+------
7 . 6 . | . . . | 2 8 . 
8 . . . | 4 1 9 | . . 5 
9 . . . | . 8 . | . 7 9 

Enter a move, or RESET, UNDO, ORIGINAL, or QUIT:
(For example, a move looks like "B4 9".)

Thanks for playing!

#!ek9
defines module bigbook.sudoku

  defines constant

    GridLength <- 9
    BoxLength <- 3
    Columns <- "ABCDEFGHI"
    //A move is two words, a two-character cell name and a number: "B4 9".
    MoveWords <- 2
    CellNameLength <- 2
    Puzzle <- "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"
    //The grid's own marks, data like the digits: an empty cell, and the lines between the boxes.
    //The rule under a row of boxes is the book's own line, which is not quite the width of a row.
    Empty <- "."
    BoxEdge <- "|"
    BoxRule <- "------+-------+------"

  defines type

    //A cell holds a digit 1-9 or NOTHING AT ALL. Unset IS the empty cell, so the "."
    //exists only at the display edge and can never be mistaken for a value.
    Digit as Integer constrain as
      >= 1 and <= 9

    //The four commands. The Console turns the word the player types into one of these; anything
    //else is an UNSET Command, and that unset value is how a move is told apart from a command.
    Command
      Reset
      Undo
      Original
      Quit

    //Why an entry is not a move, in the order the book checks. A NotAMove entry is not shaped
    //like "B4 9" at all, and the book refuses it without a word.
    MoveProblem
      NotAMove
      NoSuchColumn
      NoSuchRow
      NoSuchNumber

    Dict of (Coord, Digit)
    DictEntry of (Coord, Digit)
    List of Digit
    List of Move

  defines record

    //A grid position used as a Dict KEY - compared by value, so no "x,y" string packing
    //and no split() to get the numbers back out. The shape of lib/Coord.ek9: '<=>' is its
    //sameness, '==' and '<>' are generated from it, and the constructor copies its arguments.
    Coord
      x as Integer: Integer()
      y as Integer: Integer()

      default Coord() as pure

      Coord() as pure
        ->
          px as Integer
          py as Integer

        x :=? Integer(px)
        y :=? Integer(py)

      operator $ as pure
        <- rtn as String: `(${x},${y})`

      default operator ?
      default operator <=>
      default operator #?

    //One move: WHERE and WHAT.
    Move
      at as Coord: Coord()
      digit as Digit: Digit()

      default Move() as pure

      Move() as pure
        ->
          position as Coord
          placed as Digit

        at :=? position
        digit :=? placed

      default operator ?

  defines class

    //THE GAME's state: the grid and the moves made on it, as the book's SudokuGrid class holds them.
    SudokuGrid
      cells as Dict of (Coord, Digit): Dict() of (Coord, Digit)
      moves as List of Move: List() of Move

      SudokuGrid()
        reset()

      //Back to the puzzle as given.
      reset()
        cells: Dict() of (Coord, Digit)
        for y in 0 ... GridLength - 1
          for x in 0 ... GridLength - 1
            at <- Coord(x, y)
            cells += DictEntry(at, givenAt(at))
        moves: List() of Move

      //Places the digit unless the cell is one of the puzzle's givens; true when placed.
      place()
        -> move as Move
        <- rtn as Boolean: not isGiven(move.at)
        if rtn
          cells += DictEntry(move.at, move.digit)
          moves += move

      //Replays the remaining moves onto the puzzle, rather than keeping a copy of the whole
      //grid for every move as the book does.
      undo()
        if not moves.empty()
          keep <- length moves - 1
          kept <- cat moves | head keep | collect as List of Move
          reset()
          for move in kept
            place(move)

      cellAt() as pure
        ->
          x as Integer
          y as Integer
        <- rtn as Digit: cells.getOrDefault(Coord(x, y), Digit())

      row()
        -> y as Integer
        <- rtn as List of Digit: List() of Digit
        for x in 0 ... GridLength - 1
          rtn += cellAt(x, y)

      column()
        -> x as Integer
        <- rtn as List of Digit: List() of Digit
        for y in 0 ... GridLength - 1
          rtn += cellAt(x, y)

      //Box 0 is top left, box 8 bottom right, numbered along each row of boxes.
      box()
        -> index as Integer
        <- rtn as List of Digit: List() of Digit
        left <- (index rem BoxLength) * BoxLength
        top <- (index / BoxLength) * BoxLength
        for y in top ... top + BoxLength - 1
          for x in left ... left + BoxLength - 1
            rtn += cellAt(x, y)

      isSolved()
        <- rtn as Boolean: true
        for i in 0 ... GridLength - 1
          rtn: rtn and isComplete(row(i)) and isComplete(column(i)) and isComplete(box(i))

      default operator ?

    //THE input idiom of this book, copied unchanged from lib/LineInput.ek9 (the reasons are
    //there): read with next(), and every input loop also stops when ended() is true.
    LineInput
      stdin as Stdin: Stdin()
      inputEnded as Boolean: false

      next()
        <- rtn as String: stdin.next()
        if not rtn?
          inputEnded: true

      ended() as pure
        <- rtn as Boolean: Boolean(inputEnded)

      override operator ? as pure
        <- rtn as Boolean: true

    //THE INPUT AND OUTPUT: everything the player sees or types goes through here, worded by Say.
    Console
      stdout as Stdout: Stdout()
      input as LineInput: LineInput()
      say as Say: Say("en")

      Console()
        -> words as Say
        say: words

      showIntroduction()
        stdout.println(say.introduction())

      //The grid is drawn, not worded: computed from the game's cells, with the column letters
      //above it and the box lines sized to the boxes.
      showGrid()
        -> grid as SudokuGrid
        stdout.println(`  ${columnLabels()}`)
        for y in 0 ... GridLength - 1
          line <- `${y + 1} `
          for x in 0 ... GridLength - 1
            line += `${cellText(grid.cellAt(x, y))} `
            if endsBox(x)
              line += `${BoxEdge} `
          stdout.println(line)
          if endsBox(y)
            stdout.println(`  ${BoxRule}`)

      //A command word, or an entry the game accepts as a move. Unset only when the input has ended.
      nextEntry()
        <- rtn as String: String()
        while not rtn? and not input.ended()
          stdout.println("")
          stdout.println(say.askMove())
          if line <- input.next()
            entry <- line.upperCase().trim()
            if commandIn(entry)?
              rtn: entry
            else if problem <- problemWith(entry)
              showProblem(problem, entry)
            else
              rtn: entry
        if rtn?
          stdout.println("")

      //The command a word the player typed names: the book takes its first letter.
      commandIn()
        -> entry as String
        <- rtn as Command: Command()
        if entry.startsWith(say.reset())
          rtn: Command.Reset
        else if entry.startsWith(say.undo())
          rtn: Command.Undo
        else if entry.startsWith(say.original())
          rtn: Command.Original
        else if entry.startsWith(say.quit())
          rtn: Command.Quit

      showCannotOverwrite()
        stdout.println(say.cannotOverwrite())

      showOriginal()
        -> original as SudokuGrid
        stdout.println(say.originalWas())
        showGrid(original)

      showSolved()
        stdout.println(say.solved())

      showGoodbye()
        stdout.println(say.goodbye())

      ended() as pure
        <- rtn as Boolean: input.ended()

      //Each problem in the player's words; a NotAMove entry is refused without a word, as the book
      //refuses it.
      private showProblem()
        ->
          problem as MoveProblem
          entry as String

        if problem == MoveProblem.NoSuchColumn
          stdout.println(say.noColumn(columnIn(entry)))
        else if problem == MoveProblem.NoSuchRow
          stdout.println(say.noRow(rowIn(entry)))
        else if problem == MoveProblem.NoSuchNumber
          stdout.println(say.noNumber(numberIn(entry)))

      //The ONLY place "." appears - the empty cell is unset, not a magic string.
      private cellText()
        -> cell as Digit
        <- rtn as String: cell? <- $cell : Empty

      private columnLabels()
        <- rtn as String: ""
        labels <- ""
        for x in 0 ... GridLength - 1
          labels += `${Columns.subString(x, x + 1)} `
          if endsBox(x)
            labels += "  "
        rtn: labels.trim()

      override operator ? as pure
        <- rtn as Boolean: true

  defines function

    //THE GAME: its rules and its puzzle, with no input or output.

    //THE digit validator. A constrained type PANICS on an out-of-range construction, so the
    //range is checked before the Digit is built - never by constructing and testing.
    toDigit() as pure
      -> text as String
      <- rtn as Digit: Digit()
      if n <- Integer(text) then n >= 1 and n <= GridLength
        rtn: Digit(n)

    //The digit the puzzle gives at a position; unset where the puzzle leaves the cell empty.
    givenAt() as pure
      -> at as Coord
      <- rtn as Digit: Digit()
      index <- (at.y * GridLength) + at.x
      rtn: toDigit(Puzzle.subString(index, index + 1))

    //A "given" is a cell the puzzle fills - asked of the cell, not compared against ".".
    isGiven() as pure
      -> at as Coord
      <- rtn as Boolean: givenAt(at)?

    //A 3x3 box ends after the 3rd and 6th of the 9 cells; the grid's own edge is not drawn.
    endsBox() as pure
      -> index as Integer
      <- rtn as Boolean: (index + 1) rem BoxLength == 0 and index < GridLength - 1

    //Every digit 1-9 exactly once: nine cells that hold all nine digits.
    isComplete() as pure
      -> digits as List of Digit
      <- rtn as Boolean: true
      for d in 1 ... GridLength
        rtn: rtn and digits contains Digit(d)

    //The parts of a move as the player typed them, "B4 9": the cell's column letter, its row, and
    //the number. This is parsing what the player typed, not packing the game's own data.
    moveWordsOf() as pure
      -> entry as String
      <- rtn as List of String: entry.split(/\s+/)

    cellIn() as pure
      -> entry as String
      <- rtn as String: moveWordsOf(entry).getOrDefault(0, "")

    columnIn() as pure
      -> entry as String
      <- rtn as Character: cellIn(entry).first()

    rowIn() as pure
      -> entry as String
      <- rtn as String: cellIn(entry).subString(1, CellNameLength)

    numberIn() as pure
      -> entry as String
      <- rtn as String: moveWordsOf(entry).getOrDefault(1, "")

    //Unset when the entry is a move the grid can take; otherwise the first thing wrong with it.
    problemWith() as pure
      -> entry as String
      <- rtn as MoveProblem: MoveProblem()
      if length moveWordsOf(entry) <> MoveWords or length cellIn(entry) <> CellNameLength
        rtn: MoveProblem.NotAMove
      else if not Columns.indexOf(columnIn(entry))?
        rtn: MoveProblem.NoSuchColumn
      else if not toDigit(rowIn(entry))?
        rtn: MoveProblem.NoSuchRow
      else if not toDigit(numberIn(entry))?
        rtn: MoveProblem.NoSuchNumber

    //The move an entry describes. Only called once problemWith has found nothing wrong with it.
    moveOf() as pure
      -> entry as String
      <- rtn as Move: Move()
      column <- Columns.indexOf(columnIn(entry))
      row <- Integer(rowIn(entry))
      rtn: Move(Coord(column, row - 1), toDigit(numberIn(entry)))

  defines function

    //THE FLOW, one turn of the original's main(): an entry, then the command it names or the move
    //it makes. False when the player quits, or the input ends, before an entry is made.
    takeTurn()
      ->
        grid as SudokuGrid
        console as Console
      <- rtn as Boolean: false

      if entry <- console.nextEntry()
        rtn: true
        switch console.commandIn(entry)
          case Command.Quit
            rtn: false
          case Command.Reset
            grid.reset()
          case Command.Undo
            grid.undo()
          case Command.Original
            console.showOriginal(SudokuGrid())
          default
            //Not a command, so the Console has accepted it as a move.
            if not grid.place(moveOf(entry))
              console.showCannotOverwrite()

  defines function

    //THE language of the words, copied unchanged from lib/Language.ek9: BIGBOOK_LANG when it
    //is set (fr, zh, ...), otherwise en.
    language()
      <- rtn as String: EnvVars().get("BIGBOOK_LANG") ?: "en"

  //THE WORDS: every word the player sees or types. The grid and its marks are not here: the
  //Console draws them from the game's cells.
  defines text for "en"

    Say

      introduction()
        "Sudoku Puzzle, by Al Sweigart al@inventwithpython.com"

      askMove()
        `Enter a move, or RESET, UNDO, ORIGINAL, or QUIT:
(For example, a move looks like "B4 9".)`

      //The commands are told apart by their first letter, as in the book.
      reset()
        "R"

      undo()
        "U"

      original()
        "O"

      quit()
        "Q"

      noColumn()
        -> column as Character
        `There is no column ${column}`

      noRow()
        -> row as String
        `There is no row ${row}`

      noNumber()
        -> number as String
        `Select a number from 1 to ${GridLength}, not ${number}`

      cannotOverwrite()
        `You cannot overwrite the original grid's numbers.
Enter ORIGINAL to view the original grid.`

      originalWas()
        "The original grid looked like this:"

      solved()
        "Congratulations! You solved the puzzle!"

      goodbye()
        "Thanks for playing!"

  defines program

    //Sudoku Puzzle (Big Book project 73). Fill the 9x9 grid so that every row, column and 3x3 box
    //holds the digits 1 to 9. The game decides; the Console asks and tells, in the player's words.
    Sudoku()
      //A language with no words of its own is unset: ?: falls back to English.
      console <- Console(Say(language()) ?: Say("en"))

      console.showIntroduction()
      grid <- SudokuGrid()
      running <- true
      while running and not console.ended()
        console.showGrid(grid)
        if grid.isSolved()
          console.showSolved()
          running: false
        else
          running: takeTurn(grid, console)
      console.showGoodbye()