Home Store Project Ideas Project Guide Ask An Expert Blog Careers Teachers Parents Students

Program to Check a Sudoku Solution

Difficulty
Time Required Average (6-10 days)
Prerequisites An understanding of the material covered in ABC's of Programming: Writing a Simple 'Alphabetizer' with JavaScript
Material Availability Readily available
Cost Very Low (under $20)
Safety No issues

Abstract

Sudoku puzzles have become extremely popular over the past couple of years. You can find books of puzzles for beginners to experts, and many newspapers print Sudoku puzzles daily. This project challenges you to write a computer program to check if your Sudoku solution is correct.

Objective

The goal of this project is to write a JavaScript program to check a Sudoku puzzle answer. This is a good intermediate-level programming project for anyone interested in Sudoku puzzles.

Credits

Andrew Olson, Ph.D., Science Buddies

Cite This Page

MLA Style

Science Buddies Staff. "Program to Check a Sudoku Solution" Science Buddies. Science Buddies, 3 Oct. 2014. Web. 30 Oct. 2014 <http://www.sciencebuddies.org/science-fair-projects/project_ideas/CompSci_p023.shtml?from=Blog>

APA Style

Science Buddies Staff. (2014, October 3). Program to Check a Sudoku Solution. Retrieved October 30, 2014 from http://www.sciencebuddies.org/science-fair-projects/project_ideas/CompSci_p023.shtml?from=Blog

Share your story with Science Buddies!

I did this project I Did This Project! Please log in and let us know how things went.


Last edit date: 2014-10-03

Introduction

The goal of this project is to write a JavaScript program that will check your solution to a Sudoku puzzle and verify that it is correct. This is a good intermediate-level programming project. Who knows, if you get hooked on programming this could even be the beginning for writing a program to solve Sudoku puzzles!

Prerequisites

It is assumed that you know how to use a text editor to write an HTML file containing your program, and that you know how to load and run the file in your browser. You will also need to know the basics of how JavaScript functions can be written to work with HTML FORM elements. Specifically, you will be working with HTML TEXTAREA and INPUT elements, and using JavaScript String and Array objects in your functions. If you need help with any of this, read the Introduction section in: ABC's of Programming: Writing a Simple 'Alphabetizer' with JavaScript.

New Material

In this project, you will learn some important methods of program control logic, which you will use again and again as you write more programs. These methods are used in just about every programming language (though the actual syntax may vary slightly from language to language). Specifically, you will learn about the JavaScript "for" loop control statements, and "if...else" conditional statements. You will also learn about 2-dimensional arrays (lists of lists).

Writing a JavaScript Program to Check Sudoku Solutions

A Sudoku puzzle consists of a 9 × 9 grid of squares, partly filled in with single-digit numbers. The goal is to fill in all of the squares so that the digits 1–9 appear once and only once in each row, column, and in each of the 3 × 3 sub-squares (colored gray and white). In order to check that a solution is correct, your program will have to verify that each of the numbers 1–9 are used once in each of the nine rows, columns, and sub-squares of the puzzle. To help you get started, we've written four simple JavaScript functions which illustrate how to work with our JavaScript Sudoku FORM:

  1. the ReadCells() function reads each value in the Sudoku form, storing them in a two-dimensional array,
  2. the RestoreCells() function writes these values back to the puzzle (it won't work properly unless you've clicked the "Read Cells" button first),
  3. the ClearPuzzle() function erases all of the entries in the puzzle,
  4. the ClearTextArea() function erases the contents of the TEXTAREA.
There are four buttons below the Sudoku FORM, one for each function. Try them out to see what they do. We'll show you the JavaScript code for each of the functions later. Once you understand how the functions work, you'll have a good foundation for writing your solution-checking program.












The Sudoku Form

Here is the HTML FORM code for the first row of the puzzle:
<FORM NAME="Sudoku" METHOD="post">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_1" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="8">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_2" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="2">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_3" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="3">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_4" STYLE="BACKGROUND-COLOR:SILVER;" VALUE="">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_5" STYLE="BACKGROUND-COLOR:SILVER;" VALUE="">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_6" STYLE="BACKGROUND-COLOR:SILVER;" VALUE="">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_7" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="7">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_8" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="1">
<INPUT TYPE="TEXT" maxLength="1" SIZE="1" ID="C1_9" STYLE="BACKGROUND-COLOR:WHITE;" VALUE="5">
<BR>

Each cell in the row is an individual INPUT element. Because the input will be text, the TYPE attribute is set to "TEXT." Because answers are limited to a single digit, the maxLength attribute is set to 1 for each cell. The STYLE attribute is used to set the background color for each cell to either "WHITE" or "SILVER" (light gray). The VALUE attribute sets the cell's contents. There is also an ID attribute, which can be used by JavaScript functions to access individual cells. You'll see how to use the ID attribute shortly.

Below the puzzle are four buttons, one for each example function. Finally, Below the buttons, there is a TEXTAREA element, which is used for writing messages to the user. When you write your program, you can use a TEXTAREA for messages such as 'Your solution is correct!' or, 'Oops, I found 4 mistakes.'

The buttons are used to call JavaScript functions to do specific tasks. For your program, you'll want to have at least two buttons: 'Check Solution' and 'Clear Puzzle.'

Here is the code for one of our example buttons:
<INPUT TYPE="button" VALUE="Read Cells" NAME="ReadCellsButton" onClick="ReadCells()">

From this you can see that a button is an INPUT element whose TYPE attribute is set to "BUTTON." The VALUE attribute sets the text that will appear on the face of the button. When the user clicks on the button, the onClick attribute gives the name of the JavaScript function that is called. For this button, the function is 'ReadCells().' When you click the 'Read Cells' button, the 'ReadCells()' function is called. 'ReadCells()' reads the value of each cell in the puzzle, and stores the values in an array that other functions can access. The next section describes how this function works.

The 'ReadCells()' Function

The ReadCells() function needs a place to store the values from the Sudoku form. We will store the values in an Array, which we will call 'puzzle.' Because the RestoreCells() function also needs access to the values, we will make the puzzle Array a global variable. This means that the variable is declared outside of any function, which makes it accessible for any function to use. (As you learn more about object-oriented programming, you will see that there are better ways to take care of this need for access to variables from multiple functions. In the interest of keeping things simpler, we will use a global variable here.)

Since a Sudoku puzzle has nine rows, each with nine cells, we will make our puzzle array in the same format, i.e. two-dimensional. The following code snippet shows how it is done:

var puzzle = new Array(9);

for (i=0; i < 9; i++)
   puzzle[i]=new Array(9);

Remember that this code is placed at the beginning of our script, outside of any function definitions, so that puzzle is a global variable. This code is executed once, when the script is first loaded. The first line defines puzzle as an array with nine elements. Think of this as the nine rows of the array. Next, each of the rows needs to have storage space for nine cells. The for loop takes care of allocating this space.

Now if we want to access the value for the second row, third cell, we would write:
   puzzle[2][3].
In other words, the first array index (the number in the first set of square brackets) refers to the row, and the second array index (the number in the second set of square brackets) refers to the cell within that row.

Now that we have the puzzle array created, we can go on to the ReadCells() function. Here it is:

// reads values from the Sudoku form, stores them in the puzzle[][] array,
// and writes them to the OutputText TEXTAREAfunction ReadCells()
{
   var cell;

   document.getElementById('OutputText').value = "ReadCells():\n";
   for(i = 1; i <= 9; i++){
      for(j = 1; j <= 9; j++){
         cell = "C" + i + "_" + j;
         puzzle[i-1][j-1] = document.getElementById(cell).value;
      }
      document.getElementById('OutputText').value += puzzle[i-1].join(" ");
      document.getElementById('OutputText').value += "\n";
   }
}

The ReadCells() function reads each element in the Sudoku form, storing it in the corresponding position in the puzzle array. It also prints out what it has read in the TEXTAREA element. The first line starts the printout.
   document.getElementById('OutputText').value = "ReadCells():\n"
The document method 'getElementById' is used to refer to the 'OutputText' TEXTAREA element. The value attribute of the TEXTAREA is changed by this statement to show that this is the output of the ReadCells() function.

Next there are two nested for loops, to cycle through the rows and columns of the Sudoku puzzle. Notice that the loop counter variables, i and j, count from 1 to 9. Inside the loops, the 'Cell' string is created to refer to the ID attribute of each individual INPUT element:
   cell = "C" + i + "_" + j;
This line of code creates strings like "C1_1", "C1_2", "C1_3", just like the ID's we used for the INPUT elements for the Sudoku FORM. The next line within the nested for loops grabs the values from the Sudoku FORM and saves them in the puzzle array. Notice that because arrays in JavaScript are zero-based (i.e., the first cell in the first row would be puzzle[0][0]), we decrement the loop counters when we use them as indices for the puzzle array:
   puzzle[i-1][j-1] = document.getElementById(cell).value;

The remaining lines in the function are in the outer loop, so they are executed at the completion of each row:
JavaScript Arrays have a join() method, which joins all of the elements into a single string. The argument of the .join() method is the character you wish to use to separate the individual array elements in the joined string. So the first line joins all of the cells from a single row into one string, and adds this to the TEXTAREA (using the += assignment operator). The second line simply adds a newline character ('\n' is equivalent to pressing the <Enter> key when you're typing). The newline character is added so that each row appears on its own line in the TEXTAREA.

That's it for the ReadCells() function. The RestoreCells() function is next.

The 'RestoreCells() Function

The RestoreCells() function writes the values from the puzzle array back to the Sudoku form. It's exactly like the ReadCells() function, with two exceptions:

  1. instead of going from the FORM to the puzzle array, the values go the other way;
  2. there is no output to the TEXTAREA element. Here is the function code:
    // writes values from the puzzle[][] array to the Sudoku form
    function RestoreCells()
    {
       var cell;

       for(i = 1; i <= 9; i++){
          for(j = 1; j <= 9; j++){
             cell = "C" + i + "_" + j;
             document.getElementById(cell).value = puzzle[i-1][j-1];
          }
       }
    }

The 'ClearPuzzle()' Function

The next function is the ClearPuzzle() function. You'll want something like this for your solution-checking program so that you can easily clear the Sudoku FORM. As with the ReadCells() and RestoreCells() functions, ClearPuzzle() uses two nested forloops. In this case, each INPUT element is erased by setting it's VALUE attribute to the empty string ("", two quotation marks with nothing in between them). Here is the code:

// clears the Sudoku form
function ClearPuzzle(form)
{
   var cell;

   for(i = 1; i <= 9; i++){
      for(j = 1; j <= 9; j++){
         cell = "C" + i + "_" + j;
         document.getElementById(cell).value = "";
      }
   }

}

The 'ClearTextArea()' Function

The final function is the ClearTextArea() function. It works much like the ClearPuzzle() function, but it is simpler, because there is only one form element to clear: the TEXTAREA.

// clears the TEXTAREA below the Sudoku puzzle
function ClearTextArea(form){
   document.getElementById('OutputText').value = "";
}
If you've gotten this far, you should have all the information you need to write your Sudoku solution-checker. Your program will need a Sudoku puzzle FORM, at least two buttons ('Check Solution' and 'Clear Puzzle'), and a TEXTAREA for displaying messages to the user. Your 'CheckSolution()' function will need to do three things:
  1. Read the values from the Sudoku FORM into a two-dimensional array,
  2. Check to make sure that the numbers 1–9 are used once and only once in each
    1. row,
    2. column, and
    3. sub-square.
  3. If mistakes are found, they should be identified:
    1. print a message in the TEXTAREA with the total number of mistakes found,
    2. change the background color of each cell that has an error. Here is a code snippet to change the background color of a single cell (assuming that the variable Cell contains the ID string for the cell you wish to change:
      document.getElementById(Cell).style.backgroundColor='red;';
  4. If the solution is correct, print out a success message.

Remember to test your program thoroughly when it's completed to make sure that it catches all the errors that it should. Good luck with your project!

Note for JavaScript files with Internet Explorer:
If you experience difficulty running your JavaScript code in Internet Explorer, we strongly suggest that you install the Firefox web browser and use it instead of Internet Explorer. For more information or to download the Firefox installer, see: http://www.mozilla.com/firefox/.

If you want to continue to use Internet Explorer, try adding the following line at the beginning of your file:
<!— saved from url=(0014)about:internet —>
This line will cause Internet Explorer to run your file according to the security rules for the Internet zone on your computer. In our experience this may work, or it may not. For more information see: http://msdn.microsoft.com/library/default.asp?url=/workshop/author/dhtml/overview/motw.asp and http://www.phdcc.com/xpsp2.htm.

Terms and Concepts

To do this project, you should do research that enables you to understand the following terms and concepts:
  • HTML concepts:
    • start tags and end tags,
    • comments,
    • the <HEAD> section,
    • the <SCRIPT> section,
    • the <BODY> section,
    • the <FORM> section,
    • the <INPUT> tag,
    • the <TEXTAREA> tag.
  • JavaScript concepts:
    • functions,
    • variables,
    • objects,
    • properties,
    • methods,
    • events,
    • arrays (including 2-dimensional arrays);
  • specific JavaScript methods:
    • .getElementById(), is used to refer to a FORM element by its ID attribute,
    • .join(), an Array object method for joining all of an array's elements into a single string;
  • general programming concepts:
    • reserved words,
    • control statements (e.g., "if...else" statements, "for" loops),
    • operators:
      • assignment operators, (e.g., =,+=,-=,*=,/=),
      • comparison operators, (e.g., <,>,<=,>=,==),
      • logical operators (AND, OR and NOT, i.e., &&,||,!).

Questions

  • How do you program a button in an HTML form to call a JavaScript function?
  • getElementById
  • two-dimensional array

Bibliography

  • You can find a step-by-step JavaScript tutorial at the link below.
    Webteacher Software, 2007. "JavaScript Tutorial for the Total Non-Programmer, "Webteacher.com [accessed February 14, 2007] http://www.webteacher.com/javascript/index.html.
  • For information on HTML FORMS, here is the official reference:
    Ragget, D., A. Le Hors, I. Jacobs, (eds.), 1999. "HTML 4.01 Specification: 17. Forms," W3C Worldwide Web Consortium [accessed February 14, 2007] http://www.w3.org/TR/REC-html40/interact/forms.html.
  • This is a list of reserved words in JavaScript (you cannot use these words for function or variable names in your program, because they are reserved for the programming language itself):
    JavaScript Kit, 2004. "Reserved Words," JavaScriptKit.com [accessed February 14, 2007] http://www.javascriptkit.com/jsref/reserved.shtml.
  • Here is a JavaScript reference:
    Netscape Communications Corp., 1996. "JavaScript 1.1 Guide," [accessed February 14, 2007] http://wp.netscape.com/eng/mozilla/3.0/handbook/javascript/.
  • If you get interested and start doing a lot of programming, you may want to try using a text editor that is a little more sophisticated than Notepad. An editor designed for programming can help with formatting, so that your code is more readable, but still produce plain text files. This type of editor can also do "syntax highlighting" (e.g., automatic color-coding of HTML) which can help you to find errors. Here is a free programmer's editor that you can try:
    http://www.crimsoneditor.com/

Materials and Equipment

To do this experiment you will need the following materials and equipment:
  • computer with Web browser (e.g., Internet Explorer, Firefox),
  • text editing program (e.g., Notepad).

Share your story with Science Buddies!

I did this project I Did This Project! Please log in and let us know how things went.

Experimental Procedure

Using what you have learned about programming in Javascript, create a program that can verify if a Sudoku solution is correct. Here are some generally applicable programming tips to keep in mind as you get started with this project.
  1. Plan your work.
    • Methodically think through all of the steps to solve your programming problem.
    • Try to parcel the tasks out into short, manageable functions.
    • Think about the interface for each function: what arguments need to be passed to the function so that it can do its job?
  2. Use careful naming, good formatting, and descriptive comments to make your code understandable.
    • Give your functions and variables names that reflect their purpose in the program. A good choice of names makes the code more readable.
    • Indent the statements in the body of a function so it is clear where the function code begins and ends.
    • Indent the statements following an "if", "else", "for", or "while" control statement. That way you can easily see what statements are executed for a given branch or loop in your code.
    • Descriptive comments are like notes to yourself. Oftentimes in programming, you'll run into a problem similar to one you've solved before. If your code is well-commented, it will make it easier to go back and re-use pieces of it later. Your comments will help you remember how you solved the previous problem.
  3. Work incrementally.
    • When you are creating a program, it is almost inevitable that along the way you will also create bugs. Bugs are mistakes in your code that either cause your program to behave in ways that you did not intend, or cause it to stop working altogether. The more lines of code, the more chances for bugs. So, especially when you are first starting, it is important to work incrementally. Make just one change at a time, make sure that it works as expected and then move on.
    • With JavaScript, this is easy to do. To check your code, all you need to do is use your web browser to open the HTML file containing your code. After you've made a change in the code with your text editor, just save the file, then switch to your browser and hit the re-load page button to see the change in action.
    • Test to make sure that your code works as expected. If your code has branch points that depend on user input, make sure that you test each of the possible branch points to make sure that there are no surprises.
    • Also, it's a good idea to backup your file once in awhile with a different name. That way, if something goes really wrong and you can't figure it out, you don't need to start over from scratch. Instead you can go back to an earlier version that worked, and start over from there.
    • As you gain more experience with a particular programming environment, you'll be able to write larger chunks of code at one time. Even then, it is important to remember to test each new section of code to make sure that it works as expected before moving on to the next piece. By getting in the habit of working incrementally, you'll reduce the amount of time you spend identifying and fixing bugs.
  4. When debugging, work methodically to isolate the problem.
    • We told you above that bugs are inevitable, so how do you troubleshoot them? Well, the first step is to isolate the problem: which line caused the program to stop working as expected? If you are following the previous tip and working incrementally, you can be pretty sure that the problem is with the line you just wrote.
    • Check for simple typos first. A misspelled function name will not be recognized. In JavaScript, a misspelled variable name simply creates a new variable. This is an easy mistake to make, and can be hard to find.
    • Avoid using reserved words as variable or function names.
  5. Test your program thoroughly.
    • You should test the program incrementally as you write it, but you should also test the completed program to make sure that it behaves as expected.

Share your story with Science Buddies!

I did this project I Did This Project! Please log in and let us know how things went.


Variations

Share your story with Science Buddies!

I did this project I Did This Project! Please log in and let us know how things went.

Ask an Expert

The Ask an Expert Forum is intended to be a place where students can go to find answers to science questions that they have been unable to find using other resources. If you have specific questions about your science fair project or science fair, our team of volunteer scientists can help. Our Experts won't do the work for you, but they will make suggestions, offer guidance, and help you troubleshoot.

Ask an Expert

Related Links

If you like this project, you might enjoy exploring these related careers:

Computer programmer typing on a keyboard

Computer Programmer

Computers are essential tools in the modern world, handling everything from traffic control, car welding, movie animation, shipping, aircraft design, and social networking to book publishing, business management, music mixing, health care, agriculture, and online shopping. Computer programmers are the people who write the instructions that tell computers what to do. Read more
Software quality engineer working on database

Software Quality Assurance Engineer & Tester

Software quality assurance engineers and testers oversee the quality of a piece of software's development over its entire life cycle. Their goal is to see to it that the final product meets the customer's requirements and expectations in both performance and value. During the software life cycle, they verify (officially state) that it is possible for the software to accomplish certain tasks. They detect problems that exist in the process of developing the software, or in the product itself. They try and make things not work (try to "break" the software) by creating errors or combinations of errors that a user might make. For example, if a user enters a period or a pound sign for a password, will that break the software? They seek to anticipate potential issues with the software before they become visible. At the end of the life cycle, they reflect upon how problems or bugs arose, and figure out ways to make the software development process better in the future. Read more
Mathematician at work

Mathematician

Mathematicians are part of an ancient tradition of searching for patterns, conjecturing, and figuring out truths based on rigorous deduction. Some mathematicians focus on purely theoretical problems, with no obvious or immediate applications, except to advance our understanding of mathematics, while others focus on applied mathematics, where they try to solve problems in economics, business, science, physics, or engineering. Read more
NASA Computer hardware engineers hard at work

Computer Hardware Engineer

Whether you are playing video games, surfing the Internet, or writing a term paper, computers are an integral part of our daily lives. Computer hardware engineers work to make computers faster, more robust, and more cost-effective. They design the microprocessor chips that make your computer function, along with the equipment that makes computing easy and fun to do. Read more

Looking for more science fun?

Try one of our science activities for quick, anytime science explorations. The perfect thing to liven up a rainy day, school vacation, or moment of boredom.

Find an Activity