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

[arzterk]

// 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";
}

[Duluku]

想起解数独问题之后优化是 dancing link … 上面的没看懂

[arzterk]

@Duluku 没用复杂的 dacing link，就是最简单的 backtracking