[WP]no.020 数独を解く

個人的にはナンバープレース(ナンプレ)という名称の方が馴染んでますね。はい。


数独を解きます。WeeklyPrograming仕様なので超簡単な問題しか解けませんし、高速なアルゴリズムとは言い難い内容。

そもそも数独、とても簡単なルールと正解パターンの少なさにより、ペイントロジック以上に直感で埋めないと解けない問題が
多いです。ううむ。

ためしに雑誌の問題を入力して解いてみたのですが、2か所ほど、自分で適当に推測して入力する場面がありました。
間違っていたらエラー吐くので、その場合は元に戻ってやりなおし。
「使えねーなこれ」というのが第一印象。使えないツールで良い気がする。


VBAで作ろうとしたのですが所詮マクロ程度の内容しか扱えなかったので、html+javascriptで。
htmlだし、どこかのサーバにうpする予定。

使い方
・数字を入力する
・runを複数回押す。
・機械的に解決できなくなるまで埋めようとします。

…使えば感じるのですが、Undoを実装するべきです…
今日はここまで。別の日に手を加えます…コメントも殆どないし。

<html>
<head>
<title>np</title>
<script type="text/javascript">
<!--

var flgcls=new Array(0,0,0,0,0,0,0,0,0);// 横方向
var flgrws=new Array(0,0,0,0,0,0,0,0,0);// 縦方向
var flgmx=new Array(0,0,0,0,0,0,0,0,0);// セル

var mxtable=new Array(0,1,2,9,10,11,18,19,20); // 3x3セル参照用テーブル

var loopmax = 200;

// 非常によろしくない変数名
var e;

window.onload=function(){
e=document.f_in.elements;
}

function reset(){
for (i in e){
e[i].value="";
}
}
function initialize(){

}
function solve(){
// 更新
if (!__flgflush()) return;
if (!__tableflush()) return;
}

// フラグを更新する
function __flgflush(){
var i,j,d,f,b;
// flgcls
for (i=0;i<9;i++){
f=0;
for (j=0;j<9;j++){
d=parseInt(e[i*9+j].value)-1;
if (d<0 || isNaN(d)) continue;
b=1<<d; // bit
if ((f&b)!=0){ // 重複した数字
alert("重複した数字が検出されましたc("+j+","+i+")["+(f&b)+"]");
return false;
}
f=f|b;
}
flgcls[i]=f;
}
// flgrws
for (i=0;i<9;i++){
f=0;
for (j=0;j<9;j++){
d=parseInt(e[i+j*9].value)-1;
if (d<0 || isNaN(d)) continue;
b=1<<d; // bit
if ((f&b)!=0){ // 重複した数字
alert("重複した数字が検出されましたr("+i+","+j+")["+(f&b)+"]");
return false;
}
f=f|b;
}
flgrws[i]=f;
}
// flgmx
for (i=0;i<9;i++){
f=0;
for (j=0;j<9;j++){
d=parseInt(e[mxtable[i]*3+mxtable[j]].value)-1;
if (d<0 || isNaN(d)) continue;
b=1<<d; // bit
if ((f&b)!=0){ // 重複した数字
alert("重複した数字が検出されましたm("+i+"/"+j+")["+(f&b)+"]");
return false;
}
f=f|b;
}
flgmx[i]=f;
}
return true;
}

// 埋められるところは埋める
function __tableflush(){
var x,y,d,b;
for (x=0;x<9;x++){
for (y=0;y<9;y++){
d=parseInt(e[x+y*9].value)-1;
if (!(d<0 || isNaN(d))) continue; // すでに埋まってるところはパス

console.log("["+x+","+y+"]");
b=flgcls[y]|flgrws[x]|flgmx[Math.floor(x/3)+Math.floor(y/3)*3];
b=(b&0x1FF)^0x1FF;
n=bitp(b);
if (n!=0) e[x+y*9].value=""+n;
console.log("["+b+"/"+n+"]");
}
}
return true;
}


function bitp(b){
var i;
if (b==0) return 0;
b=b&0x1FF|0x400; // 0でも止めるために0x200を立てる
for (i=1;(b&1)==0;b=b>>1)
i++;
b=((b>>1)<<(i+1))&0x3FF;
console.log("out:"+b+" i"+i);
if (b!=0) return 0;
return i;
}

// -->
</script>
</head>

<body>
<h3>数独とかそういうの</h3>
<div>input - result</div>
<form name="f_in">
<script type="text/javascript">
<!--
document.writeln("<table border=1>");
for (y=0;y<9;y++){
document.writeln("<tr>");
for (x=0;x<9;x++)
document.writeln('<td><input type="text" size="2" value=""></td>');
document.writeln("<tr>");
}
document.writeln("</table>");

// -->l
</script>
</form>
<div>
<input type="button" value="reset" onclick="reset();">
<input type="button" value="run" onclick="solve();">
</div>

</body>
</html>
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : Javascript アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1467位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>