3 ms·
This is a very nice exposition of the strategy, but I still don't see how it answers my more specific question, about whether you can solve the problem row by r
by tgb 10y ago
This is a very nice exposition of the strategy, but I still don't see how it answers my more specific question, about whether you can solve the problem row by row (is the grid).
- alxv 10y agoSorry, it turns that was misunderstanding from my part. It turns out we cannot solve a board row by row without revisiting the previous rows. The board below is a counterexample: 101 010 100 The first and second rows are solved. However we cannot solve the last row without re-doing the first and second rows. The two solutions of this board shows this: solution #1: 110 100 000 solution #2: 110 110 000 Actually, seeing my mistake made me challenge my assumption that a singular matrix over the reals might not be over integers modulo 2. This is likely wrong too. I don't know much about abstract algebra (and I am not a mathematician). Wikipedia (https://en.wikipedia.org/wiki/Determinant#Square_matrices_over_commutative_rings_and_abstract_properties https://en.wikipedia.org/wiki/Determinant#Square_matrices_ov...) states "the reduction modulo m of the determinant of such a matrix is equal to the determinant of the matrix reduced modulo m." The move matrix M for all boards of size 3n + 2 appears to be singular. This means these boards may have no solution or a large number of solutions.
- tgb 10y agoGotcha, thanks. FYI, a singular matrix taking values in {0,1} that is singular over R if and only if it is also singular over Z/2, for exactly the reason you provide, that the determinant commutes with modding by 2.