I have written a program that tries to find a solution. Currently the best result I achieved with it is 96:
....#...#.
.##...#.#.
...###....
.#....####
..###.#...
#...#...#.
###..#.##.
...#..#...
.#..#.#.##
..#...#...
C++ code:
//#define _GLIBCXX_DEBUG
#include <x86intrin.h>
#include <cstring>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <atomic>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>
std::array<std::array<short, 10>, 10> getDists(const std::array<short, 10>& maze, int sx, int sy)
{
static const int ddx[4] { 0, 0, 1, -1 };
static const int ddy[4] { 1, -1, 0, 0 };
std::array<std::array<short, 10>, 10> dists{};
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) dists[i][j] = SHRT_MAX >> 3;
dists[sy][sx] = 0;
std::array<std::pair<char, char>, 105> dq; dq[0] = {sx, sy};
//std::deque<std::pair<int,int>> dq; dq.push_back({sx, sy});
int qi1 = 0, qi2 = 1; //qi2 = index to insert, qi1 = index to read
while(qi1 != qi2)
{
auto[cx, cy] = dq[qi1++];
short cd = dists[cy][cx];
short nd = cd + 1;
for(int di = 0; di < 4; di++)
{
int dx = ddx[di], dy = ddy[di];
int nx = cx + dx, ny = cy + dy;
if(nx < 0 || ny < 0 || nx >= 10 || ny >= 10) continue;
if((maze[ny] & (1<<nx)) == 0) continue;
if(dists[ny][nx] <= nd) continue;
dists[ny][nx] = nd;
dq[qi2++] = {nx, ny};
}
}
return dists;
}
bool dfs(const std::array<short, 10>& maze, std::array<char, 100>& marks, int x, int y, int px = -1, int py = -1)
{
static const int ddx[4] { 0, 0, 1, -1 };
static const int ddy[4] { 1, -1, 0, 0 };
marks[y * 10 + x] = true;
for(int di = 0; di < 4; di++)
{
int dx = ddx[di], dy = ddy[di];
int nx = x + dx, ny = y + dy;
if(nx < 0 || ny < 0 || nx >= 10 || ny >= 10) continue;
if(ny == py && nx == px) continue;
if((maze[ny] & (1<<nx)) == 0) continue;
if(marks[ny*10+nx]) return true;
if(dfs(maze, marks, nx, ny, x, y)) return true;
}
return false;
}
bool isTree(const std::array<short, 10>& maze)
{
std::array<char, 100> marks {};
if(dfs(maze, marks, 0, 0)) return false;
//for(int i = 0; i < marks.size(); i++) if(marks[i] == 0 && ...) return false; -- unnecessary
return true;
}
int getScore(const std::array<short, 10>& maze, bool treecheck = false)
{
if((maze[0] & (1<<0)) == 0) return -1;
if((maze[0] & (1<<9)) == 0) return -1;
if((maze[9] & (1<<0)) == 0) return -1;
if((maze[9] & (1<<9)) == 0) return -1;
if(treecheck && !isTree(maze)) return -1;
//get distances between corners
auto dTL = getDists(maze, 0, 0);
auto dTR = getDists(maze, 9, 0);
auto dBL = getDists(maze, 0, 9);
auto dBR = getDists(maze, 9, 9);
//printf("TL -> TL=%d, TR=%d, BL=%d, BR=%d\n", dTL[0][0], dTL[0][9], dTL[9][0], dTL[9][9]);
//printf("TR -> TL=%d, TR=%d, BL=%d, BR=%d\n", dTR[0][0], dTR[0][9], dTR[9][0], dTR[9][9]);
//printf("BL -> TL=%d, TR=%d, BL=%d, BR=%d\n", dBL[0][0], dBL[0][9], dBL[9][0], dBL[9][9]);
//printf("BR -> TL=%d, TR=%d, BL=%d, BR=%d\n", dBL[0][0], dBR[0][9], dBR[9][0], dBR[9][9]);
int mindist = std::min<int>({
dTL[9][0] + dBL[9][9] + dBR[0][9],
dTL[9][0] + dBL[0][9] + dTR[9][9],
dTL[9][9] + dBR[9][0] + dBL[0][9],
dTL[9][9] + dBR[0][9] + dTR[9][0],
dTL[0][9] + dTR[9][0] + dBL[9][9],
dTL[0][9] + dTR[9][9] + dBR[9][0]});
if(mindist >= (SHRT_MAX >> 3)) return -1;
return mindist;
}
int main()
{
std::mt19937 mt(time(0));
//std::array<short, 10> maze {
// 0b1110111111,
// 0b0010100101,
// 0b1110101101,
// 0b1001101011,
// 0b1011001010,
// 0b1110111011,
// 0b0000100001,
// 0b1110101111,
// 0b1010101000,
// 0b1011101111 }; //the current 97 answer
std::array<short, 10> maze {
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111,
0b1111111111 };
printf("%d\n", getScore(maze));
std::array<short, 10> bestmaze = maze;
std::set<std::array<short, 10>> seen;
int bestscore = getScore(maze), lastSeen = 0;
seen.insert(maze);
for(int64_t its = 0; bestscore < 98; its++)
{
int cx, cy;
cx = mt() % 10, cy = mt() % 10;
maze[cy] ^= 1 << cx;
if(its - lastSeen > 100)
{
lastSeen = its;
int i = mt() % seen.size();
auto it = seen.begin(); std::advance(it, i);
maze = *it;
}
int score = getScore(maze, bestscore >= 75);
if(score > bestscore || (score == bestscore && seen.count(maze) == 0))
{
if(score > bestscore) seen.clear();
bestscore = score;
seen.insert(maze);
printf("%d\n", score);
for(int y = 0; y < 10; y++)
{
for(int x = 0; x < 10; x++) printf("%c", maze[y] & (1<<x) ? '.' : '#');
printf("\n");
}
}
if(score > bestscore) bestscore = score, bestmaze = maze, lastSeen=its;
}
}
```