We are interested with a classic minesweeper-style problem. We are given a 7 times 7 field where some of the cells have numbers between 0 and 8, inclusive, and all remaining cells have dots. We want to find such allocation of exactly 10 stars to the cells with dots, at most one star per cell, so that each cell with a number has exactly that number of stars in its 8 adjacent cells. Moreover, we will only consider such 7 times 7 fields where such allocation of 10 stars exists and is unique.

Since the size of the field is very small, it's natural to use backtracking for this problem. More specifically, we will use the following algorithm (the Java code is listed below): for each cell, row-by-row, we try not to put a star there and recursively continue with the next cell, then try to put a star there and recursively continue with the next cell. As soon as there's a cell with a number which has more stars adjacent to it, we backtrack since there's no chance of successfully completing the field. As soon as all adjacent cells of a cell have been filled and there're too few stars there, we backtrack as well. When we manage to find a solution for the entire field, we output it and terminate.

Now the question is: does this solution run fast enough? You need to find out! The challenge is to create a 7 times 7 field that:

- Has unique solution.
- Makes the described algorithm to perform as many recursive calls as possible before finding that solution.

I've got a testcase which I believe to be close to the toughest possible, but I'm waiting for you to prove me wrong :)

Here's the exact code which we're talking about:

import java.io.*; import java.util.*; public class Backtrack { boolean validate(char[][] board, int r, int c) { if (r > 0 && c > 0) { if (board[r - 1][c - 1] >= '1' && board[r - 1][c - 1] <= '9') return false; } if (r > 0 && c == 6) { if (board[r - 1][c] >= '1' && board[r - 1][c] <= '9') return false; } if (r == 6 && c > 0) { if (board[r][c - 1] >= '1' && board[r][c - 1] <= '9') return false; } if (r == 6 && c == 6) { if (board[r][c] >= '1' && board[r][c] <= '9') return false; } return true; } boolean rec(char[][] board, int r, int c, int remaining) { if (r >= 7) { return remaining == 0; } if (c >= 7) { return rec(board, r + 1, 0, remaining); } if (validate(board, r, c)) { if (rec(board, r, c + 1, remaining)) return true; } if (remaining > 0 && board[r][c] == '.') { boolean ok = true; board[r][c] = '*'; for (int rr = r - 1; rr <= r + 1; ++rr) for (int cc = c - 1; cc <= c + 1; ++cc) if (rr >= 0 && rr < 7 && cc >= 0 && cc < 7) { char ch = board[rr][cc]; if (ch >= '0' && ch <= '9') { board[rr][cc] = (char) (ch - 1); if (ch == '0') ok = false; } } if (ok && validate(board, r, c)) { if (rec(board, r, c + 1, remaining - 1)) return true; } for (int rr = r - 1; rr <= r + 1; ++rr) for (int cc = c - 1; cc <= c + 1; ++cc) if (rr >= 0 && rr < 7 && cc >= 0 && cc < 7) { char ch = board[rr][cc]; if (ch >= ('0' - 1) && ch <= '9') { board[rr][cc] = (char) (ch + 1); } } board[r][c] = '.'; } return false; } public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] input = new String[7]; for (int i = 0; i < 7; ++i) input[i] = reader.readLine(); char[][] board = new char[7][]; for (int i = 0; i < 7; ++i) board[i] = input[i].toCharArray(); Backtrack backtrack = new Backtrack(); if (!backtrack.rec(board, 0, 0, 10)) throw new RuntimeException(); for (int i = 0; i < 7; ++i) { for (int j = 0; j < 7; ++j) { if (input[i].charAt(j) == '.') System.out.print(board[i][j]); else System.out.print(input[i].charAt(j)); } System.out.println(); } } }