124 lines
3.1 KiB
Swift
124 lines
3.1 KiB
Swift
import Foundation
|
|
|
|
typealias SodukuPuzzle = [[Int]]
|
|
|
|
class Soduku {
|
|
let mBoardSize:Int!
|
|
let mBoxSize:Int!
|
|
var mBoard:SodukuPuzzle!
|
|
var mRowSubset:[[Bool]]!
|
|
var mColSubset:[[Bool]]!
|
|
var mBoxSubset:[[Bool]]!
|
|
|
|
init(board:SodukuPuzzle) {
|
|
mBoard = board
|
|
mBoardSize = board.count
|
|
mBoxSize = Int(sqrt(Double(mBoardSize)))
|
|
mRowSubset = [[Bool]](count: mBoardSize, repeatedValue: [Bool](count: mBoardSize, repeatedValue: false))
|
|
mColSubset = [[Bool]](count: mBoardSize, repeatedValue: [Bool](count: mBoardSize, repeatedValue: false))
|
|
mBoxSubset = [[Bool]](count: mBoardSize, repeatedValue: [Bool](count: mBoardSize, repeatedValue: false))
|
|
initSubsets()
|
|
}
|
|
|
|
func computeBoxNo(i:Int, _ j:Int) -> Int {
|
|
let boxRow = i / mBoxSize
|
|
let boxCol = j / mBoxSize
|
|
|
|
return boxRow * mBoxSize + boxCol
|
|
}
|
|
|
|
func initSubsets() {
|
|
for i in 0..<mBoard.count {
|
|
for j in 0..<mBoard.count {
|
|
let value = mBoard[i][j]
|
|
|
|
if value != 0 {
|
|
setSubsetValue(i, j, value, true);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func isValid(i:Int, _ j:Int, var _ val:Int) -> Bool {
|
|
val--
|
|
let isPresent = mRowSubset[i][val] || mColSubset[j][val] || mBoxSubset[computeBoxNo(i, j)][val]
|
|
return !isPresent
|
|
}
|
|
|
|
func printBoard() {
|
|
for i in 0..<mBoardSize {
|
|
if i % mBoxSize == 0 {
|
|
println(" -----------------------")
|
|
}
|
|
|
|
for j in 0..<mBoardSize {
|
|
if j % mBoxSize == 0 {
|
|
print("| ")
|
|
}
|
|
|
|
print(mBoard[i][j] != 0 ? String(mBoard[i][j]) : " ")
|
|
print(" ")
|
|
}
|
|
|
|
println("|")
|
|
}
|
|
|
|
println(" -----------------------")
|
|
}
|
|
|
|
func setSubsetValue(i:Int, _ j:Int, _ value:Int, _ present:Bool) {
|
|
mRowSubset[i][value - 1] = present
|
|
mColSubset[j][value - 1] = present
|
|
mBoxSubset[computeBoxNo(i, j)][value - 1] = present
|
|
}
|
|
|
|
func solve() {
|
|
solve(0, 0)
|
|
}
|
|
|
|
func solve(var i:Int, var _ j:Int) -> Bool {
|
|
if i == mBoardSize {
|
|
i = 0
|
|
j++
|
|
if j == mBoardSize {
|
|
return true
|
|
}
|
|
}
|
|
|
|
if mBoard[i][j] != 0 {
|
|
return solve(i + 1, j)
|
|
}
|
|
|
|
for value in 1...mBoardSize {
|
|
if isValid(i, j, value) {
|
|
mBoard[i][j] = value
|
|
setSubsetValue(i, j, value, true)
|
|
|
|
if solve(i + 1, j) {
|
|
return true
|
|
}
|
|
|
|
setSubsetValue(i, j, value, false)
|
|
}
|
|
}
|
|
|
|
mBoard[i][j] = 0
|
|
return false
|
|
}
|
|
}
|
|
|
|
let board = [
|
|
[4, 0, 0, 0, 0, 0, 0, 6, 0],
|
|
[5, 0, 0, 0, 8, 0, 9, 0, 0],
|
|
[3, 0, 0, 0, 0, 1, 0, 0, 0],
|
|
[0, 2, 0, 7, 0, 0, 0, 0, 1],
|
|
[0, 9, 0, 0, 0, 0, 0, 4, 0],
|
|
[8, 0, 0, 0, 0, 3, 0, 5, 0],
|
|
[0, 0, 0, 2, 0, 0, 0, 0, 7],
|
|
[0, 0, 6, 0, 5, 0, 0, 0, 8],
|
|
[0, 1, 0, 0, 0, 0, 0, 0, 6]
|
|
]
|
|
|
|
let puzzle = Soduku(board: board)
|
|
puzzle.solve()
|
|
puzzle.printBoard()
|