Sierra College Home Page

MySierra

Schedule of Classes

Canvas

# Contest: Do you Sudoku? (with solutions and winners)

### Winners!

We have winners! We have decided to offer TWO prizes each week. The first prize will go to the submission with the highest score. The second prize will go to the most clever and/or unusual submission.

See the contest rules for our grading rubric.

The winners are:

For best entry, the winner is **Bill Tierny**, with his Visual Basic submission and a combined score of 18.5.

The prize for most unusual submission goes to **Rob Wiese**, for his DOS batch script entry.

Both are posted below.

Congratulations!

### The Problem

The game of Sudoku is played on a 9x9 grid subdivided into nine 3x3 regions. Each grid call can contain a single number 1-9. There can be no repeated numbers in each row of the larger grid, each column of the larger grid, and within each 3x3 region. As you may know, the larger grid is only partially filled out to begin with and the object of the puzzle is to fill in the rest of the cells given the constraints listed.

You solve the puzzle by filling in the empty cells. As you play, you are constantly checking to see which numbers are available for you to choose from. That is, given a list of numbers which are already used in a particular row, column, or 3x3 region, you want to know which ones are still available.

### Specification

Method/function name: sudoku

Input: List or array of integers. The list can be of any length, although no input will have more than 30. The numbers can be any integer, including negatives.

Returns: List or array of integers, each in the range 1-9, which are not in the input list. The returned list does not need to be sorted.

### Examples

Input: 4, 2, 9, 1, 7

Returns: 3, 5, 6, 8

Input: (empty list)

Returns: 1, 2, 3, 4, 5, 6, 7, 8, 9

Input: 6, 9, 1, 2, 3, 8, 7, 5, 4

Returns: (empty list)

Input: 2, 9, 2, 18, 8, -45, 9, 1, 7, 456, 12, 3, 2, 8, 100, 5

Returns: 4, 6

Please note that this program does not actually solve a Sudoku game.

### What To Submit

Your program must be submitted in one of the following formats:

- A single source file (text only) with comments that include your name(s) and instructions on how to load, compile, and run your program.
- For Java submissions, a JAR file containing your .java files and a README file listing your name(s) and instructions on how to run your program or give input to your method.
- For all others, Zip file containing the source files and a README file listing your name(s) and instructions on how to load, compile, and run your program or give input to the method/function

All submissions must by in by 11:59pm on Monday, April 6. Send your submissions to **contest@cs.sierracollege.edu** with the subject "CONTEST: Sudoku". Be sure to read the contest rules and guidelines before submitting your entry.

Feel free to discuss this contest by adding your comments below!

### Bill Tierny's Solution

'Programmer: Bill Tierney CS27 Email: tallbillsemail@gmail.com Public Class sudokuNumbersForm Private Sub goButton_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles okButton.Click Me.outLabel.Text = Sudoku(inTextBox.Text.Split(" "c, ","c, ";"c, ":"c)).TrimEnd(" "c, ","c) End Sub Private Function Sudoku(ByVal numbersUsedString() As String) As String Sudoku = "" For validInteger As Integer = 1 To 9 Dim matchBoolean As Boolean = False For Each numberString As String In numbersUsedString If numberString = validInteger.ToString() Then matchBoolean = True : Exit For End If Next If Not matchBoolean Then Sudoku &= validInteger.ToString() & ", " End If Next End Function End Class

### Rob Wiese's Solution

@echo off ::################################################################## ::# Sudoku helper ::# ::################################################################## ::# Written by Rob Wiese ::# April 6, 2009 ::# Programming Contest. ::# Language: Windows NT batch language. ::# Compatible with NT 5.1 kernel. Should work with more recent versions. YMMV ::# Instructions: Save file as c:\temp\sudoku.cmd ::# Open a command prompt ::# Type cd /d c:\temp ::# Command line usage: ::# sudoku::# Like: ::# sudoku 5 3 9 8 1 ::# or ::# sudoku 1 ::################################################################# :: Setup the Environment setlocal ENABLEDELAYEDEXPANSION set TITLE= Sudoku Helper set VERSION=.03 set results= if exist .\sudoku.tmp del .\sudoku.tmp :: Create the universe of good numbers: for %%a in (1 2 3 4 5 6 7 8 9) do (set db_%%a=%%a) :start TITLE=%TITLE% echo: echo Sudoku Helper echo ========================================================= echo: :: Test command line input and assign to variables. if .%1==. @echo Congratulations - You have solved the puzzle and need no further help^^! & goto exit for %%b in (%*) do call :args %%b :: Determine what is missing based on the command line arguments. :: Remove in boundary numbers from the universe of good numbers. for /f %%d in (soduku.tmp) do ( for %%c in (1 2 3 4 5 6 7 8 9) do ( if %%c == %%d set db_%%c=)) :: Assign whats left to a variable for %%e in (%db_1% %db_2% %db_3% %db_4% %db_5% %db_6% %db_7% %db_8% %db_9%) do set results=!results! %%e :: Let the user know what they can still use to solve the puzzle: @echo You can still use: %results% goto exit ::################################################################## ::# Sub args ::# purpose evaluate command line args ::# ::################################################################# :args :: Throw away out of boundary arguments :: Save in boundary arguments if %1 GTR 9 goto :eof if %1 LSS 1 goto :eof echo %1 >> .\sudoku.tmp goto :eof :exit if exist .\sudoku.tmp del .\sudoku.tmp echo: echo ========================================================= echo Sudoku Helper - Finished. echo:

### Other Solutions

I've cooked up solutions in several programming languages. There were two approaches to solving the problem.

In one solution, you run through the list of given numbers (we'll call it G) and build a second list (N) of the numbers 1-9 that appear in G. Then you loop from 1-9, displaying that number if it does *not* appear in N.

In the second approach, you start with a list N of the numbers 1-9 (which could be represented by an array of Booleans, with "true" indicating that the number is in the N list). Then you run through G, removing the number from N (by setting the value to false) as you go. Finally, you run through N, printing out the remaining numbers.

There are, of course, other ways of doing this problem.

Without further ado, here are some of my solutions.

### Java

/** * * @author Barry Brown * @version 4/3/2009 * * This is a basic implementation of the algorithm using a boolean[] * (array of booleans). The array represents which numbers have been * seen in the input. * * Initally, the array of ten elements (0..9) is set to all false. * As we walk through the argument array, we set the corresponding entry * to true, indicating that the number has been seen. * * When done, we walk through the boolean array, printing out the index * if the corresponding entry is false. * */ public class Sudoku { public static void main(String[] args) { boolean[] isSeen = new boolean[10]; for (int i = 0; i < 9; i++) { isSeen[i] = false; } // Walk through args, setting the corresponding entry in isSeen to true for (int i = 0; i= 1 && num <= 9) { isSeen[num-1] = true; } } // Display what's left in the array. If the entry is false, the index // hasn't been seen and we should display it. for (int i = 0; i < 9; i++) { if (isSeen[i] == false) { System.out.print(i+1 + " "); } } System.out.println(); } }

### Perl

#! /usr/bin/perl # Read numbers from the command line. If they are in the range 1-9, store # a 1 at the corresponding location of the @sudoku array. foreach $num (@ARGV) { if ($num >= 1 and $num <= 9) { $sudoku[$num] = 1; } } # Run through the @sudoku array, displaying the index if the value # stored there is 0. for $i (1 .. 9) { print "$i " unless $sudoku[$i]; } print "\n";

### Scheme

; A convenience variable that contains all the numbers 1-9 (define whole-list '(1 2 3 4 5 6 7 8 9)) ; The top-level function ; sudoku the-list (list of numbers) --> list of numbers ; Given a list of numbers, return a list of the numbers 1-9 that are not ; in the given list. ; All this function does is invoke sudoku2 with the given list and the ; whole-list. (define (sudoku the-list) (sudoku2 the-list whole-list)) ; The function that does most of the work ; sudoku2 : remove-list (list of numbers), sudoku-list (list of numbers) ; --> list of numbers ; Given a two lists of numbers, remove the numbers in remove-list from ; the numbers in sudoku-list. (define (sudoku2 remove-list sudoku-list) (cond [(empty? remove-list) sudoku-list] [(empty? sudoku-list) '()] [(cons? remove-list) (sudoku2 (rest remove-list) (remove (first remove-list) sudoku-list))] )) ; A helper function. ; remove : num (number), lon (list of numbers) --> list of numbers ; Remove all occurences of num from lon (define (remove num lon) (cond [(empty? lon) '()] [else (cond [(= (first lon) num) (remove num (rest lon))] [else (cons (first lon) (remove num (rest lon)))] )] )) ; Examples (sudoku '()) (sudoku '(1 2 3 4 5 6 7 8 9)) (sudoku '(4 2 9 1 5 2 4)) (sudoku '(-8 18 2 4 2 9 5 456 45 200 1 5 2))

### bash and grep

#! /bin/bash TMPFILE=/tmp/sudokunumbers # Create a file with the numbers 1 .. 9 in it, one per line. # Uses a "here-document" to put the numbers into the file. cat >$TMPFILE <<DONE 1 2 3 4 5 6 7 8 9 DONE # Go through the command line arguments, using grep # to display the lines (numbers) that do not match the # argument. for i in "$@" do grep -v $i $TMPFILE > $TMPFILE.new mv -f $TMPFILE.new $TMPFILE done # Display what's left in the file and remove it. cat $TMPFILE rm $TMPFILE

### Perl (again)

#! /usr/bin/perl # Start with the list of all numbers 1 through 9 @sudoku = (1 .. 9); # For each command line argument, remove the number from @sudoku # by *keeping* the elements that are not equal to the given argument. for $arg (@ARGV) { @sudoku = grep { $arg != $_ } @sudoku; } # Display what's left print "@sudoku\n";

### bash and regular expressions

#! /bin/bash TMPFILE=/tmp/sudokunumbers # Create a file with the numbers 1 .. 9 in it, one per line. # Uses a "here-document" to put the numbers into the file. cat >$TMPFILE <<DONE 1 2 3 4 5 6 7 8 9 DONE # Convert the command line arguments into a regular expression. # For example: 4 9 1 56 -100 2 # becomes: 4|9|1|56|-100|2 # Do this by replacing one-or-more spaces by a pipe pattern=$(echo "$*" | sed -E 's/ +/|/g') # Remove the comment character below to see the pattern #echo $pattern # Use grep to display the lines (numbers) that do not match the # pattern. egrep -v "$pattern" $TMPFILE # Clean up after ourselves rm -f $TMPFILE