Created
April 19, 2013 09:43
-
-
Save shadabahmed/5419275 to your computer and use it in GitHub Desktop.
A CodePen by Shadab Ahmed. Soduko Solver - Simple sudoko solver where we have atleast one unambigous cell all the time when solving the puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<section> | |
<table class="grid"> | |
<tbody> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
<tr> <td> <td> <td> <td> <td> <td> <td> <td> <td> | |
</table> | |
</section> | |
<div id="run" style="position:absolute; left: 100px; top: 620px"> | |
<input type="button" value="Run"/> | |
</div> | |
<div class="selector" style="display:none"> | |
<table class="selector first"> | |
<tbody> | |
<tr> <td> <td> <td> | |
</table> | |
<table class="selector second"> | |
<tbody> | |
<tr> <td> <td> <td> | |
</table> | |
<table class="selector third"> | |
<tbody> | |
<tr> <td> <td> <td> | |
</table> | |
</div> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class SudokuGrid | |
@delay = 0 | |
@set : (input)-> | |
@delay = 0 | |
for row,x in input | |
for col, y in row | |
if col != 0 | |
$("table.grid tr:nth-child(#{x+1}) td:nth-child(#{y+1})").text(col) | |
else | |
$("table.grid tr:nth-child(#{x+1}) td:nth-child(#{y+1})").text('').css({'background-color': ''}) | |
@found : (x,y,num)-> | |
setTimeout -> | |
$("table.grid tr:nth-child(#{x+1}) td:nth-child(#{y+1})").text(num).css({'background-color': '#5F5'}) | |
, @delay + 200 | |
@delay += 200 | |
class SudokuSolver | |
max = 0 | |
unsolved = [] | |
ranges = {} | |
input = undefined | |
block_cell_idx = (x,y)-> | |
Math.floor(y/3)*3 + Math.floor(x/3) | |
get_missing_num = (nums_existing)-> | |
num_found = false | |
for i in [0..max] | |
missing = !(1 << i & nums_existing) | |
if missing | |
if num_found | |
return 0 | |
num_found = i + 1 | |
return num_found | |
pos_cord = (r)-> | |
[r >> 4, r & 0x0F] | |
update_ranges = (x,y,num)-> | |
num_bit = (1 << (num - 1)) & 0x1FF | |
ranges.vert[y] |= num_bit | |
ranges.hor[x] |= num_bit | |
ranges.block[block_cell_idx(x,y)] |= num_bit | |
get_next = -> | |
for pos,idx in unsolved | |
[x,y] = pos_cord(pos) | |
existing_nums = ranges.vert[y] | ranges.hor[x] | ranges.block[block_cell_idx(x,y)] | |
missing_num = get_missing_num(existing_nums) | |
if missing_num | |
unsolved.splice(idx,1) | |
update_ranges(x,y, missing_num) | |
return [missing_num, x, y] | |
return [0, -1, -1] | |
@solve = -> | |
while unsolved.length | |
[missing_num, x,y] = get_next(unsolved) | |
if !missing_num | |
console.log 'Not Solvable' | |
return | |
SudokuGrid.found(x,y,missing_num) | |
console.log "#{missing_num} at #{x},#{y}" | |
@init = (input_grid)-> | |
input = input_grid | |
max = input.length - 1 | |
ranges.vert = (0 for i in [0..max] by 1) | |
ranges.hor = (0 for i in [0..max] by 1) | |
ranges.block= (0 for i in [0..max] by 1) | |
for row,x in input | |
for num,y in row | |
update_ranges(x,y,num) | |
if num == 0 | |
unsolved.push ((x << 4) | y) | |
input = [[0,0,0,4,5,0,7,0,0], | |
[7,0,9,0,0,0,4,0,6], | |
[4,5,0,7,0,9,0,2,3], | |
[0,1,2,0,0,0,0,0,0], | |
[6,7,0,9,0,2,0,0,5], | |
[0,0,0,6,0,8,9,1,0], | |
[0,3,0,0,6,7,8,9,0], | |
[0,0,0,2,0,4,0,6,0], | |
[0,6,0,0,9,0,0,0,4]] | |
$ -> | |
SudokuGrid.set input | |
$('#run').click -> | |
SudokuGrid.set input | |
SudokuSolver.init input | |
SudokuSolver.solve() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@import "compass"; | |
body{ | |
background-color: lightblue; | |
font-family: 'Monaco'; | |
} | |
table.grid { | |
background-color: lightpink; | |
border-collapse: collapse; | |
border: solid 10px #999; | |
color: #444; | |
left: 100px; | |
top: 100px; | |
position: absolute; | |
tr:nth-child(3) { border-bottom: solid medium #999; } | |
tr:nth-child(6) { border-bottom: solid medium #999; } | |
td:nth-child(3) { border-right: solid medium #999; } | |
td:nth-child(6) { border-right: solid medium #999; } | |
td { border: solid thin #999; height: 3.4em; width: 3.4em; | |
text-align: center; padding: 0; } | |
} | |
div.selector{ | |
position: absolute; | |
position: absolute; | |
z-index: 9999; | |
left: 299px; | |
top: 200px; | |
} | |
table.selector { | |
//background-color: aqua; | |
border-collapse: collapse; | |
border: solid 1px; | |
&.first{ | |
-webkit-transform: rotate(-60deg); | |
-webkit-transform-origin: -20% 60%; | |
} | |
&.second{ | |
-webkit-transform: rotate(60deg); | |
-webkit-transform-origin: 120% 60%; | |
} | |
&.third{ | |
} | |
td { border: solid thin; height: 1.4em; width: 1.4em; | |
text-align: center; padding: 0; } | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment