Problem Set 0: Learning Swift (ungraded)

Issue date	Monday, 8 January 2024
Due date	Sunday, 14 January 2024
Total points	0 points

Introduction

This problem set is ungraded, and is only here to encourage you to get a head start in learning Swift and software engineering in general. UI development is not a focus of this problem set.

Note that, ultimately, what you want to achieve from this problem set is up to you. There are many things that you can build on top of this problem set. If you have any questions or if you need any tips, please do not hesitate to contact the teaching staff.

You may ping the tutor to review your code before school starts.

tip

Be sure to check the additional notes for this Problem Set if you face any issues along the way!

Getting Started with Swift

Apple has provided extensive documentation on Swift and iOS development (it is in their best interest to do so). In the spirit of not reinventing the wheel, you are encouraged to refer to them, which we have linked to on the tips page.

Part 1: Starting Up

To warm up for CS3217, we will be building a Sudoku solver program. After all, if PM Lee can build one, surely CS3217 students can too!

For a quick refresher on what the Sudoku puzzle is, you may consult the Wikipedia page on it.

You should have received an invitation link to a GitHub Classroom. We will be using GitHub Classroom for all of our problem sets. Basically, you can use it to create a copy of our repository, and use that as a skeleton code. If you have not received it or it is not working, please double check that you have got in to our GitHub organisation. Failing that, contact the teaching staff.

At this point, you have three options in doing this problem set, from most recommended to least:

1. Use Xcode to open it. This is the recommended way, and it will possibly be the only way for you to work on the future problem sets while still keeping your sanity.

   To do this, you need to install Xcode on your macOS, and open the .xcodeproj file in Xcode, located in the xcode folder. Work on the xcode folder and ignore the swift folder.

2. Install Swift on Ubuntu. The programming language itself is actually open-source, which means you can download a precompiled binary or even build it yourself from source. If you choose this option, work on the swift folder and ignore the xcode folder.

   Note that for future problem sets, we will not cater for this option -- it is probably next to impossible to build iOS UI apps using only Swift without Xcode.

3. Open it from repl.it at https://repl.it/@donjar/CS3217ProblemSet0. Be sure to set the indentation to 4 spaces and (optionally) enable dark mode. Do fork and save the repl first before working on it. Note that this link is only provided for this problem set for you to experiment with Swift -- future problem sets won't have this option!

Regardless of how you decided to work with, you should see a codebase with the file Sudoku.swift on it. Inside is a Sudoku protocol. Things to ponder (answer it by yourself):

• what is a protocol?
• what does Apple mean when they say "protocol-oriented programming"?
• what does this file do? What does every line in this file mean?
• what are computed properties? How will that be useful when one wants to implement this protocol?

There is also Cell.swift inside, which contains the struct Cell.

• Why even create this struct in the first place when it is so short? Why not just pass row and cols around?
• Why is Cell a struct, not an enum or a class?
• Why does this struct need to implement the Hashable protocol?
• Why do we not need to specify any method to get the hash value from this struct, even though it implements Hashable?

Afterwards, you should notice that there is a .swiftlint.yml file inside. Use this opportunity to set up SwiftLint. Note that we have enabled quite a number of additional rules; you are free to disable some of them, if you feel that they impair readability. If you are using Xcode, you should be able to set SwiftLint to run automatically in it. You can even set it to automatically correct errors on save.

Note that if you are working on repl.it, you won't get a Swiftlint file; hence, it is recommended to just install Swift in your computer (or just SwiftLint, and manually copy-paste files, if need be).

Part 2: Implementing a NormalSudoku

Let us start by creating a NormalSudoku that implements this protocol. To do so, create a new file: in Xcode, from the menu bar, click File > New > File...; or use the shortcut Cmd-N. Afterwards, click "Swift File", and in the Save As box, type in "NormalSudoku" (or "NormalSudoku.swift"). If you are not using Xcode, just create a new file manually.

(You may wonder, why do we name this NormalSudoku? We are going to have more advanced Sudoku types as well! If you wish, you can rename this to whatever you think is best!)

First of all, you need to think first: should this NormalSudoku be an enum, struct, or a class? You can always refer to the Swift docs to aid you. If you still cannot decide, just stick with one -- changing it to another is most likely not going to be hard!

You should then see a new file pop up in the left sidebar. Now, delete the import Foundation (we do not really need it) and the comments above, if you wish, then write something like:

struct NormalSudoku: Sudoku {

}

This is if you decide to use a struct -- if you use an enum or a class, just change the keyword. The : Sudoku means that this struct implements the Sudoku protocol.

Now, you just need to implement the methods that is listed in the Sudoku.swift file! If you want a quick skeleton written for you, you can:

1. Run the project by clicking Product > Run or by pressing Cmd+R
2. See the error "Type NormalSudoku does not conform to protocol Sudoku"
3. Click on the red circle with white smaller circle inside (this means that Xcode can "auto-fix" the error)
4. Click "Fix" to "Do you want to add protocol stubs?" It should then generate a skeleton for you to fill in.

Now, your job is to fill in this file! Be sure to properly think about how to structure this type before you start coding. Use proper software engineering practices you have learnt!

Part 3: Implementing a SudokuSolver

Now that you are done with NormalSudoku, let us implement SudokuSolver to solve the Sudoku puzzles you just built!

Let us stop and think for a second here though. How do you actually implement a Sudoku solver? While it is not hard, it is not very trivial either -- spend some time sketching out an idea on how to solve it! If you are stuck, jump to the appendix at the end of this page (although make sure that you have tried to think it through!)

Note that your algorithm should hopefully only use the methods exposed by the Sudoku protocol. If you find that the Sudoku protocol is inadequate, you can add some more methods/properties into it; nevertheless, that protocol should be sufficient.

After you have come up with an algorithm, do write the function that implements it! Again, you need to think about how to write this function -- bare function? Function inside an enum/struct/class? Et cetera.

Note: in this problem set, performance is not a concern. You may use advanced algorithms if you wish, but the aim is more to familiarise yourself with Swift and software engineering principles. It is perfectly fine if your solver takes, for example, 1 hour or something.

Part 4: Testing your Implementation

After all of this hard work, let us actually test them to make sure that they work! To do so, create a file of type "Unit Test Case Class". Name the file whatever you want, and start writing some tests of your implementation!

If you are using Swift, you can create a new file in the folder Tests/SudokuSolverTests and follow the style of the given sample SomeTests.swift. Be sure to modify Tests/SudokuSolverTests/XCTestManifests.swift and Tests/LinuxMain.swift. If you are using repl.it, due to the restrictions on the website, you can do whatever you want such that when you press "run", all tests are run. A possible option (as shown in the current main.swift) is to put one test in each function, and make each function return a Bool indicating whether the tests passed or not.

Do note that there are actually two things that can be tested here -- the NormalSudoku implementation, as well as the SudokuSolver.

Don't know how to write tests in Swift? In the spirit of not repeating excellent tutorials in the internet, we encourage you to Google it out :]

Note: You might realise that when you actually test solving a Sudoku puzzle, it can take some time. This is actually normal in many cases. To mitigate this, you can take an easier Sudoku puzzle, or you can just fill in some of the empty spaces with numbers from the puzzle solution.

Again, we iterate that performance is not a concern in this problem set.

If your implementation uses some Set<Int> or a variant of it, the fastest way to perform operations is by using a bitmask. In fact, PM Lee actually uses bitmasks in his implementation of the Sudoku solver.

Part 5: Implementing More Advanced Sudoku Puzzles

The great thing about the Sudoku protocol is that it allows you to create more advanced Sudoku puzzles. To start with, let us implement Killer Sudoku. Despite its scary-sounding name, it is not as hard as it seems!

To achieve this, let us create another KillerSudoku type, similar to the NormalSudoku type that we created earlier. Make this somehow implement the Sudoku protocol as well. Now, if you pass in a KillerSudoku instance to SudokuSolver, you should be able to solve it without any modifications to SudokuSolver!

You might be confused in how to implement the options method. Give it some thought: if you have two boxes that sum to 4, what is the minimum and maximum number one of the boxes can have? What is these two boxes sum to 16 instead? What if you have 3 boxes that sum to, say, 23?

Don't forget write tests to make sure that your implementation works.

If you have finished KillerSudoku, you can go ahead and implement other variants if you wish.

Bonus: Reflection

If you reach here, congratulations! You should now be familiar enough with Swift to be able to start working on the real CS3217 problem sets. :]

You can ping the tutor so that your code can be checked. Also, do fill in this form so that we can get some feedback on this problem set. You will get 3 bonus points for completing this problem set and the feedback form. (Points before the semester even starts! Isn't CS3217 very generous?)

Appendix: How to solve a Sudoku Puzzle

The simplest method to solve a Sudoku is by some sort of a brute-force/complete search with some backtracking.

Start from an empty box. Fill in some number that is permitted. Keep doing this: take an empty box, fill in some number. If you can do this all the way such that all boxes are filled, great! Your puzzle is solved.

More likely than not though, you will get stuck on some empty box. By stuck, we mean that we encounter an empty box, but there is no number one can fill in that box that does not violate the rules. In this case, we backtrack: in the last box we filled, we replace that with another number. If there is no number in this box, we just keep on backtracking until we find another box that we can fill in with a different number.

This gif might make you understand it better:

This gif is made by Simpsons contributor - Program written in Java, letter images made in Photoshop, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=29034832. It comes from a Wikipedia page that lists some algorithms to solve Sudoku. You can also try some of them.