Main components
Sudoku is a complex puzzle, comprised of a 9 x 9 cell grid divided into columns, rows and 3x3 blocks. Each must contain 1-9 with no conflicts or duplication. There are many solvers that rely on brute force, but this solver uses most of the algorithms that actual people use. There is complex logic for these algorithms, backed up by forcing-chain algorithms and, if all else fails, a 'smart' recursive descent/backtrack search that utilizes prior knowledge of candidates and cells with solutions. I wanted to see how many of the algorithms I could research, 'computerize' and construct.
The solver has 24 built in puzzles with varying complexity and has a keypad with navigation tools for manual entry of your own puzzles. One display shows the 9x9 grid and the other shows the progress made by algorithm application that either clears a candidate or places a solution in a cell. Solution progress is indicated and timed.
Since the displays come with micro-SD slots, I added some robot-themed cartoons for the idle display, the main menu, the configuration menu and the manual entry routine.
Most of the expert puzzles can be solved without resorting to the recursive search.
/*
Sudoku Puzzle Solver
A Sudoku (i.e. the puzzle) is a partially completed grid.
A grid has 9 rows, 9 columns and 9 boxes, each having 9 cells (81 total).
The program first tries to solve the input puzzle using solution algorithms including:
1. Naked Single
2. Hidden Single
3. Pointing and Claiming (Locked Candidates)
4. Naked Pair,Triple,Quad
5. Hidden Pair,Triple,Quad
6. X-Wing
7. Y-Wing (aka XY-Wing)
8. XYZ-Wing
9. WXYZ-Wing
10. Swordfish
11. Jellyfish
12. Unique Rectangle (Type 1)
13. Unique Rectangle (Type 2)
14. Unique Rectangle (Type 3)
15. Unique Rectangle (Type 4)
16. Unique Rectangle (Type 5)
17. Hidden Rectangle
These solution algorithms use a classic "candidate-based" approach using an initial build of all candidate entries
for each cell that is not initially filled by the input grid. Candidates are the same as "pencil marks" or
"marks" in a manual/paper Sudoku puzzle
If the algorithm-based solutions fail (and they do for certain input puzzles!), the program switches first to "Forcing Chain" algorithms including XY-Chain, X-Chain, Medusa 3_D, Forbidding Chain
(that adds group nodes to X-Chain to enhance strong links) and Remote Pair and finally to a "Recursive Descent/Backtrack" solution search that is optimized using only the remaining candidates for
each attempt made to fill the remaining empty cells. That should work for any legal input puzzle.
Development started in February 2021 and Forcing Chain was added in mid-June.
Unique Rectangle added in July 2021
Additional chain solutions (remote pair, X Chain) added in August
Version 1.0 -- 7-7-21 First 'complete' version with all algorithms in place
7-9-21 Add new puzzle
7-15-21 Added Unique Rectangle Types 1,2,4 (see Sudoku_Puzzles) and remote pair chain
8-18-21 Added X-Chain and two new recursive demos
8-25-21 Added XYZ-Wing
9-7-21 Added Hidden Rectangle
9-28-21 Add Forbidding Chain which is a Type 1 Nice Loop and an extension of X Chain
10-1-21 Fix bug that occassionally set up wrong Solution Grid
10-27-21 Added Medusa 3D, beginning to add its elimination rules
12-27-21 Added "Workout" puzzle
03-29-22 Continue clock code
04-14-22 Date, time and temperature added
05-10-22 Small updates to idle screen
Acknowledging the very critical help from online Sudoku resources for descriptions, explanations, puzzles and quick development of test-bed solutions, including:
HoDoKu
SudokuSolutions
SudokuOfTheDay
Sudokuonline.io
Sudoku Snake
SudokuWiki.org
*/
// #define Test_Mode1 // if defined, loads test puzzles and runs
// #define Test_Mode2 // if defined, preloads a demo puzzle in input mode
// #define Test_Mode3 // check against pre-input solution (usually on if 1 is on, goes with Test_Mode1)
#define Test_Show // if not defined, turns off some of the Show_XXX routines used for debugging
#include <Adafruit_GFX.h> // graphics library
#include <Adafruit_ILI9341.h> // color display
#include <SdFat.h> // SD card & FAT filesystem library
#include <Adafruit_SPIFlash.h> // SPI / QSPI flash library
#include <Adafruit_ImageReader.h> // Image-reading functions
#include "RTClib.h" // real time clock library
#include "Sudoku_Puzzles.h" // test and demo puzzles
#include <Keypad.h> // keypad library
// Initialize for Adafruit DS3231 RTC real time clock
RTC_DS3231 rtc;
// Color display 1
#define TFT1_DC 9 // color display control pins
#define TFT1_CS 10
#define SD1_CS 4 // SD card select pin
// Comment out the next line to load from SPI/QSPI flash instead of SD card:
// on Mega use SPI Hardware CLK = 52, MISO = 50, MOSI = 51, CS = 10, DC = 9 (for last two, whatever is declared ast TFT1_DC and TFT1_CS)
Adafruit_ILI9341 tft1 = Adafruit_ILI9341(TFT1_CS, TFT1_DC);
// Color display 2
#define TFT2_DC 11 // color display control pins
#define TFT2_CS 12
#define SD2_CS 7 // SD card select pin
// on Mega use SPI Hardware CLK = 52, MISO = 50, MOSI = 51, CS = 10, DC = 9 (for last two, whatever is declared ast TFT2_DC and TFT2_CS)
Adafruit_ILI9341 tft2 = Adafruit_ILI9341(TFT2_CS, TFT2_DC);
// Comment out the next line to load from SPI/QSPI flash instead of SD card:
#define USE_SD_CARD
#if defined(USE_SD_CARD)
SdFat SD; // SD card filesystem
Adafruit_ImageReader reader(SD); // Image-reader object, pass in SD filesys
#else
Adafruit_SPIFlash flash(&flashTransport);
FatFileSystem filesys;
Adafruit_ImageReader reader(filesys); // Image-reader, pass in flash filesys
#endif
Adafruit_Image img; // An image loaded into RAM
// Keypad
// * AdaFruit PID3844 4x4 Matrix Keypad (need only if you use the Adafruit key library rather than keypad.h)
// define pins here - this keypad is pinout (with keys facing you)
// * 0 # D (keys facing you)
// nc C1 C2 C3 C4 R1 R2 R3 R4 nc (nc = no connection)
#define R1 32 // row connections 1-4
#define R2 33
#define R3 34
#define R4 35
#define C1 38 // column connections 1-4
#define C2 39
#define C3 40
#define C4 41
const byte KROWS = 4; //four rows
const byte KCOLS = 4; //four columns
char Kkeys[KROWS][KCOLS] = { // key map for key.h library
{'1','2','3','A'},
{'4','5','6','B'},
{'7','8','9','C'},
{'*','0','#', 'D'}};
byte KrowPins[KROWS] = {32,33,34,35}; //connect to the row pinouts of the keypad
byte KcolPins[KCOLS] = {38,39,40,41}; //connect to the column pinouts of the keypad
Keypad K_Keypad = Keypad( makeKeymap(Kkeys), KrowPins, KcolPins, KROWS, KCOLS );
/*
* 0 through 9 (48-57) are numbers
* * 42 is Backspace
* # 35 is Forward line (cycling)
* A 65 is Reset/Load Puzzle
* B 66 is Run Puzzle
* C 67 is is Configure
* D 68 is Demo (Run next internal puzzle)
*/
// Current use of Keypad Note Main Mode/Entry Mode definitions below
#define K_Fnumber 48 // lowest number 0
#define K_Lnumber 57 // highest 9
#define K_Backspace 42 // * backspace during entry
#define K_Forward 35 // # Goes forward one space during entry
#define K_Input 65 // (A) Go to Entry Mode/Reset (wipe) entered puzzle in input mode
#define K_Solve 66 // (B) Solve Loaded Puzzle/Return from Input Mode to Execute Puzzle
#define K_Check 67 // (C) Configuration Changes/Check puzzle validity
#define K_Demo 68 // (D) demo next puzzle/Play Sudoku
int K_Char = 0; // returned decimal value of key press
int K_Demo_Current = 0; // for each press of D increment
const int K_DC_Interval = 750; // cursor flash interval during puzzle input
unsigned long DC_Timer; // used for non blocking timer
bool Show_SD_Image; // used to see if SD demo images working
const int SD_Robots = 3; // number of rrx images to use
const int Delay_After_Solve = 10000; // delay after solving to clear the scroll screen
unsigned long Sleep_Timer; // used for non blocking timer
unsigned long Sleep_Interval = 300000; // interval with no input to go back to sleep demo
// debugging and display tools // named after Digital Equipment Corporation's DDT (dynamic debugging technique)
void DDTv(String st, int vt, bool CRR) { // Print descriptor and value
Serial.print(st);
if (CRR) {Serial.println(vt);} else {Serial.print(vt);}} // if Carriage return request <NL> then do so
void DDTvl(String st, unsigned long vt, bool CRR) { // Print descriptor and value
Serial.print(st);
if (CRR) {Serial.println(vt);} else {Serial.print(vt);}} // if Carriage return request <NL> then do so
void DDTn(int st, bool CRR){ // print a number
if (CRR) {Serial.println(st);} else {Serial.print(st);}}
void DDTs(String st, bool CRR){ // print a string
if (CRR) {Serial.println(st);} else {Serial.print(st);}}
void DDTsp(bool CRR){if (CRR) {Serial.println(" ");} else {Serial.print(" ");} } // print one space (to separate values, etc.
const bool NL = true; // new line after Show_NRC and DDTx
const bool SL = false; // don't, i.e., no <newline>
char Dstring[ ] = "1 2 3 1 2 3 1 2 3 ";
char Bstring[ ] = " ";
const byte DHoffset [] = {0,3,6, 10,13,16, 20,23,26};
const byte DVoffset [9] = {6,13,20,27,34,41,48,55,62};
const byte HStart = 10;
// constants for TFT Color display
const byte Ver1 = 2; //x axis of lh vertical line
const byte Ver2 = 79; //x axis of 2nd vertical line
const byte Ver3 = 159; //x axis of 3rd vertical line (don't care about rh, 4th)
const byte Hor1 = 2; //y axis of first (top) horizontal line
const byte Hor2 = 79; //y axis of 2nd horizontal line
const byte Hor3 = 159; //y axis of 3rd horizontal line
const byte Hor4 = 240; //y axis of 4th horizontal line (bottom of puzzle grid)
const byte Dis1 =10; //x displacement of first digit from nearest line
const byte Dis2 = 33; //x displacement of 2nd digit from nearest line
const byte Dis3 = 55; //x displacement of 3rd digit from nearest line
const byte BoxOffsets[3] = {Dis1,Dis2,Dis3}; // array of offsets left to right and top to bottom for 1st, 2nd and 3rd digit in box
const byte Msg1Offset = 27; // y axis displacement from bottom of grid to one line message
const byte Msg1TextSize = 4; // text sizes are 1-5 (small to largest) (if 5, its max of 8 and pw of 15 and offset 20)
const byte Msg1TextMax = 10; // maximum characters for single line message
const byte Msg1PW = 12; // character width in pixels (for centering adjustment)
const byte Msg2Offset = 16; // y axis displacement from bottom of grid to two line message
const byte Msg2TextSize = 3;
const byte Msg2TextMax = 13; // maximum characters for double line message
const byte Msg2PW = 9; // character width in pixels (for centering adjustment)
const byte Msg3Offset = 6; // y axis displacement from bottom of grid to three line message
const byte Msg3TextSize = 2;
const byte Msg3TextMax = 20; // maximum characters for three line message
const byte Msg3PW = 6; // character width in pixels (for centering adjustment)
const int T_Msg_Delay = 3000; // after a scroll message - keep display for a bit
const byte DigitTextSize = 2; // size of text for puzzle grid display
const byte T_ScrollTextOffsetVert =2; // distance to scrolling messages from top
const byte T_ScrollTextOffsetHor =8; // distance to scrolling messages from top
const byte T_ScrollTextSize = 1; // very small for updates
const byte T_Scrolling_Limit = 29; // maximum number of lines on display
const int Scrolling_Text_Line_Delay = 100; // delay after each line printed on progress/move display
const int Scrolling_Text_Page_Delay = 500; // delay before clearing current page
const int Scroll_Display_Delay = 2000; // used to wait between successive displays
const int Scroll_Error_Delay = 3000; // after error message before resetting progress display
bool Scrolling_Text_Just_Cleared = false; // used to skip initial delay
int T_Scrolling_Pointer = 0; // pointer for display
const int Grid_Color = ILI9341_GREEN; // color for puzzle grid
const int Display1_Color = ILI9341_YELLOW; // display portion of main (Puzzle) TFT display
const int Display2_Color = ILI9341_WHITE; // display portion of main (Puzzle) TFT display
const int Constant_Color = ILI9341_BLACK; // input digits
const int Entry_Color = ILI9341_BLUE; // and placed numbers
const int Msg1_Color = ILI9341_BLUE; // text color in display area - puzzle display
const int Msg2_Color = ILI9341_BLACK; // text color in display area - progress display
int Date_Time_Num; // used to build clock stuff
int Date_Time_Num_Year; //
int Date_Time_Num_Month; //
int Date_Time_Num_Day; //
int Date_Time_Num_Hour; //
int Date_Time_Num_Minute; //
int Date_Time_Num_Second; // not input but is displayed
int Date_Time_Num_DOW; // day of the week
bool Date_Time_Num_Valid; // used to check clock input
int Old_Minute = 61; // persistent minute to control sleep screen refresh
float fc = 0.0; // receives floating point temperature in celcius
int ifc =0; // convert to integer and adjust c to f
float fc_adjust = -8.0; // adjustment to temperature because its not calibrated
const int Display_Temp_Cycle = 15; // Display temp every n seconds
int Display_Temp_Counter = 0; // Seconds counter to decide temp vs time
String daysOfTheWeek[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
String monthsOfTheYear[12] = {"January", "February", "March", "April", "May", "June", "July","August", "September", "October", "November", "December"};
bool Show_Clear_Place = true; // Show Candidate clearing and placement
bool Use_Algorithms = true; // use algorithms before reverting to recursive descend/backtrack
bool Use_All_Demos = false; // normally, run just one demo on "D" command at main menu
byte Demo_Counter = 0; // used as above
byte Box_Coords [9][2] = {{0,0},{0,3},{0,6},{3,0},{3,3},{3,6},{6,0},{6,3},{6,6}}; //Row and Column coords of each of the 9 boxes
const byte Row_Pointer = 0; // index to row within Box_Coords, CanCoord, RR_CC etc.
const byte Column_Pointer = 1; // and index to column
byte Puzzle_Grid [9][9]; // Puzzle working solution and display grid
#ifdef Test_Mode3
byte Solution_Grid [9][9]; // and pre done solution (used for test)
#endif
char Puzzle_Buffer [25]; // returned puzzle name
String Puzzle_Name;
int Puzzles_Number = sizeof(Puzzles_List)/2; // number of test/demo puzzles
byte Cell_Entry =0;
int Cell_Pointer = 0;
const int Minimum_Starting_Clues = 17; // literature says no unique solution puzzle has less than 17 clues
int Occurence_Counter = 0; // persistent placement counter for algorithms
int RR_CC[3][2]; // used to store coordinates of found instances (e.g. for pointing pair)
int RR_CC_Ptr = 0;
byte SWF [9][6]; // array for x-wing,swordfish & jellyfish algorithms (numbr of candidate bits, membership in x,sword and fish and [C1][C2][C3][C4] or [R1][R2][R3][R4] marks)
const int SWF_Number_Found = 0; // index into SWF for how many of the marks are stored
const int SWF_Member =1; // index into SWF for a flag for whether this row/column is part of the x,s or j fish
const int SWF_Marks = 2; // where up to 4 columns or rows start to be stored
int SWF_Membership = 0; // number of members (has to be 2,3, or 4 depending on x-wing, swordfish or jellyfish)
int SWF_Start = 0; // and this is the starting c/r for the unit being checked
int SWF_Mask = 0; // this is # of columns or rows across ALL columns/rows checked against initial
int Digit_Array[10]; // quick place to unpack digits 0-9
int Y_Wing_Z; // used to globally return Y wing candidate to clear
bool No_Solution; // set true by routines like RD and Unique Rectangle that can detect no solution to end Solve loop
String PTQ_String[3] = {{"Pair"}, {"Triple"}, {"Quad"}}; //used for displays to identify source of 'move'
int Match_Counter = 0; // match counter for naked and hidden searches
int BitMask = 0; // bitmask used for matching
int BitMask_Result = 0; // found match
byte CanCount[9]; // number of candidates in each analyzed cell
int CanCand[9]; // contents for each analyzed cell
bool CanMark[9]; // used to mark which cells match/don't match
byte CanCoord [9][2]; // coordinate pointers back to main Candidates matrix
int CC_Length = 0; // number of active candidates in analytical array (0-9)
int CCC = 0; // calculated candidate counter
String Row_Labels[] = {"A","B","C","D","E","F","G","H","I"}; // can change to 0-9 if you want
// Hierarchy is Puzzle ==> Box (0-8), Rows, Columns and Cell
// Boxes, Rows and Columns run 0-8 (not 1-9), and each has both a 'total filled' count in cell 0, and knock-in markers in cells 1-9
// Where that cell (1-9) will be non-zero if that number exists in the row or column or box
int Filled = 0; // how many cells are filled (will end with 81)
int Last_Filled = 0; // total at start of pass
int Last_Total_Candidates = 0; // same for candidates because you can have a pass where candidates change but nothing placed
int Chain_Filled = 0; // number of filled cells when entering chain solutions
int Chain_CCC = 0; // same
int Passes = 0; // number of passes til solution
unsigned long Solve_Timer; // time it took for the solution
int Candidates[9][9] ; // candidate matrix is cell x 9 possible contents - each cell has 1-9 as markers for a candidate in 'bits' switched on
// e.g. if a candidate cell contains 2,6,9 then bits 2,6, and 9 are 'on' as candidates, starting from rh side (don't make this a byte -- too small!)
byte Candidates_Count[9][9]; // contains the number of bits turned on in this cell, hence the number of candidates
const int RDC_Max_Size = 81-Minimum_Starting_Clues;
const byte RDC_CurrCan = 2; // re-use Row_Pointer and Column_Pointer from above (index 0 and 1).. this adds a 'current candidate marker'
byte RDC_Matrix [RDC_Max_Size][3]; // Recursive descent matrix -- possible blank matrix, so r,c, and which candidate we are up to. This would fit a minimum-clue puzzle
int RDC_Length = 0; // the number of blank cells we actually have at start of recursive descent/backtrack
int RDC_Ptr = 0; // and current pointer - points to recursive level and CurrCan array, row and column
int RDC_Calls = 0; // recursive calls counter
byte FC_R [RDC_Max_Size]; // forcing chain -- pointer to the row of each 2-candidate cell (copied into from RDC Matrix after its loaded by Cand_Load2)
byte FC_C [RDC_Max_Size]; // pointer to column
byte FC_CN[RDC_Max_Size][2]; // contains the two candidates
int FC_UD[RDC_Max_Size][2]; // contains the 'up' and/or 'down' marker -- as each chain is followed (Soduku Solver terminology)
const byte FC_1 = 0; // index to first (or left-hand) candidate in FC_CN and FC_UD
const byte FC_2 = 1; // 2nd or right hand
const byte FC_Up = 0b00000001; // bit marker for an 'up'
const byte FC_Down = 0b00000010; // bit marker for a 'down'
const byte FC_UpandDown = FC_Up | FC_Down;
const bool MD_Mark_Green = true; // flip flop on color for this cell
const byte MD_Green = 0; // index to 'Green' -- each '1' bit marks a candidate position that is colored green (really same as FC_1 and 2)
const byte MD_Yellow = 1; // index to 'Yellow' -- each '1' bit marks a candidate position that is colored yellow (for coloring algorithms)
byte MD_Green_Candidates; // candidates colored - used for display/diagnostics
byte MD_Yellow_Candidates;
bool MD_Eliminated_Candidate; // don't use multiple Medusa rules if prior MD rules 'worked' because underlying data could be bad
const byte FC_Flag = 99; // used as flag to bypass after use
bool FC_List[RDC_Max_Size];
bool FC_Invoked = false;
const int FC_Max_Heads = 25; // maximum number of direct successors each recursion can loop through (8 in my row + 8 in my box + 8 in my column)
byte FC_Ptr; // incremental store into array
const bool Strong_Link = true;
const bool Weak_Link = false;
byte XC_Link_Counter; // X Chain link counter and row, column of head of the chain
byte XC_Head_R;
byte XC_Head_C;
unsigned int FC_Used_List[RDC_Max_Size]; // used by more complex 'used list' for forbidding chain and x-chain
byte WXYZ_Didnt_Match; // candidate that DIDN'T match(i.e. 'x') out of {589} as base against {x,5}, {x,8} or {x,9}
byte WXYZ_Match; // candidate that DID match (these are used by WXYZ_BitsMatchOne), so one of 5,8, or 9
void setup(void) {
Serial.begin(9600);
ImageReturnCode stat; // Status from image-reading functions
tft1.begin(); // initialize color display is 240 wide (horizontal) by 320 long (vertical)
tft2.begin(); // initialize 2nd color display, also 240 wide (horizontal) by 320 long (vertical)
// The Adafruit_ImageReader constructor call (above, before setup())
// accepts an uninitialized SdFat or FatFileSystem object. This MUST
// BE INITIALIZED before using any of the image reader functions!
Serial.print(F("Initializing filesystem..."));
#if defined(USE_SD_CARD) // Note: the SD Card seems to fail the first time AFTER
// SD card is pretty straightforward, a single call... // an upload but works subsequently (next power up cycle)
Show_SD_Image = true; // assume its working
if(!SD.begin(SD1_CS, SD_SCK_MHZ(25))) { // ESP32 requires 25 MHz limit
DDTs("SD begin() failed",NL);
Show_SD_Image = false;}
#else
// SPI or QSPI flash requires two steps, one to access the bare flash
// memory itself, then the second to access the filesystem within...
if(!flash.begin()) {
DDTs("flash begin() failed",NL));
Show_SD_Image = false;}
if(!filesys.begin(&flash)) {
DDTs("filesys begin() failed",NL);
Show_SD_Image = false;}
#endif
if (! rtc.begin()) { // check that clock is there
T_Msg2("RTC", "Didn't Start"); // clock missing is an error
delay(T_Msg_Delay);} //
if (rtc.lostPower()) { // if power lost, notify
T_Msg2("RTC", "Lost Power!");
delay(T_Msg_Delay);
T_Msg2("Replace","Battery?");
delay(T_Msg_Delay);}
else
{DateTime now = rtc.now(); // else just reload from RTC
Date_Time_Num_Year = now.year();
Date_Time_Num_Month = now.month();
Date_Time_Num_Day = now.day();
Date_Time_Num_Hour = now.hour();
Date_Time_Num_Minute = now.minute();
Date_Time_Num_Second = now.second();
Date_Time_Num_DOW = now.dayOfTheWeek();
T_Msg3("Clock Set", FDM_DT(Date_Time_Num_Year,Date_Time_Num_Month,Date_Time_Num_Day,Date_Time_Num_Hour,Date_Time_Num_Minute),daysOfTheWeek[Date_Time_Num_DOW]);
delay(T_Msg_Delay);
}
#ifndef Test_Mode1
Sleep_Demo(); // show start/sleep demo
#endif
T_Display_Setup(); // clear and create color display
Clear_Scroll_Display(); // and display of 'moves' (scrolling progress display(
#ifdef Test_Mode1 // test mode loads test puzzle and runs
for (int i = 0; i < Puzzles_Number; i++){
T_Display_Setup();
Clear_Scroll_Display();
Transfer_Test(i); // get the puzzle
DDTv("Puzzle Grid Fetched ",i+1,SL);
DDTs(" Named ",SL);
DDTs(Puzzle_Name,NL);
T_Msg3("Fetching",FDM("Puzzle ",i+1,""),Puzzle_Name); // offset by 1 for readability
T_Scroll_Message(FDM("Puzzle ",i+1," Loaded"));
T_Scroll_Message(Puzzle_Name);
Examine_Puzzle(); // analyze the puzzle
Puzzle_Check(); // check the puzzle
Solve_Puzzle(); // and solve it
Clear_Puzzle(); // clear puzzle grid
delay(Scroll_Error_Delay);}
while(true){;}
#endif // Test_Mode 1
K_Return_To_Main();
K_Char = 0;
Sleep_Timer = millis(); // set sleep timer
} // end of Setup
void loop(void) {
K_Read(); // read keypad
switch (K_Char){
case K_Demo: // is it demo mode (D)?
K_Char = 0; // yes, clear it
if (Use_All_Demos) { // if doing all, load all
Clear_Scroll_Display();
for (K_Demo_Current=0; K_Demo_Current< Puzzles_Number;K_Demo_Current++) {Run_Test();}
} else
{ Clear_Scroll_Display();
T_Scroll_Message(F("Select Puzzle to Run"));
T_Scroll_Message(F("Enter Two Digit Puzzle Number"));
T_Scroll_Message(FDM("From 01 to ",Puzzles_Number," "));
T_Msg3("Enter Puzzle # ",FDM("1 to ",Puzzles_Number,""),"to run");
while(K_Char == 0){K_Read();}
if (K_Char >= K_Fnumber && K_Char <= K_Lnumber){ // if its a digit
K_Demo_Current = K_Char - K_Fnumber;
K_Char = 0; } //clear
while(K_Char == 0){K_Read();}
if (K_Char >= K_Fnumber && K_Char <= K_Lnumber){ // if its a digit
K_Demo_Current = ((10*K_Demo_Current)+(K_Char - K_Fnumber));} // form 2 digit number
if (K_Demo_Current > 0 && K_Demo_Current <= Puzzles_Number){
K_Demo_Current--; // correct 1-n to 0-(n-1)
Run_Test();} else
{T_Scroll_Message("Invalid Puzzle Number!");
T_Msg3("Not a valid","Puzzle Number",FDM("",K_Demo_Current,""));
delay(Scroll_Display_Delay);}}
K_Return_To_Main();
Sleep_Timer = millis(); // reset sleep timer
break;
case K_Input: // look for puzzle entry (A)
K_Char = 0;
Clear_Puzzle();
T_Display_Setup();
T_Msg2("Load", "Puzzle"); // display state
K_Get_Puzzle(); // get puzzle input, loaded and ready
K_Return_To_Main(); // indicate we've returned
Sleep_Timer = millis(); // reset sleep timer
break;
case K_Solve: // solve current puzzle
K_Char = 0;
Examine_Puzzle(); // make sure it is legal
DDTv("Filled is ",Filled,NL);
if (Filled > 0){ // but only if not blank
if (Puzzle_Check()){
Clear_Scroll_Display(); // new progress display
Solve_Puzzle();
delay(Delay_After_Solve);
K_R_T_M_Scroll_Only();} else // check the puzzle
{ T_Msg3("Puzzle Doesn't","Check Out","Try Again");}}
Sleep_Timer = millis(); // reset sleep timer
break;
case K_Check: // Configuration
K_Char = 0;
K_Configure();
K_Return_To_Main();
Sleep_Timer = millis(); // reset sleep timer
break;
case K_Backspace: // used to go into sleep mode
K_Char = 0;
Sleep_Demo(); // show start/sleep demo
K_Return_To_Main();
Sleep_Timer = millis(); // reset sleep timer
break;
default:
K_Char = 0;
break;
} // end of switch K_Char
if (millis() - Sleep_Timer > Sleep_Interval) {
Sleep_Demo(); // show start/sleep demo
K_Return_To_Main();
Sleep_Timer = millis();}
} // end of "loop"
void Examine_Puzzle(){ // set up analytical contents
Filled = 0; // reset counters
int Cell_Entry = 0;
for (int r = 0; r < 9; r++){
for (int c = 0; c < 9; c++){ // if its a non-zero cell
Cell_Entry = Puzzle_Grid[r][c];
if (Cell_Entry > 0){
Filled++; // another cell is filled
T_Number(r,c,Cell_Entry,Constant_Color); // and enter initial cell on color display
} // end of looking at the specific cell
} // end of looking at the column in row
} // end of looking at this row
CCC = 0; // candidates count initialized
Build_Candidates(); // build the candidates matrix
Show_Grid(); // show initial puzzle grid
} // end of Examine Puzzle
bool Puzzle_Check(){ // check puzzle for initial integrity
int Cell_Entry; // Note: can't check to see if it has a solution
if (Filled < Minimum_Starting_Clues){
DDTv("Puzzle has too few initial clues ",Filled,NL);
T_Msg3("Puzzle Error",FDM("Only ",Filled," Clues"),"Try Again");
T_Scroll_Message(F("Too few cells filled at start"));
T_Scroll_Message(F("Single solution needs >=17 clues"));
return false;}
for (int r = 0; r <9; r++){ // check loaded puzzle for integrity
for (int c = 0; c <9; c++){
Cell_Entry = Puzzle_Grid[r][c];
if (Cell_Entry > 0){
if (!RD_Check(Cell_Entry, r,c)){
DDTs("Input Puzzle has an error at ",SL);
Show_NRC(Cell_Entry,r,c,NL);
Show_Grid(); // and final puzzle grid
T_Msg3("Puzzle","Conflict", FDM_NRC(Cell_Entry,r,c));
T_Scroll_Message("Cell Entry");
T_Scroll_Message("Conflict Error");
T_Scroll_Message("Entry Invalid");
return false;}}
else {
if (Candidates_Count[r][c] ==0){ // if its an unfilled cell, it has to have candidates
DDTs("Input Puzzle has an error at ",SL);
Show_NRC(Cell_Entry,r,c,NL);
DDTv("Candidates for cell = ",Candidates_Count[r][c],NL);
T_Msg3("Puzzle","Candidate Error", FDM_NRC(Cell_Entry,r,c));
T_Scroll_Message("Cell with no candidates error");
return false;}}
}}
return true;
} // end of Puzzle_Check
void Solve_Puzzle(){
String Pass_String; // differentiate one from multiple
String Time_String;
DDTv(F("Starting Algorithm Solution with "),Filled,SL);
DDTv(F(" Cells Filled and Starting Candidate Count of "),CCC,NL);
T_Msg3("Solving",FDM(" with ",Filled," Cells"),FDM(" and ",CCC," Candidates"));
T_Scroll_Message(F("Starting with Algorithms"));
T_Scroll_Message(FDM("with ",Filled," cells filled"));
T_Scroll_Message(FDM(" and ",CCC," candidates"));
Passes = 0; // reset pass counter
No_Solution = false; // assume there IS a solution
FC_Invoked = false; // we haven't used forcing chain
Solve_Timer = millis(); // get starting timer
do { // stop when the puzzle is solved
Passes++; // increment pass counter
Last_Filled = Filled; // store filled BEFORE doing anything
Last_Total_Candidates = CCC; // both filled and candidates
//solving routines follow
if (Use_Algorithms){ // if not jumping to recursive routine
Naked_Singles();
Hidden_Singles();
Hidden_Pairs_Triples_Quads();
Naked_Pairs_Triples_Quads();
Pointing();
Claiming();
X_Wing();
Y_Wing();
XYZ_Wing();
WXYZ_Wing();
Swordfish();
Jellyfish();
Unique_Rectangle();
Hidden_Rectangle();
} // end of normal algorithms
if (Filled == 81) { // solved when all cells filled!
DDTsp(NL);
DDTv("Done! ",Filled,SL);
DDTv(" Cells Filled in ", Passes,SL );
DDTs(" Passes",NL);
Show_Grid(); // and final puzzle grid
T_Scroll_Message("Solved the Puzzle!!");
Solve_Timer = (millis()-Solve_Timer)/1000;
if (Passes > 1) {Pass_String = " Passes";} else {Pass_String = " Pass";}
if (Solve_Timer > 1) {Time_String = " Seconds";} else {Time_String = " Second";}
T_Scroll_Message(FDM("Completed in ",Passes,Pass_String));
T_Scroll_Message(FDM(" and it took ",Solve_Timer,Time_String));
T_Msg3("SOLVED!",FDM("in ",Passes,Pass_String), FDM("taking ",Solve_Timer,Time_String));
return;}
if (Filled == Last_Filled && CCC == Last_Total_Candidates) { // initial check for no progress
if (!FC_Invoked){ // have we tried the chain solutions?
DDTs(F("Trying Chain Solutions!"),NL); // console and progress panel msgs
T_Scroll_Message(F("Trying Chain Solutions"));
T_Msg3("Trying","Chain","Solutions");
// try the 'easy' chain solutions first
DDTs(F("XY-Chain..."),NL); // console and progress panel msgs
T_Scroll_Message(F("XY-Chain..."));
XY_Chain(); // call XY Chain Forcing Chain
DDTs(F("X-Chain..."),NL); // console and progress panel msgs
T_Scroll_Message(F("X-Chain..."));
X_Chain();
if (Filled == Last_Filled && CCC == Last_Total_Candidates){ // second layer of 'less easy' slower chains solutions
DDTs(F("Medusa 3-D ..."),NL); // console and progress panel msgs
T_Scroll_Message(F("Medusa 3-D ..."));
Medusa_3D();
DDTs(F("Remote Pair..."),NL); // console and progress panel msgs
T_Scroll_Message(F("Remote Pair..."));
Remote_Pair(); // call remote pair chain algorithm
DDTs(F("Forbidding Chain..."),NL); // console and progress panel msgs
T_Scroll_Message(F("Forbidding Chain..."));
Forbidding_Chain();}
FC_Invoked = true;} // set flag that we've tried it
if (Filled == Last_Filled && CCC == Last_Total_Candidates) // if STILL no progress, then fall through to recursive search
{ DDTv("Algorithms Stumped at ",Filled,NL); // if didn't find anything new, only recursive search/backtrack is left to do!
DDTs("Too close for missiles -- switching to guns!",NL);
T_Msg3(FDM("Stumped at ",Filled," Filled"),"2 Close for Missiles","Switch to Guns!");
T_Scroll_Message(FDM("Stumped at ",Filled," Cells Filled"));
T_Scroll_Message("Too Close for Missiles");
T_Scroll_Message("Switching to Guns!");
delay(2000);
if (!RD()){ DDTs("No Solution",NL);
No_Solution = true; // end it
DDTs("Recursive Search Failed",NL);
T_Msg3("Recursive","Search","Failed!");
T_Scroll_Message("Recursive Search Failed");
if (Filled == 80){T_Scroll_Message("Multiple Puzzle Solutions");
T_Scroll_Message("Not a Legal Puzzle");}
else {T_Scroll_Message("Puzzle Has No Solution"); }
if (Filled == 80) {T_Msg2("Non-Unique","Solution!");} else{T_Msg2("No","Solution!");} }
else {
DDTs("Recursive Descent/Backtrack Solution Succeeded!",NL);
DDTv("Recursive Solution Required ",RDC_Calls,SL);
DDTs(" Tries",SL);
Solve_Timer = (millis()-Solve_Timer)/1000;
DDTv(" and ",Solve_Timer,SL);
DDTs(" seconds",NL);
T_Msg3("Success!",FDM("Required ",RDC_Calls," tries"),FDM("and ",Solve_Timer," Seconds"));
T_Scroll_Message("Recursive Search Succeeded!");
T_Scroll_Message(FDM("Required ",RDC_Calls," tries"));
T_Scroll_Message(FDM(" and it took ",Solve_Timer," Seconds"));
return;}
} else { T_Msg3("Chain","Algorithms","Worked!"); // if AFTER FC and/or RP we've made progress, reset flag
FC_Invoked = false;} // and reenter algorithm loop
} // end of initial "no progress"
if (CCC <0) {DDTv("Less than no candidates left",CCC,NL);
T_Msg1("Error!");
T_Scroll_Message("Error!");
T_Scroll_Message("Negative candidates left!!");
Display_Debug();
while(1){;}}
if (Filled > 81) {DDTv("Overfilled at",Filled,NL);
T_Msg2("Error!","Overfilled");
Display_Debug();
while(1){;}}
} while (Filled < 81 && !No_Solution); // end of "While Not Filled"
} // end of Solve Puzzle
void Fill_The_Cell(int n, int r,int c, String x){ // update the grid and database
int b = In_Box(r,c);
DDTs (x,SL);
DDTv(" is placing ",n,SL);
DDTs(" in ",SL);
Show_RC(r,c,NL);
if (Show_Clear_Place) {T_Scroll_Message(FDM_FTC(n,r,c,x));} // show and scroll
if (Puzzle_Grid[r][c] !=0 ){DDTv("DUPLICATE PLACE!",Puzzle_Grid[r][c],SL);
Show_NRC(n,r,c,NL);
T_Msg2("Duplicate","Placement");
T_Scroll_Message(F("Duplicate Placement"));
T_Scroll_Message(FDM_FTC(n,r,c,"Error"));
Display_Debug();
while(1){;}}
#ifdef Test_Mode3 // if defined in input grid then
if (n != Solution_Grid[r][c]){ // for debugging
DDTv("Making mistake putting ",n,SL); // tests whether n placed in cell matches solution
DDTs(" in ",SL);
Show_RC(r,c,SL);
DDTv(" - should be ",Solution_Grid[r][c],NL);
T_Msg3("Mistake","Versus","Solution");
T_Scroll_Message(F("Mistake Against Solution"));
T_Scroll_Message(FDM_FTC(n,r,c,"Error"));
Display_Debug();
while(1){;}}
#endif
Puzzle_Grid[r][c] = n;
Filled++; // increment how many cells are filled (will end with 81)
Placement_Removes_Candidates(n,r,c); // and clear candidates matrix
Candidates[r][c] = 0; // ensure cleared for this cell
if (Candidates_Count[r][c] >0) { // clear counts for cell and decrement calculated
CCC = CCC - Candidates_Count[r][c];
Candidates_Count[r][c] = 0; }
T_Number(r,c,n,Entry_Color); //update display
} // end of Fill The Cell
void Build_Candidates(){
for (int r = 0; r < 9;r++) { // clear the candidate matrix
for (int c = 0; c < 9; c++){ // and counts first
Candidates[r][c] = 0;
Candidates_Count[r][c] =0; }}
for (int r = 0; r < 9;r++) { // build the candidate matrix
for (int c = 0; c < 9; c++){ // if it is a candidate, mark it
for (int n = 1; n <= 9; n++){ // check all nine possibles
if (Can_Go(n, r,c)) {Candidate_On(n,r,c);} }} // set and increase count for # of candidates
} // end of building candidate count and content
} // end of build candidates
bool Can_Go(int check_number, int r, int c){
if (Puzzle_Grid[r][c] != 0) return false; // if cell already has completed entry, can't go here
for (int cc= 0; cc < 9; cc++) {if (Puzzle_Grid[r][cc] == check_number){return false;}} // check all columns for this row, and
for (int rr= 0; rr < 9; rr++) {if (Puzzle_Grid[rr][c] == check_number){return false;}} // and all rows for this column, and
for (int rr =Box_Coords[In_Box(r,c)][Row_Pointer]; rr < Box_Coords[In_Box(r,c)][Row_Pointer]+3; rr++){ // all cells in the box
for (int cc = Box_Coords[In_Box(r,c)][Column_Pointer]; cc< Box_Coords[In_Box(r,c)][Column_Pointer]+3; cc++){
if (Puzzle_Grid[rr][cc] == check_number){return false;}}}
return true; // neither, so it can go here
} // end of can go
void Naked_Singles(){
for (int r = 0; r < 9; r++){ // check for naked singles - only one candidate for a cell
for (int c = 0; c< 9; c++){ // for these, one candidate only and count is 1
if ((Candidates_Count[r][c]) == 1){ // if any cell has a candidate count of 1
Fill_The_Cell(Find_Next_Candidate(r,c,1),r,c,"Naked Single");}}}} // if it does, fill it
void Hidden_Singles(){ // check for hidden singles - multipe candidates potentially in cell
for (int r = 0; r < 9; r++){ // but this is the only 'n'(i.e., only occurence of candidate) in this row or column or box
for (int c = 0; c< 9; c++){
for (int n = 1; n<=9; n++){ // check each number
if (If_Candidate_On(n,r,c)){ // that is present as a candidate
Occurence_Counter = 0; // assume its the only one
for (int cc = 0; cc <9; cc++){ // check each column in the row
if (If_Candidate_On(n,r,cc)){Occurence_Counter++;}} // if we found this candidate in the row, its not unique
if ( Occurence_Counter == 1){
Fill_The_Cell(n,r,c,"Hidden Single");}} // and if it is unique, place it
if (If_Candidate_On(n,r,c)){ // that is present as a candidate
Occurence_Counter = 0; // assume its the only one
for (int rr = 0; rr <9; rr++){ // check each row in the column
if (If_Candidate_On(n,rr,c)){Occurence_Counter++;}} // if we found this candidate in the row, its not unique
if ( Occurence_Counter == 1) {Fill_The_Cell(n,r,c,"Hidden Single");}} // and if it is unique, place it
if (If_Candidate_On(n,r,c)){ // that is present as a candidate
Occurence_Counter = 1; // assume its the only one
for (int srr = Box_Coords[In_Box(r,c)][Row_Pointer]; srr <= (Box_Coords[In_Box(r,c)][Row_Pointer])+2; srr++){ //walk the box
for (int scc = Box_Coords[In_Box(r,c)][Column_Pointer]; scc <= (Box_Coords[In_Box(r,c)][Column_Pointer])+2; scc++){
if (!((srr == r) && (scc==c))) { if (If_Candidate_On(n,srr,scc)){Occurence_Counter++;}}}} // check each cell but not the source cell
if ( Occurence_Counter == 1) {Fill_The_Cell(n,r,c,"Hidden Single");}} // and if it is unique, place it
}}} // end of row, column number iteration
} // end of Hidden Singles
/*
* Locked Candidates Type 1 (Pointing): If in a block all candidates of a certain digit are confined to a row or column, that digit cannot appear outside of that block in that row or column.
* Locked Candidates Type 2 (Claiming): Works exactly the other way round: If in a row (or column) all candidates of a certain digit are confined to one block, that candidate that be eliminated from all other cells in that block.
*/
void Pointing(){
int BitMask_R ; // row instance counter, and
int BitMask_C; // column one too
for (int b = 0; b < 9; b++){ // check all the boxes in the puzzle
for (int n = 1; n <=9; n++){ // and all candidate numbers in each box
BitMask_R = 0;
BitMask_C = 0; // clear instance counters
for (int srr = Box_Coords[b][Row_Pointer]; srr <= (Box_Coords[b][Row_Pointer])+2; srr++){ //walk the box
for (int scc = Box_Coords[b][Column_Pointer]; scc <= (Box_Coords[b][Column_Pointer])+2; scc++){
if (If_Candidate_On(n,srr,scc)){bitSet(BitMask_R,srr); // for every 'n' found, mark the row in the row bitmask
bitSet(BitMask_C,scc);}}} // and same for column
if (BitsCount(BitMask_R) == 1){Clear_Row_Outside_Box(n,BitsWhich(BitMask_R),b,"Pointing Lock");} // if found only in one row , clear row of candidate OUTSIDE box b
if (BitsCount(BitMask_C) == 1){Clear_Column_Outside_Box(n,BitsWhich(BitMask_C),b,"Pointing Lock");} // if found in only one column, clear it OUTSIDE of box
} // end of each number
} // end of each box
}// end of Pointing
void Claiming(){ // note this is also sometimes called "Box/Line Intersection"
int BitMask_B;
for (int r = 0; r < 9; r++){ // check this row
for (int n = 1; n <=9; n++){ // for each number
BitMask_B = 0;
for (int c = 0; c < 9; c++){if (If_Candidate_On(n,r,c)){bitSet(BitMask_B,In_Box(r,c));}} // for every 'n' found, mark the bit corresponding to the box in the bitmask
if (BitsCount(BitMask_B) == 1){Clear_Box_Except_Row(n,r,BitsWhich(BitMask_B),"Claiming Lock");}}} // if all n in this row are in only one box , clear candidate inside box b, except for this row
for (int c = 0; c < 9; c++){ // check all the columns too
for (int n = 1; n <=9; n++){ // of that, you can eliminate that candidate from any other cells in the row or column that the candidate is aligned on.
BitMask_B = 0;
for (int r = 0; r < 9; r++){if (If_Candidate_On(n,r,c)){bitSet(BitMask_B,In_Box(r,c));}} // for every 'n' found, mark the box in the bitmask
if (BitsCount(BitMask_B) == 1){Clear_Box_Except_Column(n,c,BitsWhich(BitMask_B),"Claiming Lock");}}} // if all n in this row are in only one box , clear candidate inside box b, except for this row
} // end of claiming
void Naked_Pairs_Triples_Quads(){ // Naked triples are harder to spot. Sometimes, all three numbers in a naked triple appear in all three boxes
//of the triple. However, sometimes the numbers of the triple don't all appear in all three boxes
String Clear_String = " "; // indicator string
// start of row pass
for (int r = 0; r<9; r++){ // step through each row
for (int n = 4; n >=2; n--){
CC_Length = 0;
Clear_String = "Naked " + PTQ_String[n-2]; // construct string for display
for (int c = 0; c<9; c++){
if ((Candidates_Count[r][c]<= n) && (Candidates[r][c] > 0)){ // only load if candidates under limit and non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[r][c]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[r][c]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = r; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = c;
CC_Length++;}} // increment counter too
if (CC_Length >= n){ // search if we found sufficient number of cells to bother
BitMask_Result = NPTQ_Search(n,CC_Length);
if(BitMask_Result> 0){ // returned bitmask if found a match
for (int cc = 0; cc < 9; cc++){
Clear_All_But_Marked(r,cc,BitMask_Result, Clear_String); } // clear candidates from remainder of row
}} }}
for (int c = 0; c<9; c++){ // step through each column
for (int n = 4; n >=2; n--){
CC_Length = 0;
Clear_String = "Naked " + PTQ_String[n-2]; // construct string for display
for (int r = 0; r<9; r++){
if ((Candidates_Count[r][c]<= n) && (Candidates[r][c] > 0)){ // only load if candidates under limit and non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[r][c]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[r][c]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = r; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = c;
CC_Length++;}} // increment counter too
if (CC_Length >= n){ // search if we found sufficient number of cells to bother
BitMask_Result = NPTQ_Search(n,CC_Length);
if(BitMask_Result> 0){ // returned bitmask if found a match
for (int rr = 0; rr < 9; rr++){
Clear_All_But_Marked(rr,c,BitMask_Result, Clear_String); } // clear candidates from remainder of column
}} }}
for (int b = 0; b <9; b++){ // start of box pass
for (int n = 4; n >=2; n--){
CC_Length = 0;
Clear_String = "Naked " + PTQ_String[n-2]; // construct string for display
for (int srr = Box_Coords[b][Row_Pointer]; srr <= Box_Coords[b][Row_Pointer]+2; srr++){
for (int scc = Box_Coords[b][Column_Pointer]; scc <= Box_Coords[b][Column_Pointer]+2; scc++){
if ((Candidates_Count[srr][scc]<= n) && (Candidates[srr][scc] > 0)){ // only load if candidates under limit and non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[srr][scc]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[srr][scc]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = srr; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = scc;
CC_Length++;}} // increment counter too
if (CC_Length >= n){ // search if we found sufficient number of cells to bother
BitMask_Result = NPTQ_Search(n,CC_Length);
if(BitMask_Result> 0){ // returned bitmask if found a match
for (int srr = Box_Coords[b][Row_Pointer]; srr <= Box_Coords[b][Row_Pointer]+2; srr++){
for (int scc = Box_Coords[b][Column_Pointer]; scc <= Box_Coords[b][Column_Pointer]+2; scc++){
Clear_All_But_Marked(srr,scc,BitMask_Result, Clear_String); }}} // clear candidates from remainder of cells in this box
}} }}
} // end of Candidates Naked Pairs Triples Quads
int NPTQ_Search(int snumber, int scounter){ // search array - called with number of cells (2,3,4) and number of entries in array
for (int start_ptr = 0; start_ptr < scounter; start_ptr++){ // check each cell against remaining cells
Match_Counter = 0; // number of matching cells
for (int i = 0; i < 9; i++){CanMark[i] = false;} // clear markers
BitMask = CanCand[start_ptr]; // initial bitmask of candidates
for (int check_ptr = start_ptr; check_ptr < scounter; check_ptr++){ // check starting pointer against all remaining pointers
if ((Number_of_Candidates(BitMask,CanCand[check_ptr])<= snumber) ) // if this would add too many candidates, mark false
{CanMark[check_ptr] = true; // We would not over-run bit count, so mark it good
BitMask = BitMask | CanCand[check_ptr]; // accumulate a new mask
Match_Counter++;} // at each accumulation, increment match counter
} // end of checking start pointer against all others
if (Match_Counter == snumber) { // if we have the right number, return the mask, else use 0 as a no match flag
return BitMask;} else {return 0;}
} // end of all start pointers in row, column or box
} // end of NPTQ Search
void Hidden_Pairs_Triples_Quads(){ // Hidden pairs, triples and quads. A pair or more that can only be placed in n cells, where n is the number we are searching
for (int r = 0; r<9; r++){ // step through each row
CC_Length = 0;
for (int c = 0; c<9; c++){
if (Candidates[r][c] > 0){ // load each non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[r][c]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[r][c]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = r; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = c;
CC_Length++;}} // increment counter too
HPTQ_Process();
} // end of all rows
//start of column pass
for (int c = 0; c<9; c++){ // step through each column
CC_Length = 0;
for (int r = 0; r<9; r++){
if (Candidates[r][c] > 0){ // load each non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[r][c]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[r][c]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = r; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = c;
CC_Length++;}} // increment counter too
HPTQ_Process();
} // end of all columns
for (int b = 0; b <9; b++){ //start of box pass
CC_Length = 0;
for (int srr = Box_Coords[b][Row_Pointer]; srr <= Box_Coords[b][Row_Pointer]+2; srr++){
for (int scc = Box_Coords[b][Column_Pointer]; scc <= Box_Coords[b][Column_Pointer]+2; scc++){
if (Candidates[srr][scc] > 0){ // only load if candidates if non-zero (filled) cell
CanCount[CC_Length] = Candidates_Count[srr][scc]; // Load length of each cell in row
CanCand[CC_Length] = Candidates[srr][scc]; // load contents of each cell
CanCoord[CC_Length][Row_Pointer] = srr; // load cell coordinates too
CanCoord[CC_Length][Column_Pointer] = scc;
CC_Length++;}}} // increment counter too
HPTQ_Process();
} // end of all boxes
} // end of Candidates Hidden Pairs Triples Quads
void HPTQ_Process(){ // process row, column or box for hidden pair, triple, quad
int BM[5]; // process pairs, triples and quads
String Clear_String = " "; // indicator string
Clear_String = "Hidden " + PTQ_String[0]; // construct string for display
for (int m1 = 0; m1 < CC_Length-1; m1++){ // process pairs
for (int m2 = m1+1; m2 < CC_Length; m2++){
BitMask = CanCand[m1] & CanCand[m2]; // get initial mask
for (int m = 0; m < CC_Length; m++){
if ((m != m1) && (m != m2)){
BitMask = BitsOff(BitMask, CanCand[m]);}} // remove candidates present outside the pair
if (BitsCount(BitMask) == 2){
for (int i = 0; i < CC_Length; i++){CanMark[i] = false;} // unmark all the markers
CanMark[m1] = true; // and mark these two cells to process
CanMark[m2] = true;
Clear_HPTQ(BitMask,Clear_String); // call the clearing mechanism
CanCand[m1] = Candidates[CanCoord[m1][Row_Pointer]][CanCoord[m1][Column_Pointer]]; // and update the analytical array for new contents of
CanCand[m2] = Candidates[CanCoord[m2][Row_Pointer]][CanCoord[m2][Column_Pointer]]; // these two cells
}}} // end of process pairs
Clear_String = "Hidden " + PTQ_String[1]; // construct string for display
for (int m1 = 0; m1 < CC_Length-2; m1++){ // process triplets
for (int m2 = m1+1; m2 < CC_Length-1; m2++){ // rolling through all possible triplets in the
for (int m3 = m2+1; m3 < CC_Length; m3++){ // CanCan analytical array (loaded above)
BM[1] = CanCand[m1]; // load the three bit marker
...
This file has been truncated, please download it to see its full contents.
//#define Test_Only // define to truncate test/demo list
/*
* Puzzles are loaded into both the puzzle grid and the solution grid
* Entries of numbers 1-9 are loaded into initial puzzle grid and solution grid
* Entries of numbers 11-19 are loaded ONLY into the solution grid (used to check puzzle algorithms)
* Remember to true up Puzzles Number total to match
* Each puzzle is one-dimensional (0-80) and loaded into each row and column by Test_Transfer routine
* PROGMEM is used to conserve global variable space (non-program-storage space)
* Some basic information on solving techiques is included as a comment after the puzzle definitions
*/
const byte Easy [81 ] PROGMEM = // easy - solvable *****
{ 3,12,17,19,4,11,8,15,16,
16,5,4,7,12,8,9,13,11,
1,8,19,15,16,3,7,14,2,
12,1,16,18,19,14,5,7,3,
17,14,5,11,13,16,2,18,19,
9,3,8,12,15,17,11,6,14,
4,19,1,6,18,15,13,2,7,
18,16,2,3,17,9,4,1,15,
15,17,3,14,1,12,16,19,8};
const byte HR_1 [81 ] PROGMEM = // test hidden rectangle and has a WXYZ wing clear too
{ 3,9,4,6,8,2,1,5,7,
6,1,8,7,3,5,4,2,9,
5,2,7,4,19,11,3,6,8,
1,5,3,19,4,7,12,18,6,
4,7,12,5,6,8,19,3,1,
8,6,19,11,12,13,7,4,5,
7,3,6,8,11,4,15,19,2,
9,4,5,12,17,16,18,11,3,
2,8,1,13,15,19,16,17,4};
const byte HR_2 [81 ] PROGMEM = // test hidden rectangle also
{ 16,9,11,4,5,13,2,18,17,
3,15,2,7,8,11,16,9,14,
7,14,18,2,9,16,15,1,13,
9,3,5,1,2,8,7,4,6,
18,7,14,6,13,9,11,12,15,
12,11,16,5,14,7,18,13,9,
1,2,9,3,7,5,4,6,8,
5,6,3,8,1,4,9,17,12,
4,8,7,9,6,2,3,5,1};
const byte WXYZ [81 ] PROGMEM = // WXYZ Wing test
{ 7,1,19,18,4,13,15,12,16,
5,6,14,2,11,7,18,3,19,
8,2,13,16,15,9,7,14,11,
6,5,7,4,13,11,2,9,18,
2,14,8,19,6,15,3,11,7,
19,3,1,7,18,2,14,6,15,
14,19,6,3,7,18,11,15,12,
11,7,2,5,19,4,6,8,3,
3,18,5,11,2,6,19,7,4};
const byte Forbidding_1 [81 ] PROGMEM = // test forbidding chain with group node
{ 12,6,18,15,1,3,7,14,9,
5,4,11,19,17,8,13,6,2,
13,7,9,6,2,14,8,15,11,
11,8,13,2,4,15,9,7,16,
17,19,4,11,13,16,5,2,8,
16,2,15,17,8,9,14,1,13,
18,13,17,14,16,2,11,9,5,
4,5,12,13,19,11,16,8,7,
19,11,6,8,5,17,12,3,14};
/*
const byte Forbidding_2 [81 ] PROGMEM = // test forbidding chain with group node (not loaded now)
{ 17,5,2,4,3,1,9,6,18,
18,3,6,17,19,12,14,1,5,
1,9,14,18,16,15,13,2,17,
2,11,17,13,14,19,15,18,6,
9,4,18,16,15,17,12,13,11,
5,6,13,11,12,18,7,4,9,
3,17,9,12,18,16,11,15,14,
6,12,5,19,1,14,18,17,13,
14,8,11,5,17,13,6,9,12};
*/
const byte XC1 [81 ] PROGMEM = // Tests of X Chain
{ 2,7,11,18,6,13,5,4,19,
19,5,14,1,2,7,13,8,16,
13,16,18,4,15,19,2,7,11,
18,11,19,13,4,6,7,5,2,
16,2,7,5,19,8,4,1,13,
5,14,13,7,1,2,9,16,8,
1,3,6,2,7,4,8,9,5,
7,8,5,19,13,1,16,2,4,
14,19,2,16,18,15,1,13,7};
const byte XC2 [81 ] PROGMEM = // Tests of X Chain
{ 3,17,4,5,2,11,19,8,16,
11,18,6,14,9,13,15,17,12,
19,5,12,18,7,16,3,11,14,
15,14,17,6,8,9,11,2,3,
12,19,11,7,3,4,16,15,18,
18,6,3,1,5,2,7,14,19,
14,1,15,9,6,18,12,13,17,
17,12,9,13,4,15,18,6,11,
6,13,8,2,1,7,14,19,5};
const byte XC3 [ 81] PROGMEM = // Tests of X Chain
{ 12,14,16,3,5,1,7,8,19,
8,5,7,6,2,9,3,4,1,
1,19,13,8,7,4,16,15,2,
5,13,9,1,6,2,8,17,4,
6,8,1,15,4,17,2,19,13,
14,17,12,19,13,8,1,6,15,
7,1,8,14,19,13,15,2,16,
19,12,15,17,1,16,14,13,8,
13,6,14,12,8,15,19,1,7};
const byte UR_3a [81 ] PROGMEM = // check UR3
{ 9,12,4,15,7,16,18,1,13,
1,3,7,12,18,9,6,14,15,
6,15,8,14,13,1,12,9,7,
5,1,9,17,12,13,4,6,8,
2,7,3,16,14,18,1,5,9,
4,8,6,9,1,5,7,3,2,
17,16,2,13,5,14,19,18,1,
13,19,1,8,16,12,15,17,14,
18,4,5,1,9,17,13,2,6};
const byte Medium_1[81 ]PROGMEM = // medium - solvable
{ 19,1,16,2,13,5,17,14,8,
17,2,4,9,8,16,11,13,5,
13,5,8,7,14,1,19,2,16,
6,19,5,3,17,2,14,8,1,
2,18,7,1,16,14,3,15,9,
14,13,1,5,19,8,2,6,17,
11,14,2,6,15,7,8,19,13,
8,16,13,14,1,19,5,17,2,
15,17,9,18,2,3,16,1,14};
const byte Medium_2 [81 ]PROGMEM = // medium 2
{ 13,19,15,16,4,7,12,1,18,
17,2,18,5,11,13,19,14,6,
14,16,11,9,12,18,17,13,5,
12,15,3,11,19,14,18,6,17,
19,17,4,8,16,12,11,15,13,
11,18,6,13,17,15,4,9,2,
16,4,12,17,3,19,15,18,11,
8,11,19,12,15,6,13,7,14,
5,13,17,4,18,1,16,12,19};
const byte Difficult_1 [81 ]PROGMEM = // difficult
{ 18,17,13,5,4,1,16,19,12,
14,15,6,12,7,19,11,13,8,
12,9,11,16,13,8,15,17,14,
5,6,18,14,2,13,19,1,17,
17,11,2,19,15,16,4,18,13,
13,14,19,11,18,7,12,16,15,
11,8,14,3,16,5,17,12,9,
19,12,17,18,1,14,13,15,6,
16,3,5,17,19,12,18,14,11};
const byte UR [81 ]PROGMEM = // Invokes Unique Rectangle 1
{ 16,18,15,1,13,12,14,7,19,
7,3,14,15,9,18,11,16,12,
2,11,19,17,6,4,15,3,18,
19,12,6,18,17,1,13,4,15,
18,15,1,3,14,19,17,2,6,
14,17,13,2,15,16,8,19,11,
15,6,8,4,12,17,9,11,13,
3,14,12,9,11,15,16,18,17,
1,19,17,16,18,13,12,15,14};
const byte UR2V [81 ]PROGMEM = // Invokes Unique Rectangle 2, 2nd one
{ 11,7,9,13,14,12,15,18,6, // Vertical x.x
3,18,5,6,19,1,4,17,12, // ...
6,14,12,18,15,17,13,11,19, // Box x.x
5,6,4,17,13,8,19,2,11,
2,9,8,5,1,4,6,3,7,
7,1,3,2,16,19,8,5,4,
14,13,17,19,12,15,11,6,8,
8,5,11,4,17,16,2,19,3,
19,12,6,11,18,13,17,4,15};
const byte UR2H [81 ]PROGMEM = // Invokes Unique Rectangle 2
{ 4,6,9,5,18,13,2,7,1, // Horizontal x.........x
1,8,5,7,6,2,4,3,9, // Box x.........x
7,2,3,9,11,14,8,5,6,
6,4,7,8,5,9,3,1,2,
3,1,8,4,2,7,6,9,5,
9,5,2,11,13,6,7,8,4,
12,17,4,13,9,11,5,6,18,
18,13,1,6,14,5,9,12,17,
5,9,6,12,7,18,1,14,13};
const byte UR5 [81 ] PROGMEM = // test case for UR type 5
{ 13,9,11,8,14,16,2,5,17,
8,17,15,2,19,13,16,1,14,
14,6,12,7,11,15,13,8,19,
9,8,4,5,2,1,7,6,3,
7,2,6,4,3,8,5,9,1,
5,1,3,19,16,7,4,2,8,
12,3,19,16,8,4,1,7,5,
1,5,8,3,7,12,19,4,16,
16,14,17,1,5,19,8,3,12};
const byte Expert [81 ] PROGMEM =
{ 12,19,14,11,16,15,18,13,17,
16,11,7,8,3,14,9,15,12,
13,18,5,19,17,2,6,4,11,
15,13,2,6,18,11,14,7,19,
17,4,11,12,15,19,13,8,16,
18,6,19,17,14,3,2,11,15,
19,2,8,4,11,17,5,16,13,
14,17,13,15,9,6,1,12,18,
11,15,16,13,12,18,17,19,14};
const byte FC [81 ]PROGMEM = // Requires a forcing chain
{ 4,11,15,2,7,13,6,19,18,
7,9,8,1,5,6,2,3,4,
16,2,13,8,4,19,15,11,7,
2,3,7,4,6,8,9,5,1,
8,4,9,5,3,1,7,2,6,
5,6,1,7,9,2,8,4,3,
13,8,2,16,1,5,4,7,9,
11,7,16,19,2,4,3,18,15,
19,15,4,13,8,7,11,16,2};
const byte XWing [81 ] PROGMEM = // Test x-wing and xy-wing algorithms
{ 1,18,17,14,12,13,5,6,9,
4,9,2,17,5,6,1,13,8,
13,5,6,1,18,9,2,4,17,
15,13,9,6,4,17,8,12,1,
17,6,4,12,1,18,19,15,13,
2,1,8,19,3,5,6,17,4,
18,4,13,5,19,12,17,1,6,
9,17,5,13,6,1,4,18,2,
6,2,1,18,17,14,13,19,5};
const byte Swordfish_1 [81 ] PROGMEM = // Test Swordfish algorithm
{ 1,9,5,3,6,7,2,4,8,
12,7,8,11,5,14,3,6,9,
3,14,6,12,9,8,1,5,7,
16,12,3,7,8,11,5,9,14,
7,11,9,14,12,5,18,13,6,
5,8,4,9,13,6,7,1,12,
8,3,2,5,4,9,6,7,1,
9,16,7,18,1,3,14,2,5,
14,5,1,16,7,2,9,18,13};
const byte Jellyfish_1 [81 ] PROGMEM = // Test Jellyfish algorithm
{ 14,6,17,3,11,9,12,8,15,
11,15,3,17,18,12,6,14,19,
2,19,18,14,6,15,17,13,1,
16,8,12,1,15,3,14,9,17,
19,11,15,18,7,14,13,12,16,
13,7,14,2,19,6,11,5,18,
7,12,11,19,3,18,15,16,4,
15,14,9,16,12,17,8,11,13,
18,3,16,5,14,1,19,7,12};
const byte Diabolical_1 [81 ] PROGMEM = // Uses many algorithms incl. two forcing chains
{ 1,18,16,13,14,15,12,7,19,
19,3,2,18,7,11,14,16,15,
5,4,7,16,2,9,18,13,1,
17,5,1,19,13,14,16,12,18,
3,16,19,2,18,7,15,11,4,
14,12,18,15,11,16,3,9,17,
2,11,13,4,9,18,7,5,6,
16,17,14,11,5,13,9,8,12,
18,9,15,17,16,12,11,14,3};
const byte Diabolical_2 [81 ] PROGMEM = // test case for UR type 5, other goodies, including XYZ Wing
{ 3,14,18,15,11,17,19,6,12,
15,6,11,4,12,19,8,7,13,
19,17,12,16,3,8,4,15,1,
12,8,16,17,4,11,13,9,15,
14,5,19,2,8,3,17,1,16,
17,1,13,19,5,16,12,4,18,
1,12,4,3,7,15,16,18,19,
18,9,7,11,16,2,15,3,14,
16,3,15,18,19,14,11,12,7};
const byte Diabolical_3 [81 ] PROGMEM = // Was recursive until chains got to it, does show XYZ Wing too!
{ 18,17,11,5,16,12,14,3,9,
16,3,9,18,4,1,2,5,7,
14,12,5,17,3,9,6,8,11,
15,9,14,3,2,17,11,6,18,
12,11,8,9,5,6,7,4,13,
17,16,13,14,1,8,9,2,15,
19,4,6,1,18,5,3,17,12,
13,8,7,12,9,14,5,1,16,
11,5,12,16,17,13,18,19,14};
const byte Diabolical_4 [81 ] PROGMEM = // was used to fix UR 5 error
{ 4,13,8,15,9,16,11,2,17,
15,7,6,12,14,11,8,13,19,
2,19,11,7,18,3,14,16,15,
17,15,9,1,16,12,13,18,4,
16,1,14,19,3,18,17,5,12,
3,18,12,14,17,5,6,19,11,
18,14,15,3,11,9,12,17,6,
11,12,3,16,15,17,9,4,18,
19,6,17,18,2,14,5,11,3};
const byte Diabolical_5 [81] PROGMEM = //Does have XYZ but still stumped and requires recursive search!
{ 11,5,16,13,14,8,17,19,2,
18,19,17,6,12,11,13,15,14,
13,4,2,5,9,17,1,18,16,
14,11,13,8,17,16,19,12,5,
16,17,9,12,1,15,8,14,13,
2,18,15,19,13,4,16,11,17,
17,13,1,14,5,9,2,6,18,
15,12,18,11,16,3,14,17,19,
9,16,14,7,18,12,15,3,11};
const byte RP_1 [81 ] PROGMEM = // Tests Remote_Pair
{ 1,7,8,6,14,9,13,5,12,
9,3,4,1,5,12,6,18,7,
2,5,6,7,18,3,14,1,19,
7,9,3,5,6,18,12,4,1,
6,4,1,12,3,7,5,9,18,
8,2,5,9,1,4,7,3,6,
5,6,7,3,19,1,18,12,14,
4,1,12,18,7,5,19,6,13,
3,8,19,4,12,6,1,7,5};
const byte RP_2 [81 ] PROGMEM = // Tests Remote_Pair
{ 7,9,8,4,5,2,3,1,6,
6,14,3,7,8,1,15,9,2,
15,1,2,19,3,16,8,7,14,
3,7,11,2,6,5,19,4,8,
8,2,19,1,4,3,7,6,15,
14,6,15,8,9,7,11,2,3,
9,8,16,15,1,4,2,3,7,
1,13,7,16,2,8,14,5,19,
2,15,14,13,7,19,16,8,1};
const byte MD_1 [81 ] PROGMEM = // Medusa 3-D tests 1
{ 17,9,3,8,2,4,5,6,11,
14,8,5,6,13,11,19,17,2,
2,11,6,19,7,5,14,13,8,
3,2,1,7,6,9,8,4,5,
19,16,14,2,5,8,3,11,17,
5,7,8,11,4,13,2,9,6,
8,5,19,14,1,6,7,2,3,
11,14,7,13,8,2,6,5,19,
16,13,2,5,19,7,1,8,14};
const byte MD_1_B [81 ] PROGMEM = // Medusa 3-D tests 1, Sudoku coach
{ 3,12,5,6,4,9,7,11,8,
7,4,11,8,2,15,13,9,16,
8,16,9,11,13,7,12,4,15,
1,3,4,5,7,2,6,8,9,
16,15,17,9,8,4,11,12,3,
9,8,2,13,6,11,5,7,4,
2,11,16,4,9,13,8,15,7,
15,9,8,7,1,16,4,3,2,
4,17,13,2,15,8,9,16,1};
const byte MD_1_37 [81 ] PROGMEM = // Medusa 3-D tests 1 with 37 eliminations!
{ 16,17,12,9,11,8,4,3,15,
19,15,4,7,13,2,6,8,11,
13,8,1,16,5,4,19,17,2,
17,14,5,18,16,3,1,2,9,
11,19,16,5,2,17,3,14,8,
12,13,18,14,9,11,5,6,17,
15,16,13,12,7,9,8,1,14,
18,1,7,13,14,5,12,19,6,
4,12,19,1,18,6,17,5,13};
const byte MD_2 [81 ] PROGMEM = // Medusa 3-D Tests 2
{ 3,18,16,11,5,2,14,19,17,
2,5,17,3,14,19,16,1,18,
19,11,4,6,18,7,5,2,3,
16,9,3,2,17,11,8,14,5,
5,7,11,18,16,14,12,3,19,
4,12,8,19,3,5,17,6,11,
11,16,5,4,19,8,3,17,12,
17,3,12,5,11,6,19,8,4,
8,4,19,17,2,3,11,5,6};
const byte MD_2_B [81 ] PROGMEM = // Medusa 3-D Tests 2, Series B
{ 6,4,13,7,19,15,8,12,11,
12,7,11,18,6,4,15,13,19,
18,15,9,1,12,3,4,7,6,
5,11,7,4,13,18,19,6,2,
3,6,18,12,11,19,7,15,14,
14,9,2,15,7,6,1,18,13,
7,13,14,6,18,1,2,9,15,
9,2,15,13,4,7,6,1,18,
11,18,6,9,15,2,13,14,7};
const byte MD_3 [81 ] PROGMEM = // Medusa 3-D Tests Rule 3
{ 2,9,16,15,17,14,8,3,11,
14,11,18,16,2,13,9,7,15,
15,13,17,1,18,9,4,16,2,
8,4,5,7,6,1,2,9,3,
6,12,11,13,19,18,5,4,7,
13,17,9,12,4,5,16,11,8,
9,18,3,4,15,7,11,12,16,
11,6,14,18,3,12,7,15,9,
17,5,12,19,11,16,3,8,4};
const byte MD_3_B [81 ] PROGMEM = // Medusa 3-D Tests Rule 3, Series B
{ 9,17,1,18,3,12,16,5,4,
8,5,12,16,14,11,17,3,19,
4,13,16,5,17,19,8,11,12,
15,11,7,14,12,6,13,9,8,
2,9,8,3,1,5,14,16,7,
6,4,13,7,19,18,1,2,15,
7,12,4,19,16,13,15,8,11,
11,6,15,12,18,14,19,7,13,
3,8,9,11,5,7,2,14,6};
const byte MD_4 [81 ] PROGMEM = // Medusa 3-D Tests Rule 4
{ 1,19,12,18,5,6,17,14,3,
15,4,3,12,9,17,11,18,16,
8,17,16,11,4,3,15,19,2,
17,3,14,5,6,18,2,1,19,
9,5,18,4,2,1,16,3,7,
16,2,1,17,3,19,18,15,14,
3,1,7,9,8,12,14,16,5,
12,16,15,3,1,14,9,7,18,
14,18,19,6,7,15,3,12,1};
const byte MD_4_B [81 ] PROGMEM = // Medusa 3-D Tests Rule 4, Series B
{ 2,19,5,18,1,16,14,17,13,
11,4,18,13,9,7,16,5,12,
16,3,17,14,2,5,19,8,11,
8,17,4,16,5,11,13,12,19,
9,1,13,2,8,4,17,6,5,
5,16,12,9,7,13,8,11,4,
4,5,6,1,3,18,12,9,17,
13,12,11,7,6,19,5,4,18,
17,18,19,5,4,12,1,13,6};
const byte MD_5 [81 ] PROGMEM = // Medusa 3-D Tests Rule 5
{ 9,2,3,4,18,7,16,1,5,
8,7,6,11,5,13,9,2,4,
5,14,11,2,19,16,18,3,17,
7,6,9,13,2,15,1,4,18,
4,3,2,18,16,11,17,5,9,
1,8,5,19,17,4,2,6,13,
13,9,8,16,4,2,15,7,1,
2,11,7,15,3,19,4,8,6,
16,15,14,7,11,8,13,9,2};
const byte MD_5_B [81 ] PROGMEM = // Medusa 3-D Tests Rule 5, Series B
{ 16,5,3,11,19,7,18,4,12,
9,14,11,6,18,2,7,3,5,
12,18,7,3,5,14,16,11,19,
7,1,12,14,16,3,5,19,8,
14,6,5,19,12,18,11,7,13,
8,13,9,5,7,11,14,2,16,
11,9,8,7,3,16,2,5,14,
5,12,14,8,11,9,13,16,7,
13,7,16,2,14,5,9,8,11};
const byte MD_6 [81 ] PROGMEM = // Medusa 3-D Tests Rule 6
{ 9,8,6,7,2,1,3,4,5,
3,11,4,9,5,6,18,12,7,
15,12,7,18,3,14,9,6,11,
18,7,3,12,6,5,14,11,9,
6,9,12,14,1,7,15,18,3,
1,14,15,3,9,18,2,7,6,
14,15,18,6,7,9,11,3,12,
12,6,9,1,4,3,7,15,18,
7,3,1,5,8,2,6,9,4};
const byte MD_6_B [81 ] PROGMEM = // Medusa 3-D Tests Rule 6, Series B
{ 13,7,2,6,15,4,19,8,11,
16,11,15,13,8,9,4,7,12,
4,8,9,1,17,12,13,6,5,
15,19,1,8,14,13,6,12,7,
8,16,14,12,11,17,15,19,3,
2,13,7,19,16,15,8,11,14,
7,12,16,15,13,8,1,14,19,
11,14,3,7,9,16,12,15,8,
19,5,8,4,12,1,7,13,16};
const byte MD_3456 [81 ] PROGMEM = // Medusa 3-D Tests Rules 3,4,5,6
{ 9,15,8,13,2,11,14,7,6,
6,12,14,19,15,7,1,18,13,
1,7,13,18,16,14,15,2,19,
17,18,5,4,13,16,12,9,1,
3,9,1,7,8,2,16,14,5,
4,6,12,11,19,5,8,3,17,
18,4,17,16,11,13,19,5,12,
5,13,6,12,14,19,17,1,18,
2,1,9,5,7,18,3,16,4};
const byte Workout [81 ] PROGMEM = // Uses many different solvers
{ 11,18,16,14,12,5,17,19,3,
9,13,2,1,18,17,16,14,5,
7,4,15,16,13,19,11,8,12,
5,11,3,18,17,4,12,16,9,
16,9,18,13,15,12,14,17,1,
12,17,4,19,16,1,5,13,18,
8,16,11,5,14,13,9,2,17,
13,12,19,17,11,16,18,15,14,
14,15,17,2,9,18,3,11,16};
const byte Recursive_1 [ 81] PROGMEM = // Famous Arto Inkala puzzle 1 - one of the most difficult puzzles
{ 1,16,12,18,15,7,14,9,13,
15,3,14,11,2,19,16,17,8,
17,18,9,6,14,13,5,12,11,
14,17,5,3,11,12,9,18,16,
19,1,13,15,8,16,17,14,2,
6,12,18,17,19,4,11,13,15,
3,15,16,14,17,18,12,1,19,
12,4,11,19,13,15,18,16,7,
18,19,7,12,16,11,3,15,14};
const byte Recursive_2 [81 ] PROGMEM = // 2nd Famous Arto Inkala puzzle - one of the most difficult puzzles
{ 11,14,5,3,12,17,16,19,18,
8,13,19,16,15,14,11,2,17,
16,7,12,19,1,18,5,14,13,
4,19,16,11,18,5,3,17,12,
12,1,18,14,7,13,19,15,6,
17,15,3,2,19,16,14,8,11,
13,6,17,5,14,12,18,11,9,
19,18,4,17,16,11,12,3,15,
15,12,11,18,13,9,7,16,14};
// Matching pointers to each input grid and the name of the puzzle to display
const char Puzzle_Names_1[] PROGMEM = "Easy";
const char Puzzle_Names_2[] PROGMEM = "Medium";
const char Puzzle_Names_3[] PROGMEM = "Difficult";
const char Puzzle_Names_4[] PROGMEM = "Expert";
const char Puzzle_Names_5[] PROGMEM = "Jellyfish";
const char Puzzle_Names_6[] PROGMEM = "Unique Rectangle 1";
const char Puzzle_Names_7[] PROGMEM = "Unique Rectangle 2";
const char Puzzle_Names_8[] PROGMEM = "Unique Rectangle 3";
const char Puzzle_Names_9[] PROGMEM = "Unique Rectangle 4";
const char Puzzle_Names_10[] PROGMEM = "Hidden Rectangle 1";
const char Puzzle_Names_11[] PROGMEM = "Hidden Rectangle 2";
const char Puzzle_Names_12[] PROGMEM = "Remote Pair 1";
const char Puzzle_Names_13[] PROGMEM = "Remote Pair 2";
const char Puzzle_Names_14[] PROGMEM = "Diabolical 1";
const char Puzzle_Names_15[] PROGMEM = "Diabolical 2";
const char Puzzle_Names_16[] PROGMEM = "Diabolical 3";
const char Puzzle_Names_17[] PROGMEM = "Medusa 1";
const char Puzzle_Names_18[] PROGMEM = "Medusa 2";
const char Puzzle_Names_19[] PROGMEM = "Medusa 3";
const char Puzzle_Names_20[] PROGMEM = "Medusa 4";
const char Puzzle_Names_21[] PROGMEM = "Medusa 5";
const char Puzzle_Names_22[] PROGMEM = "Medusa 6";
const char Puzzle_Names_22a[] PROGMEM = "Workout!";
const char Puzzle_Names_23[] PROGMEM = "Long Recursive 1";
const char Puzzle_Names_24[] PROGMEM = "Long Recursive 2";
#ifdef Test_Only // used in conjuntion with Test configurations in puzzle solver to auto run one puzzle on startup
const byte* Puzzles_List [] = {Easy};
const char *const Puzzle_Names_Table[] PROGMEM = {Puzzle_Names_1};
#else
const char *const Puzzle_Names_Table[] PROGMEM = {Puzzle_Names_1, Puzzle_Names_2, Puzzle_Names_3, Puzzle_Names_4, Puzzle_Names_5,
Puzzle_Names_6,Puzzle_Names_7, Puzzle_Names_8, Puzzle_Names_9, Puzzle_Names_10,
Puzzle_Names_11,Puzzle_Names_12,Puzzle_Names_13,Puzzle_Names_14,Puzzle_Names_15,
Puzzle_Names_16, Puzzle_Names_17, Puzzle_Names_18, Puzzle_Names_19,Puzzle_Names_20,
Puzzle_Names_21,Puzzle_Names_22,Puzzle_Names_22a,Puzzle_Names_23,Puzzle_Names_24
};
const byte* Puzzles_List [] = { Easy,
Medium_1,
Difficult_1,
Expert,
Jellyfish_1,
UR,
UR2H,
UR_3a,
UR5,
HR_1,
HR_2,
RP_1,
RP_2,
Diabolical_3,
Diabolical_4,
Diabolical_5,
MD_1 ,
MD_1_B,
MD_2 ,
MD_3 ,
MD_5_B,
MD_6,
Workout,
Recursive_1,
Recursive_2};
#endif
// end
/*
* Solving Sudoku Puzzles
Fill in all blank cells making sure that each row, column
and 3 by 3 box contains the numbers 1 to 9.
The Basics:
Firstly, it's impossible to get very far without carefully
maintaining a list of 'possible values' or candidates for each
blank cell. Doing this by hand is laborious and prone to error,
and often detracts from the fun of solving these puzzles.
Fortunately, programs like this one will do this for you,
while leaving you with the fun of applying logic to solve each
puzzle.
If you don't have a program to help - systematically analyse at
each blank cell. Start with the assumption it can have any digit
(or value) between 1 and 9, and then remove all values which
have already been assigned to other cells in its respective row,
column and 3x3 box. This leaves each blank cell with a list of
candidates.
Singles:
Any cells which have only one candidate
can safely be assigned that value.
It is very important whenever a value is
assigned to a cell, that this value is also
excluded as a candidate from all other
blank cells sharing the same row,
column and box. (Programs like Simple
Sudoku will do this laborious step
automatically for you too.)
Hidden Singles:
Very frequently, there is only one
candidate for a given row, column or box,
but it is hidden among other candidates.
In the example on the right, the
candidate 6 is only found in the middle
right cell of the 3x3 box. Since every box
must have a 6, this cell must be that 6.
Beyond the Basics:
While the two steps above are the only ones which will directly
assign a cell value, they will only solve the simplest puzzles.
That's fortunate, otherwise Sudoku wouldn't be as popular as it
is today. The following steps (in increasing complexity) will
reduce the number of candidates in blank cells so, sooner or
later, a 'single' candidate or 'hidden single' candidate will
appear.
Beyond the Basics
Locked Candidates 1: (Pointing)
Sometimes a candidate within a box is restricted to one row or
column. Since one of these cells must contain that specific
candidate, the candidate can safely be excluded from the
remaining cells in that row or column outside of the box.
In the example below, the right box only has candidate 2's in its
bottom row. Since, one of those cells must be a 2, no cells in
that row outside that box can be a 2. Therefore 2 can be
excluded as a candidate from the highlighted cells.
Locked Candidates 2: (Claiming)
Sometimes a candidate within a row or
column is restricted to one box. Since
one of these cells must contain that
specific candidate, the candidate can
safely be excluded from the remaining
cells in the box.
Naked Pairs:
If two cells in a group contain an identical pair of candidates and
only those two candidates, then no other cells in that group could be those values.
These 2 candidates can be excluded from other cells in the group.
Advanced Steps:
Naked Triples & Naked Quads:
The same principle that applies to Naked
Pairs applies to Naked Triples & Naked
Quads.
A Naked Triple occurs when three cells in
a group contain no candidates other that
the same three candidates. The cells
which make up a Naked Triple don't have
to contain every candidate of the triple. If
these candidates are found in other cells
in the group they can be excluded.
A Naked Quad occurs when four cells in a
group contain no candidates other that
the same four candidates.
Hidden Pairs:
If two cells in a group contain a pair of
candidates (hidden amongst other
candidates) that are not found in any
other cells in that group, then other
candidates in those two cells can be
excluded safely.
Hidden Triples:
If three candidates are restricted to three cells in a given group,
then all other candidates in those three cells can be excluded.
Hidden triples are generally extremely hard to spot but
fortunately they're rarely required to solve a puzzle.
Hidden Quads:
If four candidates are restricted to four cells in a given group,
then all other candidates in those four cells can be excluded.
Hidden Quads are very rare, which is fortunate since they're
almost impossible to spot even when you know they're there.
For the Addict:
The following techniques are no more difficult than those above
but requires observation as to how specific candidates relate to
each other (in particular patterns) beyond any given row,
column or box.
X-Wing:
For every Sudoku, a value can exist only once in each row,
column and box. If a value has only 2 possible locations in a
given row (ie it has a candidate in only 2 cells in that row), then
it must be assigned to one of these 2 cells. Given a particular
puzzle that has two rows where a given candidate 'C' is
restricted to exactly the same two columns (and no more than 2
columns), and since:
1) candidate C must be assigned once in each of these two
rows, and
2) no column can contain more than one of candidate C
then candidate C must be assigned exactly once in each of
these two columns within these two rows. Therefore, it's not
possible for any other cells in these two columns to contain
candidate C. This same logic applies when a puzzle that has two
columns where candidate C is restricted to exactly the same two
rows.
Swordfish:
The Swordfish pattern is a variation on the "X-Wing" pattern above.
Formal definition:
Given a particular puzzle that has three rows where a given
candidate 'C' is restricted to the same three columns, and since
1. candidate C must be assigned once in each of these three rows
2. no column can contain more than one of candidate C
then candidate C must be assigned exactly once in each of
these three columns within these three rows. Therefore, it's not
possible for any other cells in these three columns to contain
candidate C.
This same logic applies when a puzzle that has three columns
where candidate C is restricted to exactly the same three rows.
The X-Wing and Swordfish techniques can be further
generalised to include rows containing candidates restricted to
four cells in the same four columns (called a Jellyfish).
XY-Wing (also called Y Wing):
Not to be confused with X-Wing (see above).
Formal definition:
Given 3 cells where -
1. all cells have exactly 2 candidates
2. they share the same 3 candidates in the form - xy, yz, xz
3. one cell (the Y 'stem' with canidates xy) shares a group
with the other 2 cells (Y 'branches' with candidates xz & yz)
then any other cell which shares a group with both 'branch' cells
can have excluded the 'z' candidate that is common to these 'branch' cells.
Proof: If a cell sharing a group with both branch cells is
assigned the 'z' candidate, then neither branch can be assigned
the 'z' candidate. Consequently, one branch would be the 'x' and
the other the 'y' leaving the 'stem' without a candidate, an
invalid state.
Note: If all 3 cells in a xy-wing pattern shared the same unit/house,
then they would be a 'naked triple'.
XYZ-Wing:
An XYZ-Wing is like an XY-Wing in that it is a group of three cells, one sharing a unit with the other two.
E.g., base is {1,4,5} and second cell in same box is {1,4}, need to find 3rd cell {1,5} outside box but still seen by base
However, the first cell in an XYZ-Wing has three candidates while the other two, called the wings, have two.
Each of the wings must share one candidate with the first cell, (that's part of sharing a unit) but of different values.
If the two second candidates in the wings are both the same, and are also the same as the extra candidate in the first cell,
then if any fourth cell shares that candidate and a unit with all three, that candidate can be eliminated.
It will be in the base's box and seen by base and both 'pincers'.
WXYZ-Wing:
A WXYZ-Wing is like an XY-Wing and an XYZ-Wing, except it is a group of four cells, one sharing a unit with the other three.
The first cell in a WXYZ-Wing has three or four candidates while the other three, called the wings, have two each.
Each of the wings must share one candidate with the first cell, (that's part of sharing a unit) but each wing must share a different value.
If the second candidates in the wings are all the same, and are also the same as the left-over candidate of the first cell if the first cell
has four candidates, then if any fifth cell shares that candidate and a unit with all the others, that candidate can be eliminated.
(E.g.) Cells in one box, Base {5,8,9}, {1,9}, {1,5} and one cell outside box that 'sees' the base {1,8}. If any other cell in the box has '1' and sees the outside
of the box cell too, eliminate the candidate 1 in that cell.
Unique Rectangle Type 1:
A "Unique Rectangle" (UR) consists of four cells that occupy exactly two rows, two columns, and two boxes.
All four cells have the same two candidates left (in real sudokus not all cells have to hold all of the UR candidates).
A UR Type 1 exists, if one of the four cells of a possible UR has additional candidates.
If those candidates were eliminated, the UR would exist, causing two solutions.
It is therefore absolutely necessary, that one of the additional candidates has to be true.
That means, that the UR candidates can be eliminated from the cell with the additional candidates.
Unique Rectangle Type 2:
If in a possible UR two non diagonal cells have only one extra candidate, and that candidate is the same in both cells,
all candidates seeing both extra candidates can be eliminated. In other words, you have two corners as in Type 1, and
two more that have those same two candidates plus an third, matching in both. That candidate can be eliminated from any cell that is
in the same house/unit as cell 3 and as cell 4 (the three-candidate corners) even those those cells may not be in same house as each other
Unique Rectangle Type 3:
This is a combination of UR with Naked/Locked Subsets. We look for two non diagonal cells in a possible UR that have extra candidates.
Since one of those candidates has to be set to avoid the UR, we can treat both cells as one virtual cell containing only
the extra candidates and try to build a Naked Subset (all additional cells have to see both UR cells with extra candidates).
If such a UR/Naked Subset is found, all subset candidates can be eliminated from all cells outside the subset (but in the same house).
So, one extra candidate seen in non-diagnal cells and one that is seen by both.
Unique Rectangle Type 4:
We look for additional candidates in two non diagonal cells again, but this time
we ignore those extra candidates and concentrate on the UR candidates themselves:
If one of the UR candidates is not possible anymore in any other cell of a house
that contains both cells with the extra candidates, the other UR candidate can be eliminated from those UR cells.
So search the house(s) that contain both non-diagonal cells (from the Type 2) and can't do the elimination if UR candidate cell is found
Unique Rectangle Type 5:
UR Type 5 is a variation of UR Type 2, but now the additional candidate can be in diagonal cells as well.
Suppose we have a possible UR with one extra candidate in either two diagonal cells or in three cells.
All occurences of that candidate can be eliminated in all cells that see all UR cells containing the additional candidate.
The logic behind that move is the same as in a UR Type 2. In other words, in the corners we have one 2-candidate bivalue and at least two others,
and maybe three, have three candidates with the 3rd matching in all. That candidate can be removed from any cell 'seen' by all three non-bivalue cells.
Hidden Rectangle:
Hidden Rectangles are very versatile, because they can be used in possible URs that contain up to
three cells with arbitrary additional candidates (the UR is hidden under a clutter of additional
candidates - not to be confused with Almost Unique Rectangles).
We need a possible UR with two or three cells containing additional candidates (with only one cell the
UR Type 1 should be used). Now take one UR cell without additional candidates and check the row and
the column containing the opposite corner of the UR. If one UR candidate is nowhere outside the UR in
those two houses, the other UR candidate can be eliminated from the opposite corner.
Links and Inferences for chains
The basis of all chains are two types of basic implications, normally called "links" or "inferences"
Weak Links
If two entities are weakly linked, they cannot be true at the same time. That means: If one of them is true,
then the other has to be false (but both can be false as well, so if one is false, nothing can be concluded).
In simple chains the entities are normally simply candidates, that share a house or a cell.
Strong Links
If two entities are strongly linked, they cannot be false at the same time.
That means: If one of them is false, then the other has to be true (both true is only possible in very advanced types of links).
If we use candidates, we would need exactly two candidates sharing a cell, or exactly two instances of the same candidate sharing a house (a conjugate pair in coloring terms).
Those two link types are the basis for every type of chains, so the difference between them has to be understood completely. To sum it up:
Weak Link: If a is true then b is false
Strong Link: If a is false then b is true
XY-Chain:
This method can be used when a great number of cells contain only two possible candidates.
in choosing one of the candidates in a starting cell, one forms a chain of choices
which results in the suppression of a candidate in a given cell.
If the other candidate is chosen in the starting cell and one ends with the suppression
of the same candidate, it can be excluded safely.
Pick your starting cell, and make a small u shape (a little smiley curve) underneath the first pencilmark.
From there, look around, but instead of crossing out pencilmarks (otherwise it gets too messy!),
when you find a value that it forces somewhere else, put the same u shape underneath the forced value.
Ignore any that the first choice eliminated you might need them later!
Carry on doing this until you cant make any more u forces.
Now choose the second value in your original cell and this time put a little n symbol (a downturned mouth) above the second pencilmark.
Like before, look at the implications and forces that this makes, continuing on until you cant find any more.
If theres a forcing chain, at some point youll find a pencilmark with both a u and n on the same mark
(in which case theyll almost join up!). This its a sure sign that whichever candidate you picked for the first cell,
youve found the right value for the second cell.
X-Chain:
X-Chains are chains that use one digit only. X-Chains of length 4 are sometimes called Turbot Fishes.
A X-Chain is a single-digit solving technique which uses a chain consisting of links that alternate between strong links and weak links,
with the starting and ending link being strong. In other words, the chain involves an even number of cells having the target digit as a candidate.
The target digit can be eliminated from any cell that is seen by both ends of the X-Chain.
The important thing with X-Chains is, that they have to start and end with a strong link. This ensures that one of the endpoints actually contains
the chain digit. That digit can be removed from any cell that sees both ends of the chain. (EG -- even number of nodes, elimination cell must 'see' both ends)
Forbidding Chain -- Really another version of X-Chain, but implemented some handling of group nodes and that opens up more strong links for chains. Begin and
end on weak link using single digit chain and alternating links. If you reach the head again, eliminate that candidate.
Remote Pair Chain:
Remote Pair is the simplest chaining technique. It considers only bivalue cells that contain the same two candidates.
Since the cells are bivalue, a strong link exists within every cell between the two candidates. The links between the cells
can therefore be weak (the cells have to see each other). To eliminate something, the chain has to be at least four cells long.
The Remote Pair ensures, that any cell within the chain has the opposite value of the cell before it. Any cell outside the Remote Pair
that sees two cells with different values cannot have one of the Remote Pair digits set.
Medusa 3D:
3D Medusa extends single's chains into a third dimension. Medusa 3-D extends the search is up through the bi-value cells which contain two different numbers.
You can think of the different candidate numbers as existing in a third dimension lifting up from the page with 1 at the bottom and 9 at the top.
In other words, its a chain that can jump not only between cells on strong links but inside a bivalue cell as well. Start the chain on a cell and one candidate in that cell and chain with alternating 'colors'. Create all possible chains and then
analyze the chain using six rules.
Rule 1 - Twice in a Cell - If two candidates in a cell have the same colour - all of that colour can be removed - and the opposite colour are all solutions. All that color in the ENTIRE puzzle grid!
Rule 2 - Twice in a Unit - Similiar to 1, but looking for two coloured occurrences of X in the same unit (row, column or box) as opposed the two of the colour in the same cell.
Rule 3 - Two Different Colors in a Cell with more than 2 candidates - We know that either ALL the blue candidates will be true, or ALL the green ones. If there are any another candidates in any cell with two colours, they cannot be solutions
Rule 4 - Two Colors "Elsewhere" - where there are candidates that can see both colours they can be removed. By 'see' we mean any candidates that are the same candidate as members of the blue/green links. (e.g., a '6' sees both a green and blue '6'). It can be removed.
Rule 5 - Two Colors in Unit and Cell - If an uncoloured candidate can see a coloured candidate elsewhere (it shares a unit) AND an opposite coloured candidate in its own cell, it can be removed.
Rule 6 - Cell Emptied by Color - If all the candidates in an uncolored cell can 'see' their counterparts all colored the same, ALL of that color can be removed (e.g., same as 1, in the entire grid)
*/
Comments
Please log in or sign up to comment.