Created
January 14, 2020 07:22
-
-
Save alwarren/93a9b44b50f2b11c1c7d8c3b26ec14a1 to your computer and use it in GitHub Desktop.
Kotin implementation of a java Sudoku generator.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(" ")) | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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