Skip to content

Instantly share code, notes, and snippets.

@potix2

potix2/gist:1257161

Created October 2, 2011 06:55
Show Gist options
  • Save potix2/1257161 to your computer and use it in GitHub Desktop.
Save potix2/1257161 to your computer and use it in GitHub Desktop.
Download ZIP
Sudoku Solver
Raw
gistfile1.html
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8" />
<title>Sudoku Solver</title>
<style type="text/css">
#content-table {
border: solid 1px #ccc;
border-collapse: collapse;
empty-cells: show;
}
#content-table tr {
}
#content-table tr td {
width: 60px;
height: 60px;
border: solid 1px #ccc;
text-align: center;
vertical-align: middle;
font-weight: bold;
color: #3c3;
}
#content-table tr td.b {
background-color: #f2f2f2;
}
#content-table tr td.origin {
color: #999;
}
.memo {
border: none;
border-collapse: separate;
empty-cells: show;
font-size: 7px;
margin: 0px;
padding: 0px;
}
.memo li {
display: block;
float: left;
color: #33f;
width: 20px;
height: 20px;
text-align: center;
line-height: 20px;
}
</style>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.6.3/jquery.min.js"></script>
<script type="text/javascript">
$(document).ready(function() {
var data = [];
function _solve() {
for ( var i = 0; i < 81; i++ ) {
if ( data[i] > 0 ) continue;
var used = new Array(0,0,0,0,0, 0,0,0,0,0);
for ( var j = 0; j < 81; j++ ) {
if ((Math.floor(j/9) == Math.floor(i/9)) || ((j%9) == (i%9)) ||
(
(Math.floor(j/27) == Math.floor(i/27)) &&
(Math.floor((j%9)/3) == Math.floor((i%9)/3))
)
) {
used[data[j]] = 1;
} else {
used[0] = 1;
}
}
for ( var j = 1; j <= 9; j++ ) {
if ( used[j] == 0 ) {
data[i] = j;
if ( _solve() ) {
return true;
}
data[i] = 0;
}
}
return false;
}
return true;
}
function setupProblem() {
$('#content-table tbody tr td').removeClass('origin');
for ( var i = 0; i < 9; i++ ) {
for ( var j = 0; j < 9; j++ ) {
var v = data[i * 9 + j];
var elem = '#content-table tbody tr:nth-child('
+ (i + 1) +') td:nth-child(' + (j + 1) + ')';
if ( v == 0 ) {
$(elem).text('');
}
else {
$(elem).text(v).addClass('origin');
}
}
}
}
function showResult() {
for ( var i = 0; i < 9; i++ ) {
for ( var j = 0; j < 9; j++ ) {
var v = data[i * 9 + j];
if ( v != 0 ) {
$('#content-table tbody tr:nth-child(' + (i + 1) +') td:nth-child(' + (j + 1) + ')').text(v);
}
}
}
}
function showMemo(memo) {
for ( var i = 0; i < 9; i++ ) {
for ( var j = 0; j < 9; j++ ) {
var m = memo[i * 9 + j];
if ( m != 0 ) {
var nums = [];
for ( var k = 0; k < 9; k++ ) {
if ( ((m >> k) & 1) == 1 ) {
nums[k] = k + 1;
}
else {
nums[k] = '';
}
}
var elem = '#content-table tbody tr:nth-child('
+ (i + 1) +') td:nth-child(' + (j + 1) + ')';
var s = '<ul class="memo">';
for ( k = 0; k < 9; k++ ) {
s += '<li>' + nums[k] + '</li>';
}
s += '</ul>';
$(elem).empty().append(s);
}
}
}
}
function convertProblemTextToArray(text) {
text = $.trim(text);
if ( !text.match(/^[0-9]{81}$/) ) {
return null;
}
else {
return text.split('');
}
}
function solve() {
if ( data == null || data.length != 81 ) {
alert('invalid problem');
return;
}
if ( _solve() ) {
showResult();
}
else {
alert('faield to solve');
}
}
function clear() {
$('#problem-text').val('');
$('#content-table tbody tr td').removeClass('origin');
for ( var i = 0; i < 81; i++ ) {
var elem = '#content-table tbody tr:nth-child('
+ (Math.floor(i/9) + 1) +') td:nth-child(' + ((i%9) + 1) + ')';
$(elem).text('');
}
}
$('#solve-button').click(solve);
$('#set-button').click(function() {
data = convertProblemTextToArray($('#problem-text').val());
if ( data == null ) {
alert('invalid problem');
return;
}
setupProblem();
});
$('#clear-button').click(clear);
//easy
// $('#problem-text').val('000081450209564387458003206920047630306852701081630024802400963563798102094320000');
//medium
// $('#problem-text').val('002306000089000003070018000700000340903425706046000009000890030400000890000103200');
//difficult
// $('#problem-text').val('405918007000000000078405100100000800000257000009000002004701390000000000600592401');
$('#problem-text').val('030000040010097050002508600003000800900004300007600004009805400070000020050071080');
$('#set-button').click();
});
</script>
</head>
<body>
<table id="content-table">
<tbody>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
<tr><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td></tr>
<tr><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td></tr>
<tr><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td></tr>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td class="b"></td><td class="b"></td><td class="b"></td><td></td><td></td><td></td></tr>
</tbody>
</table>
<input id="problem-text" type="text" name="problem" size="81" value="" /><input id="set-button" type="button" value="set" /><input id="solve-button" type="button" value="solve" /><input id="clear-button" type="button" value="clear" />
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment