本番中にパニクって解けなかったのを反省して解き直しました。DFSくらいさっと書けないとだめですね…。
問題
- C - 七目
- 9x9のマスが白で埋められている。白マスが縦・横・斜めのいずれにも白マスが7個以上連続しないように、11個のマスを黒く塗る塗り方を求める
解法
- 素直にDFS。黒く塗るしかないマスは黒く塗り、そうでない箇所では黒く塗る場合・塗らない場合の両方を試す。
- 各行に少なくとも一つは黒マスが必要なことを利用して枝刈りすると、自分の古いPCで1分20秒ほどですべての解が出ました。
コード
#include <algorithm> #include <cassert> #include <climits> #include <cmath> #include <cstdio> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(int i = 0; i < (int)(n); ++i) #define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(v) ((int)v.size()) #define pb push_back #define mp make_pair #define mt make_tuple const int N = 9; const int W = N; const int H = N; void debug_print(vector<vector<char>>& cells, int h_now, int w_now, bool print_cursor=true) { cout << "=================" << endl; REP(h, H) { REP(w, W) { if (h == h_now && w == w_now && print_cursor) { cout << "["; } else { cout << " "; } cout << (cells[h][w] == 1 ? '#' : '.'); if (h == h_now && w == w_now && print_cursor) { cout << "]"; } else { cout << " "; } } cout << endl; } cout << "=================" << endl; } pair<int,int> idx_to_h_w(int idx) { return {idx / N, idx % N}; } // 今いるマスの左・上・右上・左上を見て、このマスを黒く塗る必要があるかを判定 bool should_put_stone(int idx, vector<vector<char>>& cells) { auto hw = idx_to_h_w(idx); int h, w; tie(h, w) = hw; int dx[] = {-1, 0, -1, 1}; int dy[] = {0, -1, -1, -1}; REP(d, 4) { int seq = 0; FOR(i, 1, 7) { int h2 = h + dy[d] * i; int w2 = w + dx[d] * i; if (w2 < 0 || w2 >= W || h2 < 0 || h2 >= H) { break; } if (cells[h2][w2] == 0) ++seq; } if (seq == 6) return true; } return false; } bool dfs(int idx, vector<vector<char>>& cells, int remain) { auto hw = idx_to_h_w(idx); int h, w; tie(h, w) = hw; // 今いるマスをとりあえず白くする // これを忘れると正しくdfsできない！ cells[h][w] = 0; // cout << "remain = << " << remain << endl; // debug_print(cells, h, w); // 各行に少なくとも1つ黒マスが必要なことから // もう条件を満たせないならfalseを返す int minimum_need = H - h - 1; if (remain < minimum_need) return false; // 最後の判定 if (idx == H * W - 1) { if (should_put_stone(idx, cells)) { if (remain > 0) { cells[h][w] = 1; remain--; } else { return false; } } // 条件を満たすのでprint debug_print(cells, h, w, false); return true; } // 上・左・右上・左上いずれかに6連続で白マスなら現マスは黒く塗るしかない if (should_put_stone(idx, cells)) { // もう残数がなければおわり if (remain == 0) { return false; } else { cells[h][w] = 1; return dfs(idx + 1, cells, remain - 1); } } // 石を置いても置かなくてもよい else { // 石を置かない場合 auto ret = dfs(idx + 1, cells, remain); // 石を置く場合 if (remain > 0) { cells[h][w] = 1; ret |= dfs(idx + 1, cells, remain - 1); } return ret; } } int main(void) { vector<vector<char>> cells(N, vector<char>(N)); dfs(0, cells, 11); return 0; }
出力されたのは以下の16盤面です。
================= ......#.. ....#.... ..#...... #......#. .....#... ...#..... .#......# ......#.. ....#.... ================= ================= ......#.. ...#..... #......#. ....#.... .#......# .....#... ..#...... ......#.. ...#..... ================= ================= ......#.. ..#...... .....#... .#......# ....#.... #......#. ...#..... ......#.. ..#...... ================= ================= ......#.. ..#...... #......#. .....#... ....#.... ...#..... .#......# ......#.. ..#...... ================= ================= ......#.. ..#...... #......#. ...#..... ....#.... .....#... .#......# ......#.. ..#...... ================= ================= .....#... ...#..... .#......# ......#.. ....#.... ..#...... #......#. .....#... ...#..... ================= ================= .....#... ..#...... ......#.. ...#..... #......#. ....#.... .#......# .....#... ..#...... ================= ================= ....#.... ......#.. .#......# ...#..... .....#... #......#. ..#...... ....#.... ......#.. ================= ================= ....#.... ..#...... #......#. .....#... ...#..... .#......# ......#.. ....#.... ..#...... ================= ================= ...#..... ......#.. ..#...... .....#... .#......# ....#.... #......#. ...#..... ......#.. ================= ================= ...#..... .....#... #......#. ..#...... ....#.... ......#.. .#......# ...#..... .....#... ================= ================= ..#...... ......#.. ...#..... #......#. ....#.... .#......# .....#... ..#...... ......#.. ================= ================= ..#...... ......#.. .#......# .....#... ....#.... ...#..... #......#. ..#...... ......#.. ================= ================= ..#...... ......#.. .#......# ...#..... ....#.... .....#... #......#. ..#...... ......#.. ================= ================= ..#...... .....#... .#......# ....#.... #......#. ...#..... ......#.. ..#...... .....#... ================= ================= ..#...... ....#.... ......#.. .#......# ...#..... .....#... #......#. ..#...... ....#.... =================
