Sudoku: Difference between revisions
Content deleted Content added
→{{header|Groovy}}: improved speed |
m →{{header|Groovy}}: cosmetic changes |
||
Line 2,460: | Line 2,460: | ||
} |
} |
||
def gridRow = { grid, |
def gridRow = { grid, slot -> grid[slot.i] as Set } |
||
def gridCol = { grid, |
def gridCol = { grid, slot -> grid.collect { it[slot.j] } as Set } |
||
def gridBox = { grid, |
def gridBox = { grid, slot -> |
||
def |
def t, l; (t, l) = [slot.i.intdiv(3)*3, slot.j.intdiv(3)*3] |
||
(0..2).collect { row -> (0..2).collect { col -> grid[ |
(0..2).collect { row -> (0..2).collect { col -> grid[t+row][l+col] } }.flatten() as Set |
||
} |
} |
||
def assignCandidates = { grid, |
def assignCandidates = { grid, slots -> |
||
slots.each { slot -> |
|||
def unavailable = |
def unavailable = [gridRow, gridCol, gridBox].collect { it(grid, slot) }.sum() as Set |
||
slot.candidates = CELL_VALUES - unavailable |
|||
} |
} |
||
slots.sort { - it.candidates.size() } |
|||
if ( |
if (slots && ! slots[-1].candidates) { |
||
throw new GridException('Invalid Sudoku Grid') |
throw new GridException('Invalid Sudoku Grid') |
||
} |
} |
||
slots |
|||
} |
} |
||
def |
def slotList = { grid -> |
||
def |
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, |
assignCandidates(grid, slots) |
||
} |
} |
||
Line 2,491: | Line 2,491: | ||
def solve |
def solve |
||
solve = { grid -> |
solve = { grid -> |
||
def |
def slots = slotList(grid) |
||
if (! |
if (! slots) { return grid } |
||
while ( |
while (slots[-1].candidates.size() == 1) { |
||
def |
def slot = slots.pop() |
||
grid[ |
grid[slot.i][slot.j] = slot.candidates[0] |
||
if (! |
if (! slots) { return grid } |
||
assignCandidates(grid, |
assignCandidates(grid, slots) |
||
} |
} |
||
if (! |
if (! slots) { return grid } |
||
def |
def slot = slots.pop() |
||
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[ |
sGrid[slot.i][slot.j] = it |
||
grid = solve(sGrid) |
grid = solve(sGrid) |
||
} catch (GridException ge) { |
} catch (GridException ge) { |
||
grid[ |
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. |
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: |
ELAPSED: 35.739 seconds</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |