Related Links

• Science Fair Project Guide

Project Summary

Difficulty	6  –  10
Time required	Average (about one week)
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

Share this Project Idea! |

Donate to Science Buddies

Sponsor

Sponsored by a generous grant from Symantec Corporation

Internet Safety Tips

Get educated about online safety with help from Symantec.

symantec.com/norton/familyresources

Abstract

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.

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

New Material

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, below). 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.

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!

Terms, Concepts and Questions to Start Background Research

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).

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.

Variations

• For a more basic programming project, try Forms and Functions: Writing a Simple Calculator Program with JavaScript.
• Advanced. Do you think that you're up to the challenge of writing a program to solve Sudoku puzzles?

• For more science project ideas in this area of science, see Computer Science Project Ideas.

Credits

Andrew Olson, Ph.D., Science Buddies

Last edit date: 2007-03-23 20:30:00

Career Focus

If you like this project, you might enjoy exploring careers in Computer Science.

	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.			Software Quality Assurance Engineer and 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.
	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.			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.

Join Science Buddies Become a Science Buddies member! It's free! As a member you will be the first to receive our new and innovative project ideas, news about upcoming science competitions, science fair tips, and information on other science related initiatives. Support Science Buddies If this website has helped you, won't you consider a small gift so we may continue developing resources to help teachers and students?