Столько постов написали, а человеку так ничего и не предложили, кроме полного перебора (что уныло).

Разрешение ситуации складывается из двух моментов:
1. (не относящееся к мату) В игру уже должна быть заложена невозможность сделать игроком такой ход, в результате которого его собственный король попадает под шах;
2. Чтобы проверять на мат, достаточно лишь проверить две вещи: может ли король сделать ход, не нарушающий условия п.1; или может ли ход любой другой фигуры, отвечающий требованиям п.1 закрыть короля от одной-двух фигур, угрожающих ему в результате последнего хода противника (нетрудно заметить, что их может быть две как максимум -- та, которой ходили, и та, которую открыли в результате хода).