Avoiding Monochromatic Rectangles Using Shift Patterns

Authors

  • Zhenjun Liu Carnegie Mellon University
  • Leroy Chew Technische Universität Wien
  • Marijn J. H. Heule Carnegie Mellon University

DOI:

https://doi.org/10.1609/socs.v12i1.18591

Keywords:

Search In Boolean Satisfiability, Combinatorial Puzzles, Symmetry Handling

Abstract

We show that enforcing shift patterns significantly reduces the cost to construct grids without monochromatic rectangles. Additionally, we prove that all valid 3-colorings of a 10 by 10 grid are isomorphic.
SoCS-2021 Proceedings Cover

Downloads

Published

2021-07-21

How to Cite

Liu, Z., Chew, L., & Heule, M. J. H. (2021). Avoiding Monochromatic Rectangles Using Shift Patterns. Proceedings of the International Symposium on Combinatorial Search, 12(1), 225–227. https://doi.org/10.1609/socs.v12i1.18591

Issue

Vol. 12 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Section

Student Papers