Sudoku: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|Groovy}}: improved speed
m →‎{{header|Groovy}}: cosmetic changes
Line 2,460: Line 2,460:
}
}


def gridRow = { grid, i, j -> grid[i] as Set }
def gridRow = { grid, slot -> grid[slot.i] as Set }


def gridCol = { grid, i, j -> grid.collect { it[j] } as Set }
def gridCol = { grid, slot -> grid.collect { it[slot.j] } as Set }


def gridBox = { grid, i, j ->
def gridBox = { grid, slot ->
def tl = [i.intdiv(3)*3, j.intdiv(3)*3]
def t, l; (t, l) = [slot.i.intdiv(3)*3, slot.j.intdiv(3)*3]
(0..2).collect { row -> (0..2).collect { col -> grid[tl[0]+row][tl[1]+col] } }.flatten() as Set
(0..2).collect { row -> (0..2).collect { col -> grid[t+row][l+col] } }.flatten() as Set
}
}


def assignCandidates = { grid, empties ->
def assignCandidates = { grid, slots ->
empties.each { empty ->
slots.each { slot ->
def unavailable = (gridRow(grid, empty.i, empty.j) + gridCol(grid, empty.i, empty.j) + gridBox(grid, empty.i, empty.j)) as Set
def unavailable = [gridRow, gridCol, gridBox].collect { it(grid, slot) }.sum() as Set
empty.candidates = CELL_VALUES - unavailable
slot.candidates = CELL_VALUES - unavailable
}
}
empties.sort { - it.candidates.size() }
slots.sort { - it.candidates.size() }
if (empties && ! empties[-1].candidates) {
if (slots && ! slots[-1].candidates) {
throw new GridException('Invalid Sudoku Grid')
throw new GridException('Invalid Sudoku Grid')
}
}
empties
slots
}
}


def emptyList = { grid ->
def slotList = { grid ->
def empties = (0..8).collect { i -> (0..8).findAll { j -> ! (grid[i][j] in CELL_VALUES) } \
def slots = (0..8).collect { i -> (0..8).findAll { j -> ! (grid[i][j] in CELL_VALUES) } \
.collect {j -> [i: i, j: j] } }.flatten()
.collect {j -> [i: i, j: j] } }.flatten()
assignCandidates(grid, empties)
assignCandidates(grid, slots)
}
}


Line 2,491: Line 2,491:
def solve
def solve
solve = { grid ->
solve = { grid ->
def empties = emptyList(grid)
def slots = slotList(grid)
if (! empties) { return grid }
if (! slots) { return grid }
while (empties[-1].candidates.size() == 1) {
while (slots[-1].candidates.size() == 1) {
def empty = empties.pop()
def slot = slots.pop()
grid[empty.i][empty.j] = empty.candidates[0]
grid[slot.i][slot.j] = slot.candidates[0]
if (! empties) { return grid }
if (! slots) { return grid }
assignCandidates(grid, empties)
assignCandidates(grid, slots)
}
}
if (! empties) { return grid }
if (! slots) { return grid }
def empty = empties.pop()
def slot = slots.pop()
empty.candidates.each {
slot.candidates.each {
if (! isSolved(grid)) {
if (! isSolved(grid)) {
try {
try {
def sGrid = grid.collect { row -> row.collect { cell -> cell } }
def sGrid = grid.collect { row -> row.collect { cell -> cell } }
sGrid[empty.i][empty.j] = it
sGrid[slot.i][slot.j] = it
grid = solve(sGrid)
grid = solve(sGrid)
} catch (GridException ge) {
} catch (GridException ge) {
grid[empty.i][empty.j] = '.'
grid[slot.i][slot.j] = '.'
}
}
}
}
Line 2,558: Line 2,558:
[2, 1, 4, 8, 3, 7, 5, 9, 6]
[2, 1, 4, 8, 3, 7, 5, 9, 6]


ELAPSED: 0.506 seconds
ELAPSED: 0.572 seconds


PUZZLE
PUZZLE
Line 2,582: Line 2,582:
[4, 7, 3, 2, 5, 8, 1, 9, 6]
[4, 7, 3, 2, 5, 8, 1, 9, 6]


ELAPSED: 33.43 seconds</pre>
ELAPSED: 35.739 seconds</pre>


=={{header|Haskell}}==
=={{header|Haskell}}==
Retrieved from "https://rosettacode.org/wiki/Sudoku"