Skip to content

Instantly share code, notes, and snippets.

@alwarren
Created January 14, 2020 07:22
Show Gist options
  • Save alwarren/93a9b44b50f2b11c1c7d8c3b26ec14a1 to your computer and use it in GitHub Desktop.
Save alwarren/93a9b44b50f2b11c1c7d8c3b26ec14a1 to your computer and use it in GitHub Desktop.
Kotin implementation of a java Sudoku generator.
import kotlin.math.sqrt
// See https://www.geeksforgeeks.org/program-sudoku-generator/
class Sudoku(private val N: Int, private val K: Int) {
// Convenience value for public operations on the matrix
val width get() = N
val matrix = Array(N) { IntArray(N) }
// square root of N
private val sqrt = sqrt(N.toDouble()).toInt()
init {
fillValues()
}
// Returns false if given 3 x 3 block contains num.
private fun unUsedInBox(rowStart: Int, colStart: Int, num: Int): Boolean {
for (i in 0 until sqrt) for (j in 0 until sqrt)
if (matrix[rowStart + i][colStart + j] == num)
return false
return true
}
// Random generator
private fun randomGenerator(num: Int) = (1..num).shuffled().first()
// Fill a 3 x 3 matrix.
private fun fillBox(row: Int, col: Int) {
var num: Int
for (i in 0 until sqrt) {
for (j in 0 until sqrt) {
do {
num = randomGenerator(N)
} while (!unUsedInBox(row, col, num))
matrix[row + i][col + j] = num
}
}
}
// Fill the diagonal sqrt(N) number of sqrt(N) x sqrt(N) matrices
private fun fillDiagonal() {
var i = 0
while (i < N) {
// for diagonal box, start coordinates->i==j
fillBox(i, i)
i += sqrt
}
}
// check in the row for existence
private fun unUsedInRow(i: Int, num: Int): Boolean {
for (j in 0 until N)
if (matrix[i][j] == num) return false
return true
}
// check in the row for existence
private fun unUsedInCol(j: Int, num: Int): Boolean {
for (i in 0 until N) if (matrix[i][j] == num)
return false
return true
}
// Check if safe to put in cell
private fun checkIfSafe(i: Int, j: Int, num: Int): Boolean {
return unUsedInRow(i, num) &&
unUsedInCol(j, num) &&
unUsedInBox(i - i % sqrt, j - j % sqrt, num)
}
// A recursive function to fill remaining matrix
private fun fillRemaining(x: Int, y: Int): Boolean {
var i = x
var j = y
if (j >= N && i < N - 1) {
i += 1
j = 0
}
if (i >= N && j >= N)
return true
if (i < sqrt) {
if (j < sqrt) j = sqrt
} else if (i < N - sqrt) {
if (j == (i / sqrt) * sqrt) j += sqrt
} else {
if (j == N - sqrt) {
i += 1
j = 0
if (i >= N)
return true
}
}
for (num in 1..N) {
if (checkIfSafe(i, j, num)) {
matrix[i][j] = num
if (fillRemaining(i, j + 1))
return true
matrix[i][j] = 0
}
}
return false
}
// Remove the K no. of digits to complete game
private fun removeKDigits() {
var count = K
while (count != 0) {
val cellId = randomGenerator(N * N) - 1
// extract coordinates i and j
val i = cellId / N
val j = cellId % 9
if (matrix[i][j] != 0) {
count--
matrix[i][j] = 0
}
}
}
// Sudoku Generator
private fun fillValues() {
// Fill the diagonal of sqrt(N) x sqrt(N) matrices
fillDiagonal()
// Fill remaining blocks
fillRemaining(0, sqrt)
// Remove Randomly K digits to make game
removeKDigits()
}
// Print sudoku
fun print() {
for (i in 0 until width)
println( matrix[i].joinToString(" "))
}
}
1 8 0 3 2 0 7 0 4
6 0 9 4 1 8 2 5 3
3 2 4 0 5 9 8 6 1
2 3 8 1 6 5 9 4 7
0 9 1 0 7 4 0 0 6
4 6 7 8 0 3 0 0 5
7 4 0 6 8 1 5 0 0
0 1 0 5 4 2 6 7 0
8 5 6 9 0 7 4 1 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment