世界一数独

世界一難しい数独の問題を解く

「世界一難しい数独」の問題です。
過去の「世界一難しい数独」

..53.....
8......2.
.7..1.5..
4....53..
.1..7...6
..32...8.
.6.5....9
..4....3.
.....97..

今回作成された「世界一難しい数独」

8........
..36.....
.7..9.2..
.5...7...
....457..
...1...3.
..1....68
..85...1.
.9....4..

Down Load から提供している Numberplace のプログラムには実装しているのですが、数字のチェーンをたどりヒントを消し込む Search メニューを使います。
上級レベルから難問レベルでは威力を発揮したのですが、「世界一難しい数独」には刃が立ちません。

そこで Version 3.3 から TestMode に DelHint メニューを追加します。
メニューを実行するとヒントに表示された数字から[破綻するヒント]を削除してくれます。
このメニューは「思ったより強力」で Search メニューをしのぐ威力を発揮します。
難問レベルの問題は DelHint メニュー一発で解けるようです。

    // 矛盾が生じるヒントを削除
    private void DelHint(object sender, EventArgs e)
    {   DelHint(m_t);
        Reset();
        Invalidate();
    }

    public void DelHint(int[,,] t)
    {   int rc,y,x,k,i,j,m;
    
        for(i=0; i<9; i++)
            for(j=0; j<9; j++)
            {   if (t[i, j, 0]!=0)  continue;
                for(m=1; m<10; m++)
                {   if (t[i, j, m] == m)
                    {   for (y=0; y<9; y++)
                            for (x=0; x<9; x++)
                                for (k=0; k<11; k++)
                                    m_w[y,x,k] = t[y,x,k]%10;
                        m_w[i, j, 0] = m;
                        CreateHint(m_w);
                        Think(m_w, false);
                        rc = FIN(m_w);
                        if (rc == -2) t[i, j, m] = 0;
                    }
                }
            }
    }

Search と DelHint の強力なメニューが揃ったので「世界一難しい数独」に挑戦します。
Search を実行しても数字のチェーンが見つからず、ほとんどヒントの消し込みは出来ませんでした。
DelHint メニューを実行すると上級レベルの問題では確定出来るマスが数個は見つかるのですが、「世界一難しい数独」と言われるだけあって目立った進展はありませんでした。
そこでヒントを整理した後で「二択のヒント」に注目します。
二択の場合は、どちらかが正解で５０％の確率だからです。
二択を一個選んで調べてもどうにもなりませんが、二択を二個組み合わせると破綻する場合があります。
より難問では二択を三個組み合わせて調べる必要があるようです。
２＊２＊２＝８で１／８の確率で正解があるはずです。
二択を三個組み合わせて破綻するケースと破綻しないケースを順に調べます。
初期の局面から三個のセルを仮定すると、局面が進み Search や DelHint も効果を発揮するようになりました。
８通りを順に Think と Search と DelHint の関数を組み合わせて順に調べて行くと正解にたどり着きました。

DelHint と言う強力な関数が出来たので、これを Super メニューに組み込みます。
今まで解けなかった難問も Super メニューで解くことが出来るようになりました。
Super メニューは再帰関数を使っているのですが「過去の世界一難しい数独」を含め瞬間に解くことが出来ました。
さすがに「今回作成された世界一難しい数独」は瞬間には解けず、約５０秒の時間を要しました。

    private void Super(object sender, EventArgs e)
    {
        m_err = false;
        Super(0,m_t);
        if (FIN(m_t)!=-1)
        {   MessageBox.Show("解答が見つかりません。(失敗しました)");
            Reset(false, m_test);
        }
        else    Reset(true, m_test);
    }

    //☆ 再帰で難問を解くスーパー関数
    public bool Super(int no, int[,,] t)
    {   int[,,] wt = new int[9,9,11];
        int     x, y, k, i, cn, pt1=0, pt2=0;
        int     rc;

        if (m_err)  return false;
        if (no > 8)
        {
            MessageBox.Show("再帰呼び出しが制限を超えました。");
            m_err = true;
            return false;
        }
        CreateHint(wt, t);
        DelHint(wt);

        while(true)                     //数字に色を設定して確定する
        {
            if (Analyze(wt,false))  Analyze(wt,false);
            rc = HintCor(wt);
            if (rc<0)
            {
                for (y = 0; y < 9; y++)
                    for (x = 0; x < 9; x++)
                        for (k = 0; k < 10; k++)    m_t[y,x,k] = wt[y,x,k];
                if (rc==-2) return false;   //破綻
                if (rc==-1) return true;    //完成
            }
            if (rc==0)  break;          //確定出来なくなった
            // 色が設定されているマスを確定する   
            for (y = 0; y < 9; y++)
                for (x = 0; x < 9; x++)
                {   for (k = 1; k < 10; k++)
                        if (wt[y, x, k] > 40)
                        {   wt[y, x, 0] = k;
                            for(i=0; i<9; i++)  wt[y, i, k] = 0;
                            for(i=0; i<9; i++)  wt[i, x, k] = 0;
                            Del33(y, x, k, wt);
                        }
                }
        }

        if (m_err)  return false;
        // 数字を仮定して再帰呼び出し
        for(y=0; y<9; y++)
            for(x=0; x<9; x++)
            {   if (wt[y,x,0]!=0)   continue;
                cn = 0;
                for (k = 0; k < 9; k++)
                {
                    if (wt[y, x, k] != 0)
                    {
                        cn++;
                        if (pt1 == 0) pt1 = k;
                        else          pt2 = k;
                    }
                }
                if (cn == 2 || cn == 3)
                {
                    wt[y, x, 0] = pt1;
                    if (Super(no + 1, wt))  return true;
                    wt[y, x, 0] = pt2;
                    if (Super(no + 1, wt))  return true;
                    wt[y, x, 0] = 0;
                }
            }
        return false;
    }

「世界一難しい数独」を作成していただいた作者に敬意を表して、プログラムの提供は控えることにします。
あなたも挑戦してみませんか？とは言え私もプログラムを使わずに解けるレベルは中級以下です。 (^_^;)
Version-3 の実行形式のプログラム(Number.exe)を私のページのダウンロードから提供しています。
(Version-3 の Super メニューでは「世界一難しい数独」の問題は解けません)

[Previous Chapter ↑] Numberplace

超初心者のプログラム入門(C# Frame Work)