chiark / gitweb /
Group: hard-mode identity deduction.
authorSimon Tatham <anakin@pobox.com>
Fri, 22 May 2020 17:57:15 +0000 (18:57 +0100)
committerSimon Tatham <anakin@pobox.com>
Sat, 23 May 2020 08:08:25 +0000 (09:08 +0100)
commit6285c44610cda5146b11fb1fcda45e488a5504de
treeed7d493cdeb3f095dd42900ac05bf798e62b10ca
parent31cb5227e6df543a077910d0f3e7c7e169e7c01e
Group: hard-mode identity deduction.

This fills in the deduction feature I mentioned in commit 7acc554805,
of determining the identity by elimination, having ruled out all other
candidates.

In fact, it goes further: as soon as we know that an element can't be
the group identity, we rule out every possible entry in its row and
column which would involve it acting as a left- or right-identity for
any individual element.

This noticeably increases the number of puzzles that can be solved at
Hard mode without resorting to Unreasonable-level recursion. In a test
of 100 Hard puzzles generated with this change, 80 of them are
reported as Unreasonable by the previous solver.

(One of those puzzles is 12i:m12b9a1zd9i6d10c3y2l11q4r , the example
case that exposed the latin.c validation bug described by the previous
two commits. That was reported as ambiguous with the validation bug,
as Unreasonable with the validation bug fixed, and now it's merely
Hard, because this identity-based deduction eliminates the need for
recursion.)
unfinished/group.c