Every time you pick two tiles, the Shisen-Sho app checks, “Can these two tiles be connected by a line with two turns or fewer?” When Hint looks for a pair you can remove, it uses the same check on every pair. This article shows how it works, with a program.
The Idea: Widen the Reach for Each Turn
A line goes straight up, down, left, or right, and turns now and then. So starting from the first tile, we check like this.
- 0 turns: From the first tile, go straight in each of the four directions through open squares. If you reach the second tile, they connect.
- 1 turn: From each square you reached in step 1, change direction and go straight again.
- 2 turns: From each square you reached in step 2, change direction and go straight once more.
If you have not reached the second tile by the third round, the two tiles do not connect with two turns or fewer. Each straight run goes until it hits a tile or leaves the board.
Handling the Outside of the Board
A line can also pass through the one-square border outside the board. In a program, you can add one ring of empty squares around the board, and then the outside is treated as ordinary empty squares. For a board of 6 columns by 8 rows, you check a board of 8 columns by 10 rows.
In this diagram, the two 5 of Bamboo tiles at both ends of the top row connect with two turns through the empty squares outside at the top.
The Program
Written in JavaScript, it looks like this.
// board[r][c] is a tile name, or null if empty. One ring of empty squares is added around the board.
function canConnect(board, from, to) {
const rows = board.length;
const cols = board[0].length;
const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// The current square and the direction of the last move (-1 at the start)
let frontier = [[from[0], from[1], -1]];
const seen = new Set();
for (let turn = 0; turn <= 2; turn++) {
const next = [];
for (const [r0, c0, dir] of frontier) {
for (let d = 0; d < 4; d++) {
if (d === dir) continue;
let r = r0;
let c = c0;
while (true) {
r += steps[d][0];
c += steps[d][1];
if (r < 0 || c < 0 || r >= rows || c >= cols) break;
if (r === to[0] && c === to[1]) return true;
if (board[r][c] !== null) break;
const key = r + ',' + c + ',' + d;
if (!seen.has(key)) {
seen.add(key);
next.push([r, c, d]);
}
}
}
}
frontier = next;
}
return false;
} boardis the board with a ring of empty squares added around it. Tile squares hold the tile’s name, and empty squares holdnull.fromandtoare the[row, column]of the two tiles (positions on the board with the added ring).frontieris the list of squares you can reach with the current number of turns, along with the direction you moved to get there.- Going straight in the same direction again is skipped because the previous round already checked it (
d === dir). seenremembers that you have reached the same square in the same direction, so that you do not repeat the same check.
This program also checks whether the second tile is reached on the straight run after the second turn. You cannot pass over a tile, so a run stops where it hits one (only the second tile counts as a hit when you reach it).
Checking Against the App
We compared this program with the app’s own way of finding lines (the same calculation used for the diagrams in the site’s articles). We made 300 deals of 48 tiles in the same way as the app, including boards where some pairs had already been removed, and had the program judge 5,044 randomly chosen pairs of tiles. Its answers for connects and does not connect all matched.
When two tiles connect, the app draws the line on the screen, so it remembers not only whether they connect but also where the turns are. When there are several possible lines, it draws the one with fewer turns, and if they tie, the shorter one.
Finding Every Pair You Can Remove
To look for pairs you can remove, as Hint does, the app runs this check for each pair of tiles with the same picture. On a 48-tile board there are 72 such pairs, so at most 72 checks are enough. The number of pairs you can remove at the start is counted in How Many Pairs Can You Remove at the Start?.
