Miracle Sudoku Solver/Generator

MiracleSudokuSolver.kt

import kotlin.math.abs
import kotlin.system.measureTimeMillis

// This code solves a Sudoku puzzle with some additional constraints by Mitchell Lee
// https://www.theverge.com/tldr/2020/5/18/21262771/sudoku-puzzle-cracking-the-cryptic-watch-this-video-simon-anthony
//
// The constraints are as below:
// 1. Any two cells separated by a knight's move or a king's move (in chess) cannot contain the same digit.
// 2. Any two orthogonally adjacent cells cannot contain consecutive digits
// 3. Normal Sudoku rules apply

fun main() {
//  solve()
  gen()
}

fun gen() {
  val generator = SudokuGenerator()
  val time = measureTimeMillis {
    val boards = generator.gen()
    println("Num boards: ${boards.size}")

    // count identical ones
    val set = mutableSetOf<Board>()
    for (b in boards) {
      if (set.none { it.identicalTo(b) }) {
        set.add(b)
      }
    }
    println("Num identical boards: ${set.size}")
    for (b in set) {
      println(b)
    }
  }
  println("time: $time[msec]")
}

fun solve() {
  val solver = SudokuSolver()
  val expect = Board(arrayOf(
      intArrayOf(4, 8, 3, 7, 2, 6, 1, 5, 9),
      intArrayOf(7, 2, 6, 1, 5, 9, 4, 8, 3),
      intArrayOf(1, 5, 9, 4, 8, 3, 7, 2, 6),
      intArrayOf(8, 3, 7, 2, 6, 1, 5, 9, 4),
      intArrayOf(2, 6, 1, 5, 9, 4, 8, 3, 7),
      intArrayOf(5, 9, 4, 8, 3, 7, 2, 6, 1),
      intArrayOf(3, 7, 2, 6, 1, 5, 9, 4, 8),
      intArrayOf(6, 1, 5, 9, 4, 8, 3, 7, 2),
      intArrayOf(9, 4, 8, 3, 7, 2, 6, 1, 5)
  ))
  val time = measureTimeMillis {
    val actual = solver.solve(arrayOf(
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 1, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 2, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0)
    ))
    println(actual.size)
    println(actual.first() == expect)
  }

  println("time: $time[msec]")
}

class SudokuGenerator {
  fun gen(): List<Board> {
    val init = Array(9) { IntArray(9) }
    val boards = mutableListOf<Board>()
    val solver = SudokuSolver()
    for (i in 1..9) {
      init[0][0] = i
      boards.addAll(solver.solve(init))
    }
    return boards
  }
}

class SudokuSolver {
  fun solve(init: Array<IntArray>): Collection<Board> {
    val board = Board(init)
    val list = mutableListOf<Board>()
    solve(board, list)
    return list
  }

  private fun solve(board: Board, list: MutableCollection<Board>) {
    for (r in 0 until 9) {
      for (c in 0 until 9) {
        if (!board.placeable(r, c)) continue
        var solved = false
        for (n in 1..9) {
          if (board.set(r, c, n)) {
            solve(board, list)
            if (board.solved()) {
              list.add(board.clone())
              solved = true
            }
            board.unset(r, c, n)
          }
        }
        if (!solved) return
      }
    }
  }
}

class Board(init: Array<IntArray>) {
  val numbers = Array(9) { IntArray(9) }
  val rows = Array(9) { BooleanArray(10) }
  val columns = Array(9) { BooleanArray(10) }
  val boxes = Array(9) { BooleanArray(10) }

  init {
    for (i in 0 until 9) {
      for (j in 0 until 9) {
        val n = init[i][j]
        numbers[i][j] = n
        if (n > 0) {
          rows[i][n] = true
          columns[j][n] = true
          boxes[box(i, j)][n] = true
        }
      }
    }
  }

  fun placeable(row: Int, col: Int) = numbers[row][col] == 0

  fun set(row: Int, col: Int, n: Int): Boolean {
    val b = box(row, col)
    if (rows[row][n] || columns[col][n] || boxes[b][n] || !placeable(row, col)) return false
    for ((dr, dc) in arrayOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1))) {
      val nr = row + dr
      val nc = col + dc
      if (nr < 0 || nr >= 9 || nc < 0 || nc >= 9 || numbers[nr][nc] == 0) continue
      if (abs(n - numbers[nr][nc]) == 1) return false
    }
    for ((dr, dc) in arrayOf(
        Pair(-1, -1), Pair(-1, 1), Pair(1, -1), Pair(1, 1),
        Pair(-2, -1), Pair(-2, 1), Pair(2, -1), Pair(2, 1),
        Pair(-1, -2), Pair(1, -2), Pair(-1, 2), Pair(1, 2)
    )) {
      val nr = row + dr
      val nc = col + dc
      if (nr < 0 || nr >= 9 || nc < 0 || nc >= 9) continue
      if (numbers[nr][nc] == n) return false
    }
    numbers[row][col] = n
    rows[row][n] = true
    columns[col][n] = true
    boxes[b][n] = true
    return true
  }

  fun unset(row: Int, col: Int, n: Int) {
    numbers[row][col] = 0
    rows[row][n] = false
    columns[col][n] = false
    boxes[box(row, col)][n] = false
  }

  fun solved() = numbers.all { it.all { n -> n != 0 } }

  fun clone() = Board(numbers)

  private fun box(row: Int, col: Int) = row / 3 * 3 + col / 3


  override fun toString(): String {
    var s = ""
    for (i in 0 until 9) {
      for (j in 0 until 9) {
        s += numbers[i][j].toString() + " "
      }
      s += "\n"
    }
    return s
  }

  override fun equals(other: Any?): Boolean {
    if (this === other) return true
    if (javaClass != other?.javaClass) return false

    other as Board

    if (!numbers.contentDeepEquals(other.numbers)) return false

    return true
  }

  override fun hashCode(): Int {
    return numbers.contentDeepHashCode()
  }

  fun identicalTo(other: Board): Boolean {
    if (this == other) return true

    var equal = true
    for (i in 0 until 9) for (j in 0 until 9) equal = equal and (this.numbers[i][j] == other.numbers[j][8 - i])
    if (equal) return true
    equal = true
    for (i in 0 until 9) for (j in 0 until 9) equal = equal and (this.numbers[i][j] == other.numbers[8 - i][8 - j])
    if (equal) return true
    equal = true
    for (i in 0 until 9) for (j in 0 until 9) equal = equal and (this.numbers[i][j] == other.numbers[8 - j][i])
    return equal
  }
}