Sudoku Surface Project

From IPRE Wiki
Jump to: navigation, search

Surface Sudoku: Sudoku on the Microsoft Surface Table

Designed and Coded by Michelle Beard.

Rules of the Game

Complete the puzzle such that each row, column, and 3x3 region contains the digits 1...9

Design of the Game

  1. 9x9 grid
    1. TextBlock
    2. ListBox
  2. Menu
    1. New Game
    2. Save Game
    3. Level of Difficulty
      1. Easy
      2. Medium
      3. Hard
      4. Diabolical
  3. Buttons
    1. Display Rules
    2. Hints
    3. Start Over
    4. Undo
    5. Solve

9x9 grid

For this project, we choose to pick the standard representation of a Sudoku puzzle: a 9x9 puzzle with newspaper (black and white) style. In order to draw a grid for the game, using XAML, we created a grid of 9 rows and 9 columns, in which the actual grid's image was that of a Sudoku puzzle.

Thus, in a canvas, under XAML, we create our grid. The XAML code is

 <Grid Name="Sudoku" Background="{StaticResource WindowBackground}" 
             Height="630" Width="630" Visibility="Visible" ShowGridLines="False" 
             AllowDrop="False" Canvas.Left="12" Canvas.Top="20" HorizontalAlignment="Center">
           
           <Grid.RowDefinitions>
               <RowDefinition Name="row1" Height="70"  />
               <RowDefinition Name="row2" Height="70"  />
               <RowDefinition Name="row3" Height="70"  />
               <RowDefinition Name="row4" Height="70"  />
               <RowDefinition Name="row5" Height="70"  />
               <RowDefinition Name="row6" Height="70"  />
               <RowDefinition Name="row7" Height="70"  />
               <RowDefinition Name="row8" Height="70"  />
               <RowDefinition Name="row9" Height="70"  />
           </Grid.RowDefinitions>
           <Grid.ColumnDefinitions>
               <ColumnDefinition Name="col1" Width="70" />
               <ColumnDefinition Name="col2" Width="70" />
               <ColumnDefinition Name="col3" Width="70" />
               <ColumnDefinition Name="col4" Width="70" />
               <ColumnDefinition Name="col5" Width="70" />
               <ColumnDefinition Name="col6" Width="70" />
               <ColumnDefinition Name="col7" Width="70" />
               <ColumnDefinition Name="col8" Width="70" />
               <ColumnDefinition Name="col9" Width="70" /> 
           </Grid.ColumnDefinitions>

Here, we defined both our rows and columns of height and width 70px. Notice for the Sudoku grid, we assigned a background image. The reasoning behind this was the ease of creating a solid/thin black line to differentiate between the rows, columns, and regions in a Sudoku puzzle. However, if we ever want to resize the grid, we would also need to resize the image background. Thus, while this method is not flexible, it provides a clear and understandable background for the user.

TextBlock

The TextBlock is a UIElement in the System.Windows.Forms library. For this game, the TextBlock represents the givens of partially filled values of the puzzle. Note that the number of givens do not correspond to the difficulty of the puzzle, but the actual techniques used to solve the game, which I will talk about later.

ListBox

The ListBox is another UIElement in the System.Windows.Forms library. For this game, the ListBox represents the blank cells in the puzzle. The user will have to select a number 1...9 from the ListBox to fill in that particular cell.

TextBlock/ListBox Code

Since the TextBlock and ListBox elements will change depending on the puzzle, we need to create these elements dynamically using C#.

       public void FillBoxes(StreamReader sr)
       {
           data = new string[9, 9];
           copy = new string[9, 9];
           string temp = "";
           for (int r = 0; r < 9; r++)
           {
               for (int c = 0; c < 9; c++)
               {
                   temp = char.ConvertFromUtf32(sr.Read());
                   data[r, c] = temp;
                   copy[r, c] = temp;
                   if (temp != "0")
                   {
                       TextBlock txt = new TextBlock();
                       txt.AllowDrop = false;
                       txt.Text = temp;
                       txt.FontSize = 20;
                       txt.Foreground = Brushes.Black;
                       txt.FontWeight = FontWeights.Bold;
                       txt.VerticalAlignment = VerticalAlignment.Center;
                       txt.HorizontalAlignment = HorizontalAlignment.Center;
                       txt.SetValue(Grid.RowProperty, r);
                       txt.SetValue(Grid.ColumnProperty, c);
                       Sudoku.Children.Add(txt);
                   }
                   else
                   {
                       // Create Surface List Box to add values
                       SurfaceListBox lb = new SurfaceListBox();
                       lb.Width = 10;
                       lb.Height = 10;
                       for (int i = 1; i < 10; i++)
                           lb.Items.Add(i.ToString());
                        
                       lb.Background = Brushes.White;
                       lb.ContactTapGesture += new ContactEventHandler(lb_ContactTapGesture);
                       lb.SetValue(Grid.RowProperty, r);
                       lb.SetValue(Grid.ColumnProperty, c);     
                       Sudoku.Children.Add(lb);
                   }
               }
           }
           sr.Close();
       }


First, the program reads in the partially filled game from a text file, and depending whether or not the cell of the puzzle is empty or filled, a ListBox or TextBlock will be created. Givens will be presented in TextBlocks with a font color of black while blanks will be represented by a ListBox, which will contain the values 1...9.

Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Loaded game file onto Surface.

Element Menu

The SurfaceElementMenu is a new UIElement released in the SP 1 upgrade for the Microsoft Surface Table unit. With this element, we can define a tree like structure where the user can select options. For this game, we created three options: New Game, Save Game, and Open Game.

New Game

Currently, Surface Sudoku does not have a Sudoku puzzle generator, so for now we used an open-source program called QQwing to generate Sudoku puzzles of various levels. When the user selects "new game" from the element menu, an event will trigger where a puzzle will be read in from file, and the the TextBlocks or ListBoxes will be dynamically created.

       public void ReadGame(int level)
       {
           StreamReader sr = null;
           switch (level)
           {
               case 1:
                   sr = new StreamReader(System.IO.Path.GetFullPath(@"easy.txt"));
                   FillBoxes(sr);
                   break;
               case 2:
                   sr = new StreamReader(System.IO.Path.GetFullPath(@"medium.txt"));
                   FillBoxes(sr);
                   break;
               case 3:
                   sr = new StreamReader(System.IO.Path.GetFullPath(@"hard.txt"));
                   FillBoxes(sr);
                   break;
               case 4:
                   sr = new StreamReader(System.IO.Path.GetFullPath(@"diabolical.txt"));
                   FillBoxes(sr);
                   break;
               case 5:
                   try
                   {
                       sr = new StreamReader(System.IO.Path.GetFullPath(@"saved.txt"));
                       FillBoxes(sr);
                       break;
                   }
                   catch
                   {
                       text_results.Text += "Unable to resume game!\n";
                       break;
                   }
           }
       }    

Save Game

Unlike other games available on the Surface table like checkers and chess, the user can save the state of their game by selected in the "save game" option from the element menu. All the changes made to the game will be written to the hard drive.

       public void WriteFile()
       {
           string fileName = "saved.txt";
           string fullPath = System.IO.Path.GetFullPath(fileName);
           using (var writer = new StreamWriter(fileName))
           {
               for (int r = 0; r < 9; r++)
                   for (int c = 0; c < 9; c++)
                   {
                       {
                           writer.Write("{0}", copy[r, c]);
                       }
                   }
           }
       }

Open Game

Once a game is saved, the user has the option to resume the most recent game saved.

There is a few bugs encountered through this process. Most players of Sudoku can tell the difference from their changes by color. Also, when the user saves and resumes her game, the state of the board appears, including the changes in color. In this version of Surface Sudoku, the save option does not preserve the state of the board in regards to changes made by the user.

Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Element Menu

Buttons

Surface Sudoku also contains five buttons:

  1. Display Rules
  2. Hints
  3. Start Over
  4. Undo
  5. Solve

In the next five sections, we will describe the functionality of each of these buttons.

Display Rules

Display rules is a simple and convenient button for the user. All it does is display or hide the rules of Sudoku. For novice users, the rules may be needed, but for seasoned players, the textual display is not necessary.

Hints

There comes a time when playing a Sudoku puzzle where the user is stumped on what the next move should be. Most Sudoku games allow the user to use "hints" throughout game play. For Surface Sudoku, we created a hint button which can only give 4 hints per game. When the user selects the "hint" button, an click event will fire which will choose at random a blank cell of the puzzle and fill it in. We created a random number generator to generate integers between 0...8 for the rows and columns in order solve the cells of a puzzle.

       protected int GetRandomInt(int max)
       {
           System.Security.Cryptography.RandomNumberGenerator rnd = System.Security.Cryptography.RandomNumberGenerator.Create();
           byte[] r = new byte[1];
           rnd.GetBytes(r);
           double val = (double)r[0] / byte.MaxValue;
           int num = (int)Math.Round(val * max, 0);
           return num;  
       }


       private void hintBtn_Click(object sender, RoutedEventArgs e)
       {
           if (hints >= 4)
               text_results.Text += "Used up all hints!\n";
           else
           {
               while (true)
               {
                   int row = GetRandomInt(8);
                   int col = GetRandomInt(8);
                   backtrack(data, 0, 0);
                   if (copy[row, col] == "0")
                   {
                       TextBlock results = new TextBlock();
                       Collection<ListBox> elements = GetElements<ListBox>(Sudoku, row, col);
                       ListBox parent = (ListBox)elements[0];
                       Sudoku.Children.Remove(parent);
                       string actual_value = data[row, col];
                       copy[row, col] = actual_value;
                       results.Text = actual_value;
                       results.FontSize = 20;
                       results.Foreground = Brushes.Blue;
                       results.FontWeight = FontWeights.Bold;
                       results.VerticalAlignment = VerticalAlignment.Center;
                       results.HorizontalAlignment = HorizontalAlignment.Center;
                       results.SetValue(Grid.RowProperty, row);
                       results.SetValue(Grid.ColumnProperty, col);
                       Sudoku.Children.Add(results);
                       hints += 1;
                       break;
                   }
               }
           }
       }


This approach to coding the "hint" button is trivial, but future work needs to be done for the "hint" button to select the next most logical cell to complete.

Start Over

The "start over" button is also a trivial action where the user's moves will be cleared and the "hints" counter to be reset.

       private void stoverBtn_Click(object sender, RoutedEventArgs e)
       {
           Sudoku.Children.Clear();
           ReadGame(status);
           text_results.Clear();
           hints = 0;
           hintBtn.Visibility = Visibility.Visible;
           undoBtn.Visibility = Visibility.Hidden;
       }

Undo

As the user makes changes to the grid, they should have the option to undo their moves, especially if they have made a mistake. In the code for this button, we create a Stack object to collect the rows and columns changed by the user. As the user selects the "undo" button, the most recent change will be popped from the stack and a new ListBox will be created at that row and column. Note in the code that we first have to remove the TextBlock UIElement from the Sudoku grid before changing the cell to a ListBox.

       private void undoBtn_Click(object sender, RoutedEventArgs e)
       {
           if (moves.Count != 0)
           {
               ArrayList recentmove = (ArrayList)moves.Pop();
               int row = (int)recentmove[0];
               int col = (int)recentmove[1];
               Collection<TextBlock> elements = GetElements<TextBlock>(Sudoku, row, col);
               TextBlock parent = (TextBlock)elements[0];
               Sudoku.Children.Remove(parent);
               SurfaceListBox replace = new SurfaceListBox();
               for (int i = 1; i < 10; i++)
                   replace.Items.Add(i.ToString());
               replace.Height = 10;
               replace.Width = 10;
               replace.ContactTapGesture += new ContactEventHandler(lb_ContactTapGesture);
               replace.Background = Brushes.White;
               replace.SetValue(Grid.RowProperty, row);
               replace.SetValue(Grid.ColumnProperty, col);
               copy[row, col] = "0";
               Sudoku.Children.Add(replace);
           }
           else
               undoBtn.Visibility = Visibility.Hidden;
       }

Solve

If the user is stuck and has used up all their hints, they may choose to let the computer solve the puzzle. Currently, the algorithm to solve the puzzle is a backtracking algorithm or sometimes known as depth-first search.

Backtracking Solver

Backtracking is a simple to implement recursive procedure which uses brute-force methods to find the valid solution to a particular cell in a grid. While backtracking is considered to be the most computationally expensive of other Sudoku solvers, it guarantees to find a solution to an instance of a puzzle (even though we cannot guess how long it will take to find it).

       public bool backtrack(string[,] input, int r, int c)
       {
           if (c == 9)
           {
               c = 0;
               r += 1;
           }
           if (r == 9 && c == 0)
               return true;
           if (input[r, c] != "0")
               return backtrack(input, r, c + 1);    
           for (int v = 1; v < 10; v++)
           {
               if (! check(input, r, c, v.ToString()))
               {
                   input[r, c] = v.ToString();
                   if (backtrack(input, r, c+1))
                       return true;
               }
           }
           input[r, c] = "0";
           return false;
       }
Checking Constraints

Since Sudoku is a constraint game, we need to make sure that values being inputted are valid and do no break the rules of Sudoku.

       public bool checkRow(string[,] input, int row, string val)
       {
           for (int c = 0; c < 9; c++)
           {
               if (val == input[row, c])
                   return true;
           }
           return false;
       }
       public bool checkCol(string[,] input, int col, string val)
       {
           for (int r = 0; r < 9; r++)
           {
               if (val == input[r, col])
                   return true;
           }
           return false;
       }
       public bool checkSquare(string[,] input, int row, int col, string val)
       {
           int mrow = row - (row % 3);
           int mcol = col - (col % 3);
           for (int rr = mrow; rr < mrow + 3; rr++)
           {
               for (int cc = mcol; cc < mcol + 3; cc++)
               {
                   if (val == input[rr, cc])
                       return true;
               }
           }
           return false;
       }
       public bool check(string[,] input, int row, int col, string val)
       {
           if (checkRow(input, row, val))
               return true;
           if (checkCol(input, col, val))
               return true;
           if (checkSquare(input, row, col, val))
               return true;
           return false;
       }
Checking whether or not the puzzle is solved

Since Sudoku is NP-complete, we wrote a P function to check whether a puzzle is solved. The most basic way to check if a Sudoku puzzle is solved is to check if there are no empty grids left. There is another option and that is to check the solution to the puzzle by comparing it to the actual solution of the game (in user mode). An added constraint to Sudoku is that all puzzles must have one unique solution. Thus, this implies that no matter how many times the computer solves the puzzle, it will still get the same solution (this is also another reason why Sudoku is NP-complete since we cannot form a P formula to determine how long a computer will take to find another solution to an instance of a puzzle).

       public bool PuzzleSolved(string[,] input)
       {
           for (int r = 0; r < 9; r++)
           {
               for (int c = 0; c < 9; c++)
               {
                   if (input[r, c] == "0")
                       return true;
               }
           }
           return false;
       }

Event Handlers

This section will detail the most important handling of the events when the user taps on the grid of the surface where a ListBox element is located.

ListBox Tap Event

In order to play Surface Sudoku, the user must select a number from the populated list of numbers in the ListBox. However, in order to find where the user is tapping is tapping. By doing some research on event handling in C# for System.Windows.Controls, we were able to code the event.

When the user selects a ListBox value in a row and column, we first cast the sender object as a ListBox, since that is what the user just touched to activate the handler. Once we have our specific ListBox, we find where it is located on the grid by row and column. Now that we have those important numbers, we can remove the ListBox at that row and column and replace it with a TextBlock which will show what the user selected in blue text.


       public void lb_ContactTapGesture(object sender, ContactEventArgs e)
       {
           ListBox parent = (ListBox) sender;
           object val = GetDataFromListBox(parent, e.GetPosition(parent));
           TextBlock results = new TextBlock();
           int col = Grid.GetColumn(parent);
           int row = Grid.GetRow(parent);
           if (val != null)
           {
               if (!check(copy, row, col, val.ToString()))
               {
                   Sudoku.Children.Remove(parent);
                   results.Text = val.ToString();
                   results.FontSize = 20;
                   results.Foreground = Brushes.Blue;
                   results.FontWeight = FontWeights.Bold;
                   results.VerticalAlignment = VerticalAlignment.Center;
                   results.HorizontalAlignment = HorizontalAlignment.Center;
                   results.SetValue(Grid.RowProperty, row);
                   results.SetValue(Grid.ColumnProperty, col);
                   Sudoku.Children.Add(results);
                   copy[row, col] = val.ToString();
                   ArrayList saves = new ArrayList();
                   saves.Add(row);
                   saves.Add(col);
                   undoBtn.Visibility = Visibility.Visible;
                   moves.Push(saves);
               }
               else
               {
                   text_results.Text += "Incorrect value " + val.ToString() + " inputted!\n";
               }
           }
           if (!PuzzleSolved(copy))
               text_results.Text += "Solved!";
       }
Grab Data from ListBox

When the user selects a ListBox, we need to find what value was selected from the nine possible values (1-9). Given a source (ListBox) and the position of the ListBox on the surface, we can find the data the user selected on the ListBox.

       public static object GetDataFromListBox(ListBox source, Point point)
       {
           UIElement element = source.InputHitTest(point) as UIElement;
           if (element != null)
           {
               object data = DependencyProperty.UnsetValue;
               while (data == DependencyProperty.UnsetValue)
               {
                   data = source.ItemContainerGenerator.ItemFromContainer(element);
                   if (data == DependencyProperty.UnsetValue)
                   {
                       element = VisualTreeHelper.GetParent(element) as UIElement;
                   }
                   if (element == source)
                   {
                       return null;
                   }
               }
               if (data != DependencyProperty.UnsetValue)
               {
                   return data;
               }
           }
           return null;
Find Element from Row and Column

The uses of the hint button allows the user to reveal an answer to a cell. While it is non-trivial to choose at random the location of a blank cell and solve it, it was difficult to find the element located at that row and column. The opposite is much more simple, since given an element, we can call Grid.GetRow(UIElement) to find the row where that element is located. Thus, it was suggested from online sources to write a query to search through a grid at a specific row and column. Thus, we wrote a LINQ where we are given a grid, search through the children of the grid and find the element that matches at that particular row and column.

       public static Collection<TElement> GetElements<TElement>(Grid grid, int row, int column) where TElement : UIElement
       {
           var elements = from UIElement element in grid.Children
                          where element is TElement &&
                                Grid.GetRow(element) == row &&
                                Grid.GetColumn(element) == column
                          select element as TElement;
           return new Collection<TElement>(elements.ToList());
       }

Surface Sudoku V.1.00

Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Splash Screen
Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Playing the game
Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Solved game by user
Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Solution to game
Video of Surface Sudoku in Action Surface Sudoku Code

Future Work

Sudoku Surface V.1.00 is a playable game, but there exist many bugs in the program that can hinder the user experience during game play.

  1. When the user saves the state of their game and resumes it, they are unable to tell where their changes occurred since all the text being read in is treated as the givens of a Sudoku puzzle.
  2. While it is fine for now to read in from a text file a puzzle, it would be more elegant to create a Sudoku puzzle generator. Or, something that might be interesting is to install a script to run QQwing to generate a puzzle at some level and save it as text file to be read in by the game. Another option would be to look up a puzzle online and download it. Continuing with this idea, if the user would like to play the current Sudoku puzzle offered at the New York Times website, the user can have the option to download that puzzle from New York Times and have it appear on the Surface table.
  3. The user interface needs much work. Currently, there is only one color scheme (black and white), but later versions of Surface Sudoku can have more options for interesting color schemes. For example, by using the PictureBox element, the user can see a thumbnail of the background before they select it.
  4. In the original design of Sudoku surface, we were coming up with a way for a LibraryStack element to contain images 1-9. When the user clicks and drags the scatter object to the grid, an element will fire and the data from the image would be read in. Thus, a particular row and column containing a TextBlock element would change their text to the number associated with the image.
  5. Currently there is no sound/music during game play, so there should be an option for the user to activate the music player.