V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
arzterk
V2EX  ›  算法

上班划水,写了个解数独的程序

  •  
  •   arzterk · 2018-12-19 17:09:30 +08:00 · 2639 次点击
    这是一个创建于 1926 天前的主题,其中的信息可能已经有所发展或是发生改变。
    // This file is a "Hello, world!" in C++ language by GCC for wandbox.
    #include <iostream>
    #include <cstdlib>
    #include <functional>
    #include <bitset>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    typedef struct tag_timer_guard{
    clock_t _begin;
    tag_timer_guard():_begin(clock()){

    }
    ~tag_timer_guard(){
    cout << (clock() - _begin) << "ms\n";
    }
    }_timer_guard;

    // that it takes to call that function. Notice the R is return type of Function
    template <typename F, typename... Args>
    typename result_of<F(Args...)>::type
    time_call(F f, Args&&... args)
    {
    _timer_guard _timer;
    return invoke(f, std::forward<Args>(args)...); // in c++17 use std::invoke directly.
    }


    template <int N>
    class Sodu
    {
    public:
    typedef short(Board)[N][N]; // based @0,1,2,...N-1
    const static int Q = (int)sqrtf(N);
    Sodu(short *c = 0)
    {
    memset(_board, 0, sizeof(_board));
    if (c)
    {
    memcpy(&_board, c, sizeof(_board));
    }

    for (int i = 0; i < N; ++i) // set empty pos to -1
    {
    for (int j = 0; j < N; ++j)
    {
    if (--_board[i][j] > -1)
    {
    hoz[i].set(_board[i][j]);
    ver[j].set(_board[i][j]);
    // blk-idx [i/Q, j/Q] row_num/col_num : Q
    blk[int(i / Q) * Q + int(j / Q)].set(_board[i][j]);
    }
    }
    }
    }

    void solve()
    {
    _solve(0);
    }

    void print()
    {
    for (int i = 0; i < N; ++i)
    {
    for (int j = 0; j < N; ++j)
    {
    cout << _board[i][j] + 1 << " ";
    if ((j+1) % Q == 0)cout << '|';
    }
    if ((i+1) % Q == 0)cout << endl;
    cout << endl;
    }
    cout << endl;
    }

    protected:
    void _solve(int t)
    {
    if (t == N * N )
    {
    print();
    return;
    }
    int i = t / N, j = t % N;

    if (_board[i][j] > -1)
    {
    return _solve(t + 1);
    }
    for (size_t v = 0; v < N; ++v)
    {
    int k = int(i / Q) * Q + int(j / Q);
    if (!hoz[i][v] && !ver[j][v] && !blk[k][v])
    {
    _board[i][j] = v;
    hoz[i].set(v);
    ver[j].set(v);
    blk[k].set(v);
    _solve(t + 1);
    _board[i][j] = -1;
    hoz[i].reset(v);
    ver[j].reset(v);
    blk[k].reset(v);
    }
    }
    }

    private:
    typedef std::bitset<N> Flags;
    Board _board;
    Flags hoz[N], ver[N], blk[N];
    };


    #define _X9 // 9X9 mode. default is 4X4 test mode
    #define Level 2// 1: simple;2:hard;3:very hard

    int main()
    {
    clock_t beg = clock();
    #ifdef _X9
    short x[] =
    {
    #if (Level == 1) // simple
    0,0,0,0,4,0,0,0,0,
    0,0,3,2,6,5,7,0,0,
    0,5,6,7,0,3,1,9,0,
    0,2,7,0,0,0,4,1,0,
    3,9,0,0,0,0,0,2,8,
    0,6,8,0,0,0,3,7,0,
    0,3,9,4,0,2,8,6,0,
    0,0,1,8,5,9,2,0,0,
    0,0,0,0,3,0,0,0,0,
    #endif
    #if (Level == 2) // hard
    0,0,0,0,2,0,3,0,6,
    0,0,2,1,0,0,0,0,0,
    6,8,0,5,0,0,0,0,1,
    0,0,4,0,6,0,0,8,3,
    9,0,0,0,0,0,0,0,7,
    8,7,0,0,9,0,4,0,0,
    7,0,0,0,0,3,0,6,4,
    0,0,0,0,0,8,1,0,0,
    4,0,1,0,0,7,0,0,0,
    #endif
    #if (Level == 3) // very hard
    3,0,0,0,0,0,0,0,9,
    0,7,0,0,4,0,0,3,0,
    0,0,6,1,0,3,5,0,0,
    0,0,7,0,3,0,8,0,0,
    0,8,0,2,0,4,0,1,0,
    0,0,5,0,7,0,6,0,0,
    0,0,2,3,0,7,4,0,0,
    0,1,0,0,6,0,0,2,0,
    8,0,0,0,0,0,0,0,7,
    #endif
    };

    Sodu<9> x9(x);
    x9.print();
    x9.solve();
    #else // test 4X4 mode
    short a[]=
    {
    1,0,0,3,
    0,0,0,1,
    0,0,0,2,
    2,0,0,4,

    /*1,2,4,3,
    4,3,2,1,
    3,4,1,2,
    2,1,3,4,*/
    };
    Sodu<4> x4(a);
    x4.print();
    x4.solve();
    #endif
    clock_t end = clock();
    cout << "\nCOST:"<< (end - beg) << "MS";
    }
    2 条回复    2018-12-20 08:47:08 +08:00
    Duluku
        1
    Duluku  
       2018-12-19 17:31:45 +08:00 via iPhone
    想起解数独问题之后优化是 dancing link … 上面的没看懂
    arzterk
        2
    arzterk  
    OP
       2018-12-20 08:47:08 +08:00
    @Duluku 没用复杂的 dacing link,就是最简单的 backtracking
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1069 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 19:03 · PVG 03:03 · LAX 12:03 · JFK 15:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.