Skip to content

Instantly share code, notes, and snippets.

@pathikrit
Created October 10, 2012 07:04
Show Gist options
  • Save pathikrit/3863614 to your computer and use it in GitHub Desktop.
Save pathikrit/3863614 to your computer and use it in GitHub Desktop.
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
Copy link
Author

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