Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
1-liner CoffeeScript Sudoku Solver
solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0
# This can be compressed into a 1-liner (see above)
solve = (s, c = 0) -> # 's' is 2d sudoku array and 'c' is the cell [0,81) to start solving at
return if c is 81 then s else solve s, c+1 unless s[x = c/9|0][y = c%9] is 0 # base case - either all 81 cells filled or at a filled cell
box = (i) -> sudoku[x - x%3 + (i - i%3)/3][y - y%3 + i%3] # ith cell in sub 3x3 box containing x,y
good = (g) -> [0...9].every (i) -> g not in [s[x][i], s[i][y], box i] # returns true iff s[x][y] (originally 0) when set to g breaks sudoku rules due to collision
guesses = [1..9].filter good # select non-conflicting guesses for position x,y
produces_solution = (g) -> s[x][y] = g; solve s, c+1 # true iff a guess actually produces a solution at x,y
(guesses.some produces_solution) or s[x][y] = 0 # either some guess produces a solution or reset
sudoku = [[1,0,0,0,0,7,0,9,0], # Test - 0 denotes blank cells
[0,3,0,0,2,0,0,0,8],
[0,0,9,6,0,0,5,0,0],
[0,0,5,3,0,0,9,0,0],
[0,1,0,0,8,0,0,0,2],
[6,0,0,0,0,4,0,0,0],
[3,0,0,0,0,0,0,1,0],
[0,4,0,0,0,0,0,0,7],
[0,0,7,0,0,0,3,0,0]]
console.log if solve sudoku then sudoku else 'No solution'
@pathikrit

This comment has been minimized.

Copy link
Owner Author

pathikrit commented Apr 5, 2013

for a cleaner longer solution see this - https://github.com/pathikrit/coffee-pearls/blob/master/sudoku.coffee

also this is a true one liner (no cheating by semicolons)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.