Summary

This is your first assignment asking you to write a Haskell program which is somewhat larger than just toy examples. You have to find out the most suitable way to solve the problem by yourself. For that purpose you will need to create suitable data structures and functions manipulating them so that a solution can be found, although the labs should provide you with more than just inspiration. You will also need to write some simple file reading functions that will let you access the test files.

The purpose of this assignment is to let you write fully functioning code from scratch: you won't get any deeper comments about your solution regarding the programming style before it fullfills the functional requirements (i.e., it works). Use testing for that purpose. We expect you to use Hlint in order to make your code readable before you submit it.

The assignment should be completed in pairs. (We assume lab pairs. Let us know if you need other configuration.)

Introduction

Sudoku is a number-based puzzle demanding you to complete a partially-filled 9x9 grid with digits 1 to 9 in a specific manner, namely so that no row, no column, and no 3x3 box (there are 9 of each type: rows, columns and boxes, altogether called units) has repeating digits in it.

In order to test your understanding of it you may wish to use one of many on-line Sudoku sites, like e.g., www.sudoku.com.

In order to make your solution generic, we will expect it to be applicable to ordinary 9x9 Sudoku, but also to a smaller, 4x4 one (redefined appropriately). As a (non-obligatory) extension, you may wish to test your solution also on a 16x16 grid.

The problem

Your task consists of writing a Haskell functionverifySudoku :: String -> Bool that verifies consistency of puzzles (partially filled Sudoku grids) given as input. A puzzle is considered consistent if it may be completed into a full Sudoku, with all grid cells filled in according to Sudoku rules.

For the purpose of this assignment you may assume that puzzle consistency may be verified by checking whether (1) all of the non-empty squares do not have conflicting peers (see lab 1 for definition of peers), AND (2) there are no "blocking" situations, allowing only conflicting peers to be placed in some square. Three examples (using 0s to denote empty cells and "|" for legibility, to separate units) of conflict situations (where values 2, 8 and 5, respectively, introduce conflicts):

003|020|600

900|305|001

001|826|400

008|102|900

700|000|008

006|708|200

002|609|500

800|203|009

005|010|300

========

200|080|300

060|070|084

030|500|209

000|105|408

000|000|000

402|706|000

301|007|040

720|040|068

004|010|003

========

000|000|907

000|420|180

000|705|026

100|954|000

050|000|040

000|507|009

920|108|000

034|059|000

507|000|000

You can find them in the file conflicts.txt.

Two examples of blocking situations, illustrated on a 4x4 grid:

01|20

02|10

30|00

40|00

====

12|34

00|00

30|42

01|00

You can find them in the file blockings.txt.

A collection of 50 simple puzzles, all obviously consistent, can be found here: easy50.txt. A collection of 20 inconsistent ones can be found here: inconsistent20.txt.

Your task

Write the Sudoku verifier that detects inconsistent (in the above defined sense) puzzles. You may only use Prelude functions in your solution. The solution should be generic, so that both 4x4 and 9x9 Sudokus can be handled by changing just one setting (e.g., rows and columns variables), that should be done automatically after detecting the size of Sudokus in the file. Your program should be able to read at least the four files with examples named above. Note that the format of the puzzles in the test files for this assignment differs from the one used during the labs, as individual puzzles are split among several rows (and separated by separator rows).

Submission

You are expected to submit one single file with the verifier module. The file should contain in the very beginning instructions describing how to run the tests of your code (and your names, of course). You may assume that we possess the test files named in this assignment (i.e., conflicts.txt, blockings.txt, easy50.txt, and inconsistent20.txt), although the file sizes may differ, i.e., they may contain either more or less test examples than 50 or 20, respectively (handle this gracefully). The code should be submitted via canvas.

The deadline is 29th April 2024, 23:59 CET. Plan your time appropriately!

You should receive a response/confirmation within approximately one week from the deadline, given you submit on time.