Skip to content

Instantly share code, notes, and snippets.

@shadabahmed
Created April 19, 2013 09:43
Show Gist options
  • Save shadabahmed/5419275 to your computer and use it in GitHub Desktop.
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
<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>
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()
@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