Colorings and Sudoku Puzzles

Authors

Katelyn D. May, Murray State UniversityFollow

Abstract

Map colorings refer to assigning colors to different regions of a map. In particular, a typical application is to assign colors so that no two adjacent regions are the same color. Map colorings are easily converted to graph coloring problems: regions correspond to vertices and edges between two vertices exist for adjacent regions. We extend these notions to Shidoku, 4x4 Sudoku puzzles, and standard 9x9 Sudoku puzzles by demanding unique entries in rows, columns, and regions. Motivated by our study of ring and field theory, we expand upon the standard division algorithm to study Gr\"obner bases in multivariate polynomial rings. We utilize Gr\"obner bases of an ideal of a multivariate polynomial ring over a finite field to solve coloring, Shidoku, and Sudoku problems. In the last section, we note Gr\"obner bases are also well-suited to hypergraph coloring problems.

Author Bio

Katelyn Danielle May will graduate from Murray State University in 2020 with a Bachelor of Science in mathematics. She plans to pursue a doctoral degree in mathematics after completion of her undergraduate course work. This paper was written as a research project originating from an exploration of field and ring theory within her Modern Algebra II course.

Faculty Sponsor

Kelly Pearson

Recommended Citation

May, Katelyn D. (2020) "Colorings and Sudoku Puzzles," Rose-Hulman Undergraduate Mathematics Journal: Vol. 21: Iss. 1, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol21/iss1/6